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

房明磊，丁德鳳，王 敏

(安徽理工大學 數學與大數據學院，安徽 淮南 232001)

考慮無約束最優化問題：

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

xk+1=xk+αkdk，

(1)

(2)

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

(3)

許多文獻在這些已有方法的基礎上，對βk進行了深入的研究，提出新的混合共軛梯度法。

烏彩英[5]結合牛頓法，提出改進的PRP共軛梯度法：

(4)

該算法結合了牛頓法和PRP算法的優勢，在Wolfe線搜索條件下滿足充分下降條件和全局收斂性。

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

(5)

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

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

(6)

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

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

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

1 新的混合共軛梯度算法

(7)

(8)

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

(9)

其中，0≤θ≤1。新提出的方法下降方向為:

(10)

顯然，當θ=0時，(10)變為PRP共軛梯度法，當θ=1時，(10)還原為牛頓法。

算法：(NEW)

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

步驟2：用Wolfe線搜索計算步長αk;

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

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

2 充分下降條件

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

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

(11)

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

步長αk由Wolfe線搜索準則得到：

(12)

(13)

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

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

(14)

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

當k>1時，假設結論成立。由Wolfe線搜索

(15)

所以：

(16)

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

(17)

因此：

(18)

性質*[9]考慮一般的共軛梯度法，假設對所有的k≥1有：

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

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

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

(19)

(20)

(21)

3 算法的全局收斂性

(22)

此關系式稱為Zoutendijik條件。

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

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

根據定理1和引理3，得到：

(23)

因此，

(24)

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

(25)

從而得到：

(26)

(27)

(28)

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

4 數值實驗結果

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

表1 測試函數集

續表1

表2 實驗結果

續 表2

5 結論

經過與HS方法和PRP方法在NI、NG和NFF3方面的數據進行比較，可以看出新提出方法在解決優化測試問題是有效的。

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

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

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