一類混合HS和DY共軛梯度法及其全局收斂性

王安平，馬 爍

(1.長江大學(xué) 工程技術(shù)學(xué)院，湖北 荊州 434020；2.荊州理工職業(yè)學(xué)院 基礎(chǔ)課部，湖北 荊州 434000)

0 引言

xx+1=xk+αkdk

(1)

(2)

其中，x1為初始點，dk為搜索方向，αk由某種線性搜索或由特定公式計算出的步長因子，βk為參數(shù)，gk=f(xk).關(guān)于βk的著名公式[1]有：

其中yk-1=gk-gk-1,‖·‖為歐式范數(shù).一般情況下，F(xiàn)R，CD和DY方法有較強(qiáng)的收斂性，HS，PRP和LS方法卻有很好的數(shù)值實驗效果．為了利用各種共軛梯度法的優(yōu)勢，得到更好收斂性和數(shù)值效果，許多學(xué)者先后提出了各種不同的混合共軛梯度法[1，2]．1990年，Toutai-Ahmed和Storey首次提出混合FR和PRP共軛梯度法，避免了FR方法可能連續(xù)產(chǎn)生小步長的缺點，其中βk的計算公式為：

1992年，Gilbert和Nocedal[3]對其作了進(jìn)一步研究，提出如下混合共軛梯度法：

考慮到HS方法較好的數(shù)值表現(xiàn)和DY方法好的收斂性，2001年，Dai和Yuan[4]提出了DY方法和HS方法的混合形式，其中βk的計算公式為：

并取得了很好的數(shù)值效果．文獻(xiàn)[5]給出了一種新的HS和DY混合算法，其中βk的計算公式，

文獻(xiàn)[6]提出了FR和PRP的某種凸組合，其中βk的計算公式，

文獻(xiàn)[7]又提出了一種關(guān)于CD和LS的某種凸組合的共軛梯度方法，其中βk的計算公式為

其它關(guān)于混合共軛梯度法還可參見文獻(xiàn)[8-13].受上述文獻(xiàn)的啟發(fā)本文提出了DY和HS某種凸組合的共軛梯度法，其中新的βk公式：

(3)

1 混合的HS-DY算法及其下降性

本文的步長策略為Wolfe線搜索，即選取αk>0滿足

(4)

(5)

其中δ和σ是滿足0<δ<σ<1的常數(shù)．

本文我們提出的一種HS和DY混合共軛梯度法，記為WHD方法：

步1.給定初始點x1∈Rn及收斂精度ε>0，d1=-g1，令k:=1；

步2.若‖gk‖≤ε，則停止迭代；否則由式(2)和式(3)求得dk；

步3.按照Wolfe線搜索式(4)和式(5)來計算步長αk；

步4.計算xx+1=xk+αkdk，置k:=k+1，轉(zhuǎn)步2

(6)

(7)

(8)

2 新算法的全局收斂性分析

為了證明本文算法的收斂性，本文作如下必要的假設(shè)H:

(1)f(x)在水平集L1={x∈Rn|f(x)≤f(x1)}有界，其中x1為初始點;

(2)在水平集L1的一個鄰域U內(nèi)f(x)連續(xù)可微的，其梯度g(x)是lipschitz連續(xù)的，即存在常數(shù)L>0使：

‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈U．

(9)

(10)

又由Cauchy-Schwarz不等式有：(gk+1-gk)Tdk≤‖gk+1-gk‖·‖dk‖≤Lαk‖dk‖2

于是得

(11)

再由式(4)與式(11)得

(12)

又因為函數(shù)列{fk}有界，所以有

即引理結(jié)論成立．

證：假設(shè)定理不成立，即?k都有g(shù)k≠0，則存在c>0，使得

‖gk‖2>c,k=1,2,3…

(13)

由式(3)與式(10)

(14)

由式(2)得dk+gk=βkdk-1，兩邊同時取平方得：

(15)

(16)

由式(14)及式(16)可得

(17)

式(2)兩端分別于gk作內(nèi)積得

(18)

由式(18)及式(7)可得

由式(17)，式(19)及式(13)可得

(20)

3 數(shù)值試驗

本節(jié)我們選用文獻(xiàn)[14][15]中的部分測試函數(shù)檢驗本算法，并將結(jié)果與標(biāo)準(zhǔn)HS方法和標(biāo)準(zhǔn)DY方法進(jìn)行比較.采用Wolfe線搜索，均不采用重新開始策略.測試環(huán)境為MATLAB7.9.0,運行環(huán)境為內(nèi)存4.00GB,CPU為2.60GHz的個人計算機(jī)上運行.參數(shù)設(shè)置如下：δ=0.1，σ=0.45，本文算法中μ=0.5，終止條件為‖gk‖≤10-6或It-limit>9999，計算得到3種方法的數(shù)值結(jié)果如表1所示.

表1 數(shù)值測試結(jié)果及其比較

注：表中“Prolem與DIM”分別表示測試函數(shù)的名稱和維數(shù) “NI/NF/NG”依次表示迭代的次數(shù)、函數(shù)值計算的次數(shù)和梯度值計算的次數(shù)，“F”表示迭代失敗.

本文提出的WHD算法,通過對26個問題的測試,而HS方法有8個函數(shù)測試失敗，DY方法有7個函數(shù)測試失敗．對于三種算法都能通過的測試函數(shù)，在迭代的次數(shù)，函數(shù)值計算的次數(shù)，梯度值計算的次數(shù)方面，本文算法比HS方法略好一些，但是比DY方法要好很多．結(jié)合實驗結(jié)果，說明本文算法是有效的．

[1]戴彧虹，袁亞湘.非線性共軛梯度法[M].上海：上海科學(xué)技術(shù)出版社，2000.

[2]D.Touati-Ahmed,C.S.Storey.Efficient hybrid congjugate gradient techniques[J].J.Opti.Theo.Appl.1990,64:379～397.

[3]J.C.Gilbert,J.Nocedal.Global convergence peoperties of conjugate gradient methods for optimization[J].SIAM.J.Opti.1992,2(1):21～42.

[4]Y.H.Dai,Y.X.Yuan.An efficient hybrid congjugate gradient method for unconstrained optimizaton[J].Anna.Oper.Rese.2001,103:33～47.

[5]Z.F.Dai,L.P.Chen.A mixed HS-DY conjugate gradient methods[J].計算數(shù)學(xué),2005,27(4):429～436.

[6]曹名園，楊月婷.求解大規(guī)模優(yōu)化的混合共軛梯度法[J].工程數(shù)學(xué)學(xué)報，2013，30(1):10～18.

[7]張 雁，單 銳，王換鵬,等.一類混合CD-LS共軛梯度法的全局收斂性[J].遼寧工程技術(shù)大學(xué)學(xué)報(自然科學(xué)版)，2013，32(3):409～412.

[8]董曉亮，高岳林，何郁波.一類Armijo搜索下的混合HS-PRP共軛梯度法[J].工程數(shù)學(xué)學(xué)報，2013，30(3):370～376.

[9]W.Jia,J.Z.Zong,X.D.Wang.AN Improved Mixed Conjugate Gradient Method[J].Syst.Engi.Proc.2012,4:219～225．

[10]X.F.Yang,Z.J.Luo,X.Y.Dai.A Global Convergence of LS-CD Hybrid Conjugate Gradient Method[J].Adva.Nume.Anal.，2013,9:1～5．

[11]Y.Y.Huang,S.Y.Liu,X.W.Du,et al.A Globally Convergent Hybrid Conjugate Gradient Method and Its Numerical Behaviors[J].J.Appl.Math.，2013,3：1～14．

[12]王開榮，王書敏.具有充分下降性的修正型混合共軛梯度法[J].山東大學(xué)學(xué)報(自然科學(xué)版)，2013，48(9):78～84.

[13]馬 爍.一種帶強(qiáng)Wolfe線搜索的CD和LS混合共軛梯度法[J].重慶工商大學(xué)(自然科學(xué)版)，2014，32(4):62～65.

[14]J.J.More,B.S.Garbow,K.E.Hillstrome.Testing unconstrained optimization software[J].ACM Trans Math.sofe.1981,7:17～41.

[15]N.Andrei,An unconstrained Optimization test functions Collection[J].Adva.Mode.Opti.,2008,10(1):147～161．