Wolfe 線搜索下具有充分下降性的混合共軛梯度法

房明磊，丁德鳳，王 敏

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

考慮無約束最優(yōu)化問題：

其中f:Rn→R是一個(gè)光滑的非線性函數(shù)，梯度函數(shù)g(x)存在。為方便起見，令gk=?f(xk)，Gk=?2f(xk)，yk-1=gk-gk-1，sk-1=xk-xk-1。共軛梯度法是求解上述無約束優(yōu)化問題的常見有效方法之一，它的迭代公式為：

xk+1=xk+αkdk，

(1)

(2)

其中，αk為步長，dk表示搜索方向，βk為標(biāo)量。不同的βk公式對(duì)應(yīng)不同的共軛梯度法，經(jīng)典的βk公式有Fletcher-Reeves[1]，Ploak-Ribiere-Polyak[2][3], Hestenes-Stiefel[4]等，具體形式如下：

(3)

許多文獻(xiàn)在這些已有方法的基礎(chǔ)上，對(duì)βk進(jìn)行了深入的研究，提出新的混合共軛梯度法。

烏彩英[5]結(jié)合牛頓法，提出改進(jìn)的PRP共軛梯度法：

(4)

該算法結(jié)合了牛頓法和PRP算法的優(yōu)勢(shì)，在Wolfe線搜索條件下滿足充分下降條件和全局收斂性。

Snezana S和Djordjevic[6]針對(duì)LS和FR方法，提出混合共軛梯度法：

(5)

其中，參數(shù)θk∈[0,1]。證明該混合共軛梯度法產(chǎn)生的搜索方向，不依賴于任何線搜索滿足著名的D-L共軛條件，同時(shí)在合適的條件下與牛頓方向一致，算法在強(qiáng)Wolfe線搜索條件下具有充分下降性和全局收斂性。

Sarra Delladji[7]采用PRP和HZ方法的凸組合方式提出混合共軛梯度法：

(6)

該算法在最優(yōu)解附近具有最速下降方向，在Wolfe線搜索下具有充分下降性和全局收斂性。

受上述文獻(xiàn)混合方式的啟發(fā)，基于文獻(xiàn)[5]考慮修正PRP共軛梯度法，提出如下的βk更新方式：

其中，0≤θ≤1，并證明了新方法在Wolfe條件下的充分下降性和全局收斂性。

1 新的混合共軛梯度算法

(7)

(8)

使用泰勒展開式，近似得到:

(9)

其中，0≤θ≤1。新提出的方法下降方向?yàn)?

(10)

顯然，當(dāng)θ=0時(shí)，(10)變?yōu)镻RP共軛梯度法，當(dāng)θ=1時(shí)，(10)還原為牛頓法。

算法：(NEW)

步驟1：取x1∈Rn，ε≥0，d1=-g1，k=1，如果‖g1‖≤ε，停止迭代;

步驟2：用Wolfe線搜索計(jì)算步長αk;

步驟3：令xk+1=xk+αkdk，gk+1=g(xk+1)，如果‖gk+1‖≤ε，停止迭代;

步驟5：令k=k+1，返回步驟2。

2 充分下降條件

(i)假設(shè)(H)在水平集L(x1)={x∈Rn:f(x)≤f(x1)}的一個(gè)鄰域U內(nèi)，函數(shù)f(x)連續(xù)可微，梯度函數(shù)g(x)滿足Lipschitz條件，即存在常數(shù)L>0使：

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

(11)

(ii)水平集L(x1)是緊集。

步長αk由Wolfe線搜索準(zhǔn)則得到：

(12)

(13)

其中,0≤ρ≤σ≤1，δk=(1-c)‖gk‖2/(Lk‖dk‖2)，αk=max{δk,δkρ,δkρ2,…}。

注：在文獻(xiàn)[8]中提出了Lk的一些估算方式，這里設(shè)L1>(1-c)L。

(14)

其中,c1=(1-θ)(L1-L(1-c))/L1。

當(dāng)k>1時(shí)，假設(shè)結(jié)論成立。由Wolfe線搜索

(15)

所以：

(16)

由假設(shè)條件(H)，Wolfe線搜索和PRP公式有：

(17)

因此：

(18)

性質(zhì)*[9]考慮一般的共軛梯度法，假設(shè)對(duì)所有的k≥1有：

在此假設(shè)下，此方法具有性質(zhì)*：存在常數(shù)b>1，λ>0，使得對(duì)所有的k均滿足|βk|≤b，

引理2 設(shè)目標(biāo)函數(shù)滿足假設(shè)條件H，如果存在常數(shù)γ>0，對(duì)所有的k≥1，使得‖gk‖≥γ均成立，則公式(2.4)具有性質(zhì)*。

證明：由L(x1)的緊密性，存在常數(shù)M1>0，使得對(duì)所有的x∈L(x1)均有‖xk‖≤M1。根據(jù)Wolfe線搜索的條件，得到：

(19)

(20)

(21)

3 算法的全局收斂性

(22)

此關(guān)系式稱為Zoutendijik條件。

定理1 設(shè)目標(biāo)函數(shù)滿足假設(shè)條件H，考慮公式(2.4)，其中αk滿足Wolfe搜索條件，則有：

‖gk‖≥ζk=1,2,3…，

根據(jù)定理1和引理3，得到：

(23)

因此，

(24)

從引理1可知，{f(xk)}是單調(diào)遞減數(shù)列，并由αk的選取方式有：

(25)

從而得到：

(26)

(27)

(28)

這與式(23)矛盾，故定理成立。

4 數(shù)值實(shí)驗(yàn)結(jié)果

本算法的實(shí)驗(yàn)問題選取文獻(xiàn)[11]中的部分測(cè)試函數(shù)集如表1所示，實(shí)驗(yàn)結(jié)果如表2所示，分別從迭代次數(shù)(NI)、梯度函數(shù)計(jì)算次數(shù)(NG)和目標(biāo)函數(shù)計(jì)算次數(shù)(NFF)與HS方法和PRP方法進(jìn)行比較，應(yīng)用文獻(xiàn)[12]提供的性能圖對(duì)實(shí)驗(yàn)效果進(jìn)行刻畫。測(cè)試環(huán)境為處理器11th Gen Intel(R) Core(TM) i5-11300H @ 3.10 GHz，RAM為16 G的計(jì)算機(jī)，軟件平臺(tái)是Matlab R2021a。實(shí)驗(yàn)選取的參數(shù)如下：ε=10-6，δ=0.02，σ=0.2。算法的停止準(zhǔn)則為以下兩者情形之一：(1) ‖gk‖<ε; (2)迭代次數(shù)超過1 000次。

表1 測(cè)試函數(shù)集

續(xù)表1

表2 實(shí)驗(yàn)結(jié)果

續(xù) 表2

5 結(jié)論

經(jīng)過與HS方法和PRP方法在NI、NG和NFF3方面的數(shù)據(jù)進(jìn)行比較，可以看出新提出方法在解決優(yōu)化測(cè)試問題是有效的。

圖1 HS法和PRP方法在NI方面的比較

圖2 HS法和PRP法在NG方面的比較

圖3 HS法和PRP法在NFF3方面的比較