精确线搜索下一种新的混合共轭梯度法

景书杰,王慧婷,牛海峰,陈 耀

(河南理工大学数学与信息科学学院,河南焦作 454000)

1 引言

考虑如下无约束优化问题

其中f(x)是Rn−→R上的连续可微函数,用非线性共轭梯度法求解无约束优化问题(1.1),点列{xk}的迭代格式为

这里的αk为步长.本文选用精确线搜索计算αk,即每步迭代中选择αk满足

选取步长因子αk最好的方法就是使目标函数沿着搜索方向dk达到极小,从理论上来说,精确线搜索所得到的步长因子有着最好的下降量.例如Zoutendijk[1]证明了采取精确线搜索的FR方法对一般非凸函数总收敛;从文献[2]中的结果可知用精确线搜索的PRP方法对一致凸函数全局收敛;Rivaie[3]提出了一个新算法在精确线搜索下有更好的结果.

搜索方向dk的迭代格式为

其中gk=▽f(xk),如果用θk表示向量dk与−gk的夹角,则有

这里的βk为一标量,著名的βk公式有(可参看文献[4–8])

其中‖·‖表示欧式范数.通常情况下,FR和DY方法有很好的收敛性,而PRP和HS方法却有很好的数值效果.学者们为了寻找既能保证收敛性又可以有良好数值效果的算法,在以上公式的基础上,一方面对βk进行改进例如文献[3,9,10],另一方面将不同的βk公式进行混合[11–13].最近,文献[3]中给出了一个新的参数公式

并得到了该算法在精确线搜索下的全局收敛性.受文献[12]的启发,取βNewk为

其中µ为参数且0＜µ≤1.

2 算法及其性质

本文讨论一种新的混合共轭梯度法,其中

算法A步骤1给定ε＞0,x1∈Rn,0＜µ≤1,d1=−g1,k:=1.

步骤2若‖gk‖＜ε,则停止;否则转步骤3.

步骤3由精确线搜索计算步长αk,使其满足(1.3)式.

步骤4令xk+1=xk+αkdk,求gk+1,并用(2.1)式试求βk+1.

步骤5令dk+1=−gk+1+βk+1dk,令k=k+1;转步骤2.

引理2.1对任意k≥1,算法A产生的搜索方向dk满足,其中C≥0.

证当k=1时故结论成立.

(i)当时,若有结论成立.否则有

因此当k＞1时,

因为0＜ µ≤1,故其中C ≥0.

(ii)当时,对式(1.3)有

引理2.2同引理2.1中的条件,由式(1.5)和(2.1)可得

证因为

由(2.1)式知,当所以

3 全局收敛性

假设

(H1)目标函数f(x)在水平集L0={x∈Rn|f(x)≤f(x1)}上有下界,其中x1为初始点.

(H2)目标函数f(x)在水平集L0的一个邻域N 内连续可微,且梯度函数g(x)满足Lipschitz连续,即存在常数L＞0,使

引理3.1若(H1),(H2)成立,考虑一般方法xk+1=xk+αkdk,其中dk满足步长αk满足精确线搜索(1.6)式,则有

证由(1.6)式,αk=min{α|∇f(xk+αdk)Tdk=0,α ＞ 0},即g(xk+αkdk)Tdk=0.再由 Lipschitz 条件 (3.1),有 ‖g(xk+ αkdk)− g(xk)‖ ·‖dk‖ ≤ Lαk‖dk‖2.由 Cauchy-Schwartz不等式可得

所以即又因为由假设可知,对一切α＞0都成立

定理3.1设目标函数满足假设(H1),(H2),若存在常数m ＞0,使得‖g(x)‖≤m,∀x∈L0,迭代点列{xk}由算法A产生,则有

证假设定理不成立,所以存在一个常数C＞0,有‖g(x)‖≤C.由dk+gk=βkdk−1,对等式两端取模平方,并移项得到

由引理2.2可知所以

两边除以得

又因为

所以

所以

即

与引理3.1中的(3.2)式矛盾,故

证毕.

参考文献

[1]Zoutendijk G.Nonlinear programming,computational methods[J].Integ.Nonl.Prog.,1970:37–86.

[2]Powell M J D.Restart procedures for the conjugate gradient method[J].Math.Prog.,1977,12(1):241–254.

[3]Rivaie M,Mamat M,June L W,Mohd I.A new class of nonlinear conjugate gradient coefficients with global convergence properties[J].Appl.Math.Comp.,2012,218:11323–11332.

[4]Hestenes M R,Stiefel E L.Methods of conjugate gradients for solving linear systems[J].J.Res.Nat.Bureau Stand.,1952,5(49):409–436.

[5]Fletcher R,Reeves C.Functions minimization by conjugate gradients[J].Comp.J.,1964,7(2):149–154.

[6]Polak E,Ribi´ere G.Note sur la convergence de m´ethodes de directions conjug´ees[J].Rev.Fran.Inform.Rech.Op´erationelle,1969,16(3):35–43.

[7]Polyak B T.The conjugate gradient method in extreme problems[J].USSR Comp.Math.Math.Phys.,1969,9:94–112.

[8]Dai Y H,Yuan Y X.A Nonlinear conjugate gradient method with a strong global convergence property[J].SIAM J.Optim.,1999,10:177–182.

[9]Rivaie M,Mamat M,Abashar A.A new class of nonlinear conjugate gradient coefficients with exact and inexact line searches[J].Appl.Math.Comp.,2015,268:1152–1163.

[10]Xu Z S.A class of new conjugate gradient methods[J].J.Math.,2002,22(1):27–30.

[11]江羡珍,韩麟,简金宝.Wolfe线搜索下一个全局收敛的混合共轭梯度法[J].计算数学,2012,34(1):103–112.

[12]戴志峰,陈兰平.一种混合的HS-DY共轭梯度法[J].计算数学,2005,27(4):429–436.

[13]景书杰,邓涛.精确线搜索下具有充分下降性的混合共轭梯度法[J].河南理工大学学报(自然科学版),2010,29(2):266–273.