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

曹尹平，周光輝

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

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

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

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

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

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

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

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

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

1 算法框架及其基本性質(zhì)

基于DPRP 方法中參數(shù)標量βk為式（4）與MWWP 線搜索（6）和（7），構(gòu)建新算法框架（稱為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，進入循環(huán)返回步驟2。

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

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

為了證明新算法下產(chǎn)生的共軛梯度法的全局收斂性，假設(shè)如下。

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

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

2 全局收斂性

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

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

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

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

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

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

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

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

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

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

帶入式（12）中，可得

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

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

3 數(shù)值實驗

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

表1 測試函數(shù)

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

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

圖1 100維下不同算法迭代次數(shù)對比

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

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

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

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

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

4 結(jié)語

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