Wolfe線搜索下的一個修正DY譜共軛梯度法

房明磊，孫敏(安徽理工大學數(shù)學與大數(shù)據(jù)學院，安徽 淮南 232001)

1 共軛梯度法

考慮如下無約束非線性優(yōu)化問題：

min{f(x)}|x∈Rn}

(1)

式中，x是決策變量；目標函數(shù)f:Rn→R是一光滑的非線性函數(shù)。

共軛梯度法是解決上述大規(guī)模非線性優(yōu)化問題的比較有效的常用方法，有著低存儲、易計算的優(yōu)點，其迭代格式的一般形式為：

xk+1=xk+αkdk

(2)

(3)

式中，gk=f(xk)是f(x)在點xk處的梯度；αk是滿足某種線搜索的步長；βk是標量，是調控方向的參數(shù)。

不同的βk選取方式對應著不同的共軛梯度法，著名的βk的計算公式[1～7]有：

其中， ‖·‖表示范數(shù)。

以上6個公式所對應的算法中， PRP、HS和LS方法具有很好的實驗效果，F(xiàn)R、DY和CD方法具有較強的收斂性質。為了利用共軛梯度法各自的特點，許多學者在這些公式的基礎上進行了大量的研究，對經(jīng)典的βk公式進行修改，有的是著重非負性改進，有的是著眼于充分下降性，有的則是考慮參數(shù)的混合，并且獲得了一些實驗效果和收斂性質都比較好的方法[8～13]。

Barzilai和Borwein等[14,15]分別介紹和討論了無約束問題的譜梯度法，Bingin[16]等提出譜梯度法和共軛梯度法結合的譜共軛梯度法，其迭代公式含有2個可變參數(shù):

該譜共軛梯度法在Wolfe 線搜索下收斂且數(shù)值結果較理想。對比傳統(tǒng)梯度法，譜梯度算法有很好的加速效果，許多學者也對譜共軛梯度法進行了大量的研究[17～20]。受譜共軛梯度法的啟發(fā)，筆者給出了一種修正的DY譜共軛梯度法。

2 修正的DY譜共軛梯度法

(4)

(5)

其中，0≤μ1≤μ2。當μ1=μ2=0時，該方法變?yōu)閭鹘y(tǒng)的DY共軛梯度法。

SMDY算法描述如下：

Step 1 初始化:x1∈Rn，δ∈(0,1)，σ∈(δ,1)，0≤μ1≤μ2,ε≥0,d1=-g1,k=1,若‖gk‖≤ε，停止；

Step 2 計算步長αk滿足標準的Wolfe非精確線搜索準則:

(6)

(7)

Step 3 置xk+1=xk+αkdk，若‖gk+1‖≤ε，停止迭代；

Step 5 置k=k+1，轉Step 2。

3 修正算法的全局收斂性

算法的全局收斂性證明以下列假設條件為基礎：

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

(H2)f(x)在Ω的某鄰域Ω1內連續(xù)可微，且其梯度函數(shù)g(x)滿足Lipschitz條件，即存在常數(shù)L>0，使得對?x,y∈Ω1，有：

‖g(x)-g(y)‖≤L‖x-y‖

(8)

并假定‖gk‖≠0，否則目標函數(shù)的穩(wěn)定點已獲得，算法終止。

證明用數(shù)學歸納法證明。

則：

(9)

故引理1得證。

引理2若αk滿足Wolfe非精確線搜索條件式(6)和式(7)，則：

(10)

證明由式(4)可知：

故引理2得證。

引理3若目標函數(shù)f(x)滿足假設條件(H1)(H2)，則SMDY算法產(chǎn)生的序列{gk}和{dk}滿足Zoutendijk條件:

證明由式(7)和式(8)可得：

從而可得：

結合式(6)和式(10)，可得：

(11)

對式(11) 從k=1,2,3,…求和：

并由假設(H1)知f(x)在Ω有界，可得：

證明用反證法證明。假設定理1結論不成立，則存在常數(shù)c>0，使得對?k≥1，有：

‖gk‖≥c

由式(3)移項得：

對等式兩端分別取模平方，再移項得：

(12)

(13)

反復利用式(13)遞推形式和‖gk‖≥c及d1=-g1，可得：

從而：

因而有：

這與引理3矛盾，故定理1得證。

4 結語

在經(jīng)典的DY算法基礎上提出了一種修正的譜共軛梯度算法，在Wolfe非精確線搜索下證明了算法的全局收斂性。由于構造譜參數(shù)的過程中引進了2個待定參數(shù)，在理論上2個參數(shù)只要滿足關系要求即可，但是在數(shù)值表現(xiàn)上可能會因為不同值的選取而使得數(shù)值試驗表現(xiàn)不同。

[參考文獻]

[1]Fletcher R, Reeves C M.Function minimization by conjugate gradients[J].Comput J,1964, 7: 149～154.

[2] Polak E, Ribière G. Note sur la convergence de mèthodes de directions conjugèes[J].Rev Fr Inform Rech Oper,1969, 3:35～43.

[3] Polyak B T.The conjugate gradient method in extreme problems[J].USSR Comput Math Math Phys, 1969, 9: 94～112.

[4] Hestenes M R, Stiefel E.Method of conjugate gradient for solving linear equations[J].J Res Natl Bur Stand, 1952,49: 409～436.

[5] 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.

[6] Fletcher R.Practical methods of optimization vol 1: unconstrained optimization[M].New York:Wiley& Sons,1987.

[7]Liu Y, Storey C.Efficient generalized conjugate gradient algorithms[J].Journal of Optimization Theory and Applications, 1991, 69:129～137.

[8] Jiang X Z，Lin H, Jian J B.A hybrid conjugate gradient method with descent property for unconstrained optimization [J].Applied Mathematical Modelling，2015, 39:1281～1290.

[9] Dai Y H, Kou C X.A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search[J].SIAM J Optim,2013,23:296～320.

[10] Jiang X Z， Jian J B. A sufficient descent Dai-Yuan type nonlinear conjugate gradient method for unconstrained optimization problems[J].Nonlinear Dynamics, 2013, 72:101～112.

[11]鄭小平，陳忠.一類推廣的共軛梯度法及收斂性分析[J].長江大學學報(自科版)，2016，13(34)：1～3.

[12] Jiang X Z， Jian J B.Two modified nonlinear conjugate gradient methods with disturbance fators for unconstrained optimization[J].Nonlinear Dyn,2014,77(1-2):387～394.

[13]王開榮,高佩婷.建立在 DY法上的兩類混合共軛梯度法[J].山東大學學報(理學版),2016,51(6):16～23.

[14] Barzilai J， Borwein J M.Two-point step size gradient methods[J].IMA J Numer Anal,1988, 8(1):141～148.

[15] Raydan M.The Barzilain and Borwein gradient method for the large scale unconstrained minimization problem[J].SIAM J Optim, 1997,7:26～33.

[16] Birgin E G， Martínez J M.A spectral conjugate gradient method for unconstrained optimization[J].Appl Math Optim,2001,43:117～128.

[17]汪丹戎,陳忠,張毅.求解無約束優(yōu)化問題的一種新的譜共軛梯度法[J].長江大學學報(自科版),2015,12(31)：6～8,40.

[18] 王華軍,王碩,曹義超.求解線性逆問題的譜共軛梯度法[J].廣西科學,2016,23(5):416～421,427.

[19] 林穗華.Wolfe線搜索下的修正FR譜共軛梯度法[J].山東大學學報(理學版),2017，52(4):6～12.

[20] Jian Jinbao, Chen Qian, Jiang Xianzhen,et al.A new spectral conjugate gradient method for large-scale unconstrained optimization[J].Optimization Methods and Software,2017,32(3):503～515.