MWWP線搜索下的新共軛梯度法

曹尹平，周光輝

（淮北師范大學數學科學學院，安徽淮北 235000）

共軛梯度法具有計算簡便、編程簡單、儲存空間小和二次終止性等優點，是解決大規模無約束優化問題的較為常用的方法。一般迭代形式為

其中gk=?f(xk)為目標函數f的梯度函數，αk為步長因子，dk為搜索方向，βk為參數標量，不同的βk決定了不同的共軛梯度法。最早的共軛梯度法是由Fletcher和Reeves[1]在1964年提出，被稱為FR共軛梯度法，其參數標量,其中表示歐幾里得范數。其他經典的共軛梯度法還有HS 法[2]、PRP法[3-4]和DY法[5]，它們的參數標量分別為

PRP方法在數值結果上有較好的表現，因此，多年來諸多學者對PRP方法進行了廣泛深入地研究，得到了許多改進的PRP共軛梯度法[6-11]。Wei等[6]提出WYL法，參數標量為

WYL法保留了PRP方法的性質，且在一定的條件下證明了WYL方法的全局收斂性。為了確保每一步迭代都是充分下降的，文獻[10]對WYL公式進行修正，得到了DPRP公式及

其中參數μ＞1，并證明了DPRP公式產生的算法采用任何線搜索確定步長因子αk都是充分下降的，即

并且在標準Wolfe線搜索下使得DPRP方法全局收斂。

由共軛梯度法的表達形式可知，影響其變化的不僅有參數變量βk，還有步長因子αk。一般在較為經典的方法中，通常采用標準Wolfe 線搜索。2017 年，Yuan 等[12]提出了一種新型線搜索（modified weak Wolfe-Powell line search，簡稱MWWP型線搜索），形式如下：

由于DPRP方法對任何線搜索都是充分下降的，本文考慮DPRP方法在MWWP線搜索下是否具備全局收斂性，進而與標準Wolfe線搜索進行數值實驗對比，分析新算法的有效性，為解決大規模無約束優化問題提供更有效的方法。

1 算法框架及其基本性質

基于DPRP 方法中參數標量βk為式（4）與MWWP 線搜索（6）和（7），構建新算法框架（稱為NDPRP算法），步驟如下。

步驟1給定初值x1∈Rn，ε∈(0,1)，δ∈()，δ1∈(0,δ)，σ∈(δ,1)，μ＞1 且當k=1 時，d1=-g1。如果‖gk‖≤ε，則停止。

步驟2采用MWWP線搜索（6）和（7），計算步長αk。

步驟3令xk+1=xk+αkdk，如果‖gk+1‖≤ε，則停止。

步驟4利用與dk=-gk+βkdk-1迭代公式，計算下降方向。

步驟5令k=k+1，進入循環返回步驟2。

DPRP方法對任何線搜索都是充分下降的且有下列性質。

引理1[10]由（1）與（2）構成的一般迭代算法，其中βk由式（4）中的產生，μ＞1，則對于所有的k≥1，總成立

為了證明新算法下產生的共軛梯度法的全局收斂性，假設如下。

假設（H1）目標函數f(x)在水平集Ω={x∈Rn|f(x)≤f(x1)}上有下界，其中x1為初始點。

假設（H2）目標函數f(x)在水平集Ω的某一鄰域N內連續可微，梯度函數gk=?f(xk)滿足Lipschitz條件，即存在常數L＞0，使,?x,y∈N。

2 全局收斂性

Yuan等[12]提出MWWP型線搜索具有以下兩種形式：

形式②中δ1的取值由δ的取值范圍所決定，一般情況下②不具備全局收斂性，因此本文討論的重點是MWWP線搜索在形式①的條件下新算法的全局收斂性。

引理2考慮新算法滿足假設，序列{xk,αk,dk,gk}均由新算法產生，且MWWP線搜索滿足形式①，由此可得

顯然，搜索方向dk滿足充分下降條件（8），則有

證明由假設（H1），f(xk+αkdk)與f(xk)有下界，且由引理1 可知，δ1＜δ和成立。如果α→∞，則成立。再由上述假設與MWWP線搜索結合可得

對上述不等式進行求和，得

再由假設（H2）與MWWP線搜索形式①可得

定理1考慮新算法滿足假設，序列{xk,αk,dk,gk}均由新算法產生，且MWWP線搜索滿足形式①，則或者gk=0對于某個k成立，或者。

證明若gk=0對于某個k成立，則xk為點列的穩定點，定理成立。否則，采用反正法。假設定理不成立，則存在常數c＞0，對于?k都成立時，有，由式（2）得

由式（4）和引理1可知，

帶入式（12）中，可得

由于存在常數c＞0，使得對于?k都成立

這與引理2矛盾，則假設不成立，原命題成立。

3 數值實驗

為了檢測新算法的實際數值結果，我們對常用的無約束測試函數集（文獻[13]中的算例）進行模擬測試。新算法采用MWWP 線搜索進行測試，記為NDPRP，DPRP 算法采用標準Wolfe 線搜索準則進行測試，FR 算法和DY 算法均采用MWWP 線搜索進行測試。各算法的測試均在Matlab 7.0、Win 7.0 操作系統、Intel(R)Core(TM)I5-3210M CPU 2.50GHz 4.00GB 內存環境下進行。參數選取δ=0.4、δ1=0.2、σ=0.6、ε=10-5、μ=2，算法終止條件為‖gk‖＜ε或迭代次數超過1 000，維數取值為100、1 000、2 000。測試函數如表1所示。

表1 測試函數

實驗中，分別對3種不同維數下的迭代次數與迭代消耗CPU時間進行檢測。為了簡潔明了地反映數值結果，我們采用Dolan與Moré[14]提出的性能比較圖對本次實驗結果進行刻畫（如圖1～6）。即以求解測試函數極小點的時間（或迭代次數）為度量，將測試所消耗的計算時間（或迭代次數）與最短時間（或最少迭代次數）的比值作為算法的效率，記為r。為了比較各種算法的性能，設定，其中size{x∈X:r≤τ}為集合中元素的個數，X為測試函數的集合，n為所有測試函數的個數。P為r的分布函數，且P≤1。我們取P為縱軸，τ為橫軸，繪制曲線。某一算法的曲線位置越高，則表示該算法的數值實驗效果越好。

從圖1～6的分布明顯看出，NDPRP算法和DPRP算法均優于DY算法與FR算法。因此我們重點分析NDPRP與DPRP算法的區別，在100維和1 000維這兩種較低維數條件下，通過圖1～4可以看出，在迭代次數上NDPRP和DPRP算法幾乎重合；而在消耗CPU時間方面，NDPRP算法的優勢沒有明顯地表現出來。但從圖5、6發現，當維數超過2 000時，無論是迭代次數還是消耗CPU時間，NDPRP 算法的曲線都在DPRP的上方，可以認定NDPRP算法的優勢開始逐步體現出來。由此推測隨著維數的不斷提高，采用NDPRP算法去處理較大規模的無約束優化問題時，具有一定的競爭力，是一種值得研究的有效算法。

圖1 100維下不同算法迭代次數對比

圖2 100維下不同算法迭代消耗CPU時間對比

圖3 1 000維下不同算法迭代次數對比

圖4 1 000維下不同算法迭代消耗CPU時間對比

圖5 2 000維下不同算法迭代次數對比

圖6 2 000維下不同算法迭代消耗CPU時間對比

4 結語

通過上述數據的分析可知，NDPRP算法是一種有效可行的解決大規模無約束優化問題的方法。在未來的研究中，我們將該算法應用于解決一些實際的問題，如圖像去噪、信號處理等。