搜索下的记忆梯度法及其收敛性

Wolfe线性搜索下的超记忆梯度法及其收敛性汤京永;董丽【摘要】研究无约束优化问题, 给出了一种新的超记忆梯度法, 在较弱条件下证明了算法具有全局收敛性和线性收敛速率. 数值试验表明新算法是有效的.【期刊名称】《吉林大学学报（理学版）》【年(卷),期】2010(048)003【总页数】5页(P396-400)【关键词】无约束优化;超记忆梯度法;全局收敛性;线性收敛速率【作者】汤京永;董丽【作者单位】信阳师范学院,数学与信息科学学院,河南,信阳,464000;上海交通大学,数学系,上海,200240;信阳师范学院,数学与信息科学学院,河南,信阳,464000【正文语种】中文【中图分类】O221.21 引言考虑无约束优化问题min f(x), x∈Rn,(1.1)其中: Rn是n维欧氏空间; f(x): Rn→R为连续可微函数. 本文设f(x)的梯度函数为g(x), 若xk为当前迭代点, 则g(xk)简记为gk, f(xk)简记为fk, f(x*)简记为f *.求解问题(1.1)的算法主要是迭代法, 基本格式为xk+1=xk+αkdk,(1.2)这里dk为f(x)在xk点的下降方向, αk为f(x)沿该方向的搜索步长. 对αk和dk的不同选择构成了不同的迭代法[1].对于dk, 可采用dk=-gk, 此种算法称为最速下降法[1]. 此类算法虽然结构简单, 每次迭代的计算量小, 但收敛速度慢且容易产生拉锯现象. 若f(x)二次连续可微, 则可采用dk=-Hkgk, 其中Hk为▽2f(xk)-1或▽2f(xk)-1的某种近似, 此种算法称为拟牛顿法[1]. 拟牛顿法虽然在一定条件下有较快的收敛速度, 但每次迭代时都需要计算和存储矩阵, 不适于求解大型优化问题. 上述两种算法在每步迭代时仅利用当前点的信息产生下一个迭代点, 而忽略了前面迭代点的信息, 这在算法设计中是一种信息浪费.共轭梯度法在每次迭代时通过记忆前一步的迭代信息产生下一个迭代点, 搜索方向的基本结构为其中βk是一个参数, 当βk用不同的公式时即得到了不同的共轭梯度法[1-2]. 此类算法有效避免了计算和存储矩阵, 是求解大型优化问题的有效方法之一, 但很多共轭梯度法不具有全局收敛性[2-3].为了充分利用前面迭代点的信息, 以改进算法的性能, 保证算法具有全局收敛性, 文献[4]提出了记忆梯度法[4]. 记忆梯度法是共轭梯度法的推广, 在每步迭代时同样不需计算和存储矩阵, 算法简单, 因而适于求解大型优化问题, 且与共轭梯度法相比, 此类算法增加了参数选择的自由度, 更有利于构造稳定的快速收敛算法[5-7]. 但很多记忆梯度法仅利用前一步的迭代信息, 同样忽略了前面迭代点的信息. 文献[8]提出一种超记忆梯度法, 算法在每步都能充分利用前面多步迭代点的信息, 并且具有全局收敛性.本文提出一种新的求解无约束优化问题的超记忆梯度法, 算法在每步迭代时都充分利用前面多步迭代点的信息产生下降方向, 采用Wolfe线性搜索产生步长, 在较弱条件下证明了算法具有全局收敛性. 当目标函数为一致凸函数时, 证明了算法具有线性收敛速率. 数值试验表明算法是有效的.2 超记忆梯度法及其性质假设:(H1) 目标函数f(x)在水平集L0={x∈Rn|f(x) ≤f(x1)}上有下界;(H2) 梯度函数g(x)在包含L0的开凸集B上一致连续;(H3) f(x)是二次连续可微的一致凸函数.算法2.1 ρ∈(0,1), 0<σ1<σ2<1, m>0是一个整数, x1∈Rn. 令k ∶=1.步骤如下:(1) 若‖gk‖=0, 则停止迭代; 否则, 转(2);(2) 计算dk, 使其满足:(2.1)其中(2.2)(3) xk+1=xk+αkdk, 其中αk由Wolfe线性搜索确定, 即要求αk满足:(2.3)(2.4)(4) 令k ∶=k+1, 转(1).引理2.1 对任意的k≥1, 有注2.1 由引理2.1及式(2.3)可知{fk}单调不增, 即fk≤fk-1≤…≤f1, 从而知xk∈L0.引理2.2 对任意的k≥1, 有‖dk‖≤(1+ρ)‖gk‖.3 算法的全局收敛性定理3.1 假设(H1)和(H2)成立, {xk}是由新算法产生的迭代点列, 则证明: 首先证明{‖dk‖}有界. 由引理2.2知, 只需证明{‖gk‖}有界. 假设{‖gk‖}无界, 则存在无穷子列N⊂{1,2,…,}, 使得‖gk‖→+∞, k∈N, k→+∞.(3.1)由式(2.3)和引理2.2知(3.2)因为{fk}单调不增且有下界, 故知{fk}有极限, 从而由式(3.2)知(3.3)因此αk‖gk‖2→ 0 (k∈N, k→+∞), 于是由式(3.1)可知αk‖gk‖→ 0 (k∈N,k→+∞), 进而再由引理2.2可得αk‖dk‖→0, k∈N, k→+∞.(3.4)由式(2.4)、引理2.1及引理2.2可得(3.5)从而由(H2)和式(3.4)可得‖gk‖→ 0 (k∈N, k→+∞), 这与式(3.1)矛盾. 因此, {‖gk‖}有界.假设则存在无穷子列K⊂{1,2,…}及υ>0, 使得‖gk‖>, ∀k∈K.(3.6)由式(3.3)和(3.6)知,(3.7)从而知αk→ 0 (k∈K, k→+∞). 因为{‖dk‖}有界, 故知式(3.4)成立. 又由式(3.5)及假设(H2)和式(3.4)知‖gk‖→ 0 (k∈K, k→+∞), 这与式(3.6)矛盾. 因此,4 算法的线性收敛速率引理4.1[5] 若假设(H3)成立, 则假设(H1)和(H2)成立, f(x)在Rn上有唯一的极小点x*, 且存在M≥m>0, 使得:(4.1)m‖x-x*‖≤‖g(x)‖≤M‖x-x*‖.(4.2)引理4.2[5] 若假设(H3)成立, 则g(x)在水平集L0上Lipschitz连续, 即存在常数L>0, 使得‖g(x)-g(y)‖≤L‖x-y‖, ∀x,y∈L0.定理4.1 若假设(H3)成立, {xk}是由算法2.1产生的无穷点列, 则{xk}至少线性收敛于x*.证明: 由式(2.3)和引理2.1可知(4.3)又由式(3.5)知(4.4)从而由引理4.2可得于是由引理2.2知(4.5)又由式(4.3)和(4.5)可得(4.6)令则易知0<ω<1/2, 从而由式(4.6)知fk-fk+1≥ω‖gk‖2.余下的证明类似于文献[5]中的定理3, 故略.5 数值试验为进一步检验算法2.1的实用效果, 选取两个算例对本文算法进行数值试验, 并与Wolfe搜索下的共轭梯度法和最速下降法进行比较. 用IT表示达到相应精度时算法的迭代次数, fk表示迭代结束时的目标函数值, NA表示本文提出的新算法, 用FR,PRP,HS,CD和DY分别表示FR,PRP,HS,CD及DY共轭梯度法[1-2], SM表示最速下降法. 参数取值为ρ=0.299, σ1=0.38, σ2=0.85. 计算结果列于表1～表3. 例5.1 f(x)=(x1-x2)2+(x2+x3-2)2+(x4-1)2+(x5-1)2,x0=(-2,2,-2,2,2)T, x*=(1,1,1,1,1)T, f *=0.例5.2 扩展Beale函数:其中n=40.例5.3 例5.2中取n=80.表1 精度为|fk-f *|≤10-8,10-9,10-10时例5.1的计算结果Table 1 Results of example 5.1 with precision requirements |fk-f *|≤10-8,10-9,10-10方法ITfkNA8,9,91.531 2×10-9, 7.188 6×10-11, 7.188 6×10-11FR12,13,158.254 4×10-9, 9.037 9×10-10, 2.920 9×10-11PRP10,11,123.531 8×10-9, 1.4309×10-10, 8.863 7×10-11HS19,20,212.685 8×10-9, 2.552 0×10-10, 1.2343×10-11CD12,13,141.442 0×10-9, 1.403 5×10-10, 6.294 6×10-11DY12,14,149.175 2×10-9, 8.899 0×10-11, 8.899 0×10-11SM14,15,163.465 8×10-9, 5.180 8×10-10, 6.871 2×10-11表2 精度为|fk-f *|≤10-4,10-5,10-6时例5.2的计算结果Table 2 Results of example 5.2 with precision requirements |fk-f *|≤10-4,10-5,10-6方法ITfkNA13,15,165.902 6×10-5, 2.291 6×10-6, 2.108 7×10-7FR21,26,275.054 4×10-5, 2.864 4×10-6, 6.378 0×10-7PRP14,15,171.672 2×10-5, 5.0709×10-6, 8.909 3×10-7HS83,143,2036.925 6×10-5, 9.915 7×10-6, 9.9476×10-7CD16,18,22 6.059 7×10-5, 8.275 8×10-6, 7.110 6×10-7DY22,25,264.830 1×10-5, 1.036 3×10-6, 4.843 8×10-7SM98,128,1728.586 6×10-5, 9.226 2×10-6, 8.990 0×10-7表3 精度为|fk-f *|≤10-4,10-5,10-6时例5.3的计算结果Table 3 Results of example 5.3 with precision requirements |fk-f *|≤10-4,10-5,10-6方法ITfkNA14,15,164.801 9×10-5, 4.583 2×10-6, 4.217 3×10-7FR22,26,285.609 5×10-5, 5.728 7×10-6, 5.096 6×10-7PRP14,16,193.344 5×10-5, 3.2499×10-6, 6.644 6×10-7HS94,162,2249.834 6×10-5, 9.961 2×10-6, 9.9260×10-7CD17,19,249.915 0×10-5, 8.436 0×10-6, 2.212 7×10-7DY22,25,269.660 2×10-5, 2.072 5×10-6, 9.687 6×10-7SM103,139,1839.330 6×10-5, 9.941 6×10-6, 9.897 4×10-7由表1～表3可见, 本文提出的新算法不但理论上具有全局收敛性和线性收敛速率, 而且数值效果较好, 特别在要求精度较高和规模较大时, 新算法具有更好的效果.参考文献【相关文献】[1] 袁亚湘, 孙文瑜. 最优化理论与方法 [M]. 北京: 科学出版社, 1997.[2] 戴或虹, 袁亚湘. 非线性共轭梯度法 [M]. 上海: 上海科学技术出版社, 2000.[3] MA Ming-juan, HUANG Qing-dao, DENG Jian. Conjugate Gradient Method with the Inexact Line Search [J]. Journal of Jilin University: Science Edition, 2009, 47(3): 505-506. (马明娟, 黄庆道, 邓键. 非精确条件下的共轭梯度方法 [J]. 吉林大学学报: 理学版, 2009, 47(3): 505-506.)[4] Miele A, Cantrell J W. Study on a Memory Gradient Method for the Minimization of Functions [J]. JOTA, 1969, 3(6): 459-470.[5] TANG Jing-yong, SHI Zhen-jun. A Class of Global Convergent Memory Gradient Methods and Its Linear Convergence Rate [J]. Advances in Mathematics, 2007, 36(1): 67-75. (汤京永, 时贞军. 一类全局收敛的记忆梯度法及其线性收敛性 [J]. 数学进展, 2007, 36(1): 67-75.)[6] TANG Jing-yong, DONG Li, GUO Shu-li. A New Memory Gradient Method with Curve Search Rule [J]. Journal of Xinyang Normal University: Natural Science Edition, 2009, 22(2): 179-182. (汤京永, 董丽, 郭淑利. 一类新的曲线搜索下的记忆梯度法 [J]. 信阳师范学院学报: 自然科学版, 2009, 22(2): 179-182.)[7] TANG Jing-yong, DONG Li, ZHANG Xiu-jun. A New Class of Memory Gradient Methods with Wolfe Line Search [J]. Journal of Shandong University: Natural Science, 2009, 44(7): 33-37. (汤京永, 董丽, 张秀军. 一类新的Wolfe线性搜索下的记忆梯度法 [J]. 山东大学学报: 理学版, 2009, 44(7): 33-37.)[8] SHI Zhen-jun. A New Super-Memory Gradient Method for Unconstrained Optimization[J]. Advances in Mathematics, 2006, 35(3): 265-274.。