陈 旦
(重庆师范大学数学科学学院，重庆沙坪坝 401331)
BB梯度法[1]是由Barzilai和Borwein在1988年提出的一种求解大规模无约束优化问题的新型梯度算法，考虑无约束优化问题：
(1)
其中f(x):Rn→R为连续可微函数，n是变量的个数.Barzilai和Borwein给出如下迭代格式：
xk+1=xk-αkgk
(2)
其中gk为f(x)在xk处的梯度，步长αk由下面两个迭代公式决定，分别为：
(3)
其中sk=xk+1-xk，yk=gk+1-gk，该步长利用了目标函数f(x)前后两个迭代点处的梯度值.同时，f(x)在二维凸二次情况下，该方法超线性速度收敛.
BB梯度法的提出极大地激发了人们重新研究梯度法的热情，也取得了很大的进展.文献[2]进一步证明了BB算法具有R-线性收敛速度，文献[3]结合GLL非单调线搜索[4]将BB算法推广到一般的无约束优化领域，提出了解无约束优化问题的BB算法并证明了该算法具有全局收敛性，数值结果表明，BB算法的数值性能比一些经典的共轭梯度法的要好.随后，许多解一般无约束优化问题的修正BB梯度法被提出来，如文献[5-8]等.
(4)
(5)
由于拟牛顿方程对拟牛顿法的理论和数值性能都有至关重要的影响，于是许多具有更好性质的修正拟牛顿方程也随之发展起来，例如：对于一类修正的拟牛顿方程[10]：
(6)
其中t为参数.当t=0时，(6)式为标准拟牛顿方程；
当t=1时，(6)式为2006年文献[11]提出的修正的拟牛顿方程；
当t=2时，(6)式为2011年文献[12]提出的修正拟牛顿方程；
当t=3且uk=sk时，(6)式为1999年文献[13]提出的修正拟牛顿方程.
2013年，文献[15]从插值的角度得到一个步长：
(7)
(8)
基于(6)式这一类修正的割线方程，可以发现该式中(gk+1+gk)Tsk和fk-fk+1前面的系数比为1∶2，同时也可以发现将修正的割线方程结合BB步长时，为了让修正的步长包含有更多迭代点处的信息，就分别令uk=sk和uk=yk得到了很多修正的步长，那么有没有一种更好的选取uk的方式，使得它既可以包含上述两种情况来获得一个步长，也可以让所得到的步长比上面这一类修正的BB步长都要好？本文通过结合文献[19]给出的混合割线方程，来改进文献[15]中提出的方法.该步长的选取不仅利用了更多迭代点处的函数值和梯度值信息，而且其对应的算法能进一步改进一类经典的BB型方法.数值结果表明，所改进的方法数值性能要优于文献[9,15]中一些经典的BB型方法.
在这一节中，对BB梯度法给出一些新的步长选择.首先，给出文献[19]中提出的混合割线方程以及新步长的推导，然后再说明改进的新步长的优点.
文献[19]中提出了一个修正的混合割线方程：
(9)
其中ϑk=(gk+gk+1)Tsk+2(fk-fk+1)，uk=(1-θk)yk+θksk，θk是一个混合参数且θk∈[0,1].该文献给出了θk的一个选择，即：
(10)
步骤1 若k=0，选择一个初始的θk∈[0,1]；
步骤2 由式子(10)计算θk；
步骤3 若θk<0，则令θk=0；
步骤4 若θk>0，则令θk=1.
(11)
进一步，结合上述混合割线方程，将(9)式中的uk分别应用到(6)式中t=2和t=3情形下的修正割线方程下，可以得到另外两个新的BB步长：
(12)
基于这些步长的选择，结合文献[15]中的算法框架提出一个修正的BB型算法，并且期待它们的结果比之前所改进的一类BB型算法更加有效.
在这一节中，给出所修正的BB梯度法的算法描述，选择初始步长后，利用Hager-Zhang非单调线搜索[20]来计算后面的近似步长，修正的BB梯度法(MSBB)步骤如下：
步骤0 给定初始值x0∈Rn，λmax≥λmin≥0，ε，γ∈(0,1)，η∈[0,1]，0<σ1<σ2<1；
计算f0，令C0=f0，Q0=1，α0=1，k=1.
步骤1 若‖gk‖≤ε，停止迭代；
否则，令dk=-αkgk，t=1.
步骤2 计算步长αk(Hager-Zhang线搜索).若满足：
(13)
令xk+1=xk+tdk，转向步骤3；
否则，选择t∈[σ1t,σ2t]，转向步骤2.
步骤3 通过(4)-(5)式，(8)式，(11)-(12)式计算步长αk，若αk<0，令αk=αBB1，若αk<0，再令αk=λmax；
否则，αk=min{λmax,{λmin,αk}}；
转步骤4.
步骤5 令k=k+1；
转向步骤1.
进一步给出上述算法的收敛性分析，收敛性结果用到了如下两个假设：
假设2.1 水平集Ω={x∈R:f(x)≤f(x0)}有界，即存在一个常数B>0，有
‖x‖≤B，∀x∈L.
假设2.2 目标函数f在Ω的某个邻域N连续可微，且梯度∇fLipschitz连续，即存在常数L>0，有
上述引理表明任何tk都满足非单调线搜索条件(13)，于是就可以确定上述算法.进一步，在[αmin,αmax]中选择步长αk，能确保存在两个常数c1和c2，使得搜索方向dk满足：
gkdk≤-c1‖gk‖2，‖dk‖≤c2‖gk‖，∀k∈R.
以这种方式，可以得到算法3.1的收敛性定理[13],下面定理的证明参考文献[20].
Hager-Zhang线搜索过程中的参数分别为γ=10-4，ηk=0.7，σ=0.8，另外两个参数分别为λmax=1030，λmin=10-30，混合参数的初始值为θk=0.5.这篇文章中的终止准则为：
‖gk‖∞≤10-6,
当迭代次数超过6 000时也会终止.从文献[21]中选择了85个测试函数，它们的维数介于100～100 000之间，算法的测试环境为Matlab2012a，联想Windows10下Ubuntu14.04操作系统，电脑的处理器为2.1 Ghz的Intel(R)Core(TM)i5-5 500 CPU，内存为4 G.
图1 计算时间性能曲线Fig.1 Performance profiles based on CPU time 图2 迭代次数性能曲线Fig.2 Performance profiles based on the number of iterations图3 梯度计算次数性能曲线Fig.3 Performance profiles based on the number of gradient calls图4 函数计算次数性能曲线Fig.4 Performance profiles based on the number of function calls
图1表明从计算时间性能曲线来看，SGW1和MSBB2可以解决22%的问题，SGZ1和MSBB1可以解决18%的问题，SBB4可以解决20%的问题，MSBB3可以解决36%的问题，如果我们青睐于能以最大效率解决95%的问题，那么MSBB1方法和MSBB3方法优选，如t>2时的性能曲线高度所示.类似地，从图2，图3，图4我们也可以看出当t>2时，MSBB2方法和SGW1,SGZ1,SBB4方法是可比的，MSBB1和MSBB3方法对应的性能曲线都在其他方法对应的性能曲线之上，因此，MSBB1方法和MSBB3方法更优.
本文基于文献[19]所提出的混合割线方程修正文献[14]中提出的步长，得到一个新的步长，新步长不仅利用了当前迭代点处的梯度值和函数值，也利用了前两次迭代点处的梯度值和函数值，同时基于文献[15]中新步长的推导过程，又提出了另外两个新的步长.在文献[15]中算法的框架下，结合Hager-Zhang非单调线搜索，所提出的方法具有全局收敛性.数值结果采用Dolan和More"提出的性能曲线，通过对6种方法的性能曲线分析MSBB1和MSBB3数值性能要更好.
猜你喜欢割线步长梯度基于Armijo搜索步长的BFGS与DFP拟牛顿法的比较研究成都信息工程大学学报(2021年5期)2021-12-30一个改进的WYL型三项共轭梯度法数学物理学报(2021年6期)2021-12-21一种自适应Dai-Liao共轭梯度法应用数学(2020年2期)2020-06-24一个具梯度项的p-Laplace 方程弱解的存在性华东师范大学学报（自然科学版）(2019年3期)2019-06-24一类扭积形式的梯度近Ricci孤立子数学年刊A辑(中文版)(2018年2期)2019-01-08潮流方程的割线法求解中国水利水电科学研究院学报(2018年2期)2018-05-24从一道试题谈圆锥曲线的切割线定理中学生理科应试(2016年10期)2016-12-06从圆的切割线定理谈起福建中学数学(2016年8期)2016-12-03基于逐维改进的自适应步长布谷鸟搜索算法河北科技大学学报(2015年5期)2015-03-11一种新型光伏系统MPPT变步长滞环比较P&O法电测与仪表(2014年2期)2014-04-04