一種下降的混合共軛梯度法

李文杰，周光輝，曹尹平

（淮北師范大學 數(shù)學科學學院，安徽 淮北 235000）

0 引言

共軛梯度法常用來求解非線性無約束優(yōu)化問題min{f(x)|x∈Rn}有效方法之一，f(x):x∈Rn→R 為一階連續(xù)可微函數(shù)，其一般迭代形式如下：

其中g(shù)k=?f(xk)為目標函數(shù)f的梯度函數(shù)，αk為步長，dk為搜索方向，組合系數(shù)βk為共軛梯度參數(shù)，βk取值不同，對應的共軛梯度法不同，著名的Hestenes-Stiefel（HS）、Fletcher-Reeves（FR）、Polak-Ribiére-Polyak（PRP）和Dai-Yuan（DY）公式共軛參數(shù)βk計算公式［1-4］如下：

在以上4個公式所對應的方法中，PRP方法和HS方法數(shù)值效果比較好，而FR方法和DY方法的理論收斂性比較好.

因此，許多研究者構(gòu)造兼具上述兩優(yōu)點的新共軛梯度法.例如，韋曾欣等［5］給出PRP 方法的一個變體參數(shù)βk：

該方法既滿足PRP方法的自動重啟、良好的數(shù)值性，又滿足充分下降性質(zhì)，有助于證明全局收斂性.姚勝偉［6］等人將這一思想推廣到HS方法，提出以下參數(shù)

最近，在文獻［6-8］的基礎(chǔ)上，文獻［9］提出一種混合算法：

于這些雜交方法，簡金寶等［10］介紹參數(shù)βk一種新的構(gòu)造，如下所示：

根據(jù)上述文章思想，結(jié)合文獻［11］提出的新參數(shù)：

產(chǎn)生一個新的共軛梯度法的猜想，并給出參數(shù)變量：

1 算法框架及其下降性

基于文獻［10-11］提出的混合共軛梯度法，構(gòu)造如下新算法框架.

算法1

步驟1 任取初始值x1∈Rn，?ε ＞0,?0＜δ ＜1,d1=-g1,令k:=1;

步驟2 檢驗終止條件.如果||gk||＜ε,則停止.否則，由某一個非精確線搜索求得步長αk；

步驟3 令xk+1=xk+αkdk，由式（8）計算返回步驟2.

以下引理指出，不論采用哪種線搜索程序，算法框架中的搜索方向都是下降的.

引理1設(shè)搜索方向dk由算法1產(chǎn)生，則

代入式（2）有

代入式（2）有

從引理1的證明過程中，很容易的得到公式（3）的另一重要性質(zhì).

引理2設(shè)步長αk滿足Wolfe線搜索條件，且步長{dk}由算法產(chǎn)生，對所有k≥1，都有

因此，引理2得證.

2 算法的全局收斂性

在這一部分中，證明在標準Wolfe線搜索條件下算法框架的全局收斂性.為實現(xiàn)這一目標，以下兩個基本假設(shè)條件［12］是必要的：

（H1）目標函數(shù)f(x)在水平集Λ={x∈Rn|f(x)≤f(x1)}上有下界，其中x1為算法初始點.

（H2）目標函數(shù)f(x)在水平集Λ 的一個鄰域U內(nèi)可微，且其梯度函數(shù)g(x)=?f(x)滿足Lipschitz條件，即存在常數(shù)L ＜0，使

下面的引理是著名的Zoutendijk條件［13］，在算法全局收斂性分析中起著重要作用.

引理3若假設(shè)（H1）（H2）成立，考慮迭代，搜索方向dk滿足，步長αk滿足標準Wolfe非精確線性搜索準則：

其中:δ和σ滿足0＜δ ＜σ ＜1.則

基于以上的討論，下面在非精確線性搜索條件下證明算法框架1是全局收斂的.

定理1設(shè)目標函數(shù)滿足假設(shè)（H1）（H2），{xk}由算法1產(chǎn)生，其中步長αk滿足Wolfe條件（14）（15），則有

3 數(shù)值實驗

本節(jié)測試算法1的數(shù)值結(jié)果，對于常用的無約束測試函數(shù)集文獻［14］中的算例進行模擬測試，并與參考文獻［11］中的方法進行數(shù)值比較.所有測試都在標準Wofle線搜索準則（14）（15）下完成，算法的測試環(huán)境為Matlab7.0，Win10操作系統(tǒng)，AMD Ryzen 5 3500U 2.10 GHz，8.00GB內(nèi)存下進行的.在運行過程中預設(shè)的參考值為σ=0.9，δ=0.001，μ=2.1，ε=10-5，在測試的過程中若出現(xiàn)‖g‖k ＜ε、迭代次數(shù)超過1 000這兩種情況之一，算法就會停止迭代，即該算法對此算例失效.在實驗中，對算法1與文獻［11］中的方法分別在1 000維，2 000維和3 000維3種維數(shù)下，對函數(shù)進行測試比對.測試函數(shù)問題見表1，將數(shù)值結(jié)果繪制成Dolan性能對比圖［15］（見圖1～6）.其中new代表的就是本文構(gòu)造的新混合共軛梯度法，JXZ代表的是文獻［11］中算法.

圖1 1 000維迭代次數(shù)對比

表1 測試函數(shù)

圖2 1 000維迭代時間對比

圖3 2 000維迭代次數(shù)對比

圖4 2 000維迭代時間對比

圖5 3 000維迭代次數(shù)對比

圖6 3 000維迭代時間對比

4 數(shù)值結(jié)果分析

通過Dolan性能圖發(fā)現(xiàn)，依據(jù)文中采取的測試函數(shù)在標準Wolfe線搜索下進行實驗，新混合共軛梯度法在迭代次數(shù)和時間上是優(yōu)于文獻［11］中共軛梯度法的.迭代時間的性能曲線在低維度時，時間上出現(xiàn)交叉，當維數(shù)增加后，新的混合共軛梯度法優(yōu)勢趨于明顯，進一步說明算法是可行性的.由此見，在相同條件下，新的混合共軛梯度法在求解大規(guī)模無約束優(yōu)化問題時可能有較好的效果.混合共軛梯度法是提高算法性能的一種有效方法.因此，在未來的研究工作中，可以找到更多的方法來選擇問題的參數(shù)，從而獲得性能更好的算法，使算法的效率最大化.