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

1 共軛梯度法

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

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

(1)

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

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

xk+1=xk+αkdk

(2)

(3)

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

不同的βk選取方式對(duì)應(yīng)著不同的共軛梯度法，著名的βk的計(jì)算公式[1～7]有：

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

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

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

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

2 修正的DY譜共軛梯度法

(4)

(5)

其中，0≤μ1≤μ2。當(dāng)μ1=μ2=0時(shí)，該方法變?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 計(jì)算步長(zhǎng)αk滿足標(biāo)準(zhǔn)的Wolfe非精確線搜索準(zhǔn)則:

(6)

(7)

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

Step 5 置k=k+1，轉(zhuǎn)Step 2。

3 修正算法的全局收斂性

算法的全局收斂性證明以下列假設(shè)條件為基礎(chǔ)：

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

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

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

(8)

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

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

則：

(9)

故引理1得證。

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

(10)

證明由式(4)可知：

故引理2得證。

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

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

從而可得：

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

(11)

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

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

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

‖gk‖≥c

由式(3)移項(xiàng)得：

對(duì)等式兩端分別取模平方，再移項(xiàng)得：

(12)

(13)

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

從而：

因而有：

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

4 結(jié)語(yǔ)

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

[參考文獻(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]鄭小平，陳忠.一類(lèi)推廣的共軛梯度法及收斂性分析[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)，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]王開(kāi)榮,高佩婷.建立在 DY法上的兩類(lèi)混合共軛梯度法[J].山東大學(xué)學(xué)報(bào)(理學(xué)版),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]汪丹戎,陳忠,張毅.求解無(wú)約束優(yōu)化問(wèn)題的一種新的譜共軛梯度法[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自科版),2015,12(31)：6～8,40.

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

[19] 林穗華.Wolfe線搜索下的修正FR譜共軛梯度法[J].山東大學(xué)學(xué)報(bào)(理學(xué)版),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.