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

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

1 共軛梯度法

考慮如下無約束非線性優化問題：

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

(1)

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

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

xk+1=xk+αkdk

(2)

(3)

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

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

其中， ‖·‖表示范數。

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

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

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

2 修正的DY譜共軛梯度法

(4)

(5)

其中，0≤μ1≤μ2。當μ1=μ2=0時，該方法變為傳統的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內連續可微，且其梯度函數g(x)滿足Lipschitz條件，即存在常數L>0，使得對?x,y∈Ω1，有：

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

(8)

并假定‖gk‖≠0，否則目標函數的穩定點已獲得，算法終止。

證明用數學歸納法證明。

則：

(9)

故引理1得證。

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

(10)

證明由式(4)可知：

故引理2得證。

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

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

從而可得：

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

(11)

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

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

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

‖gk‖≥c

由式(3)移項得：

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

(12)

(13)

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

從而：

因而有：

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

4 結語

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

[參考文獻]

[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]汪丹戎,陳忠,張毅.求解無約束優化問題的一種新的譜共軛梯度法[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.