曹尹平，周光輝

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

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

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

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

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

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

并且在標(biāo)準(zhǔn)Wolfe線搜索下使得DPRP方法全局收斂。

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

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

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

基于DPRP 方法中參數(shù)標(biāo)量βk為式（4）與MWWP 線搜索（6）和（7），構(gòu)建新算法框架（稱為NDPRP算法），步驟如下。

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

步驟2采用MWWP線搜索（6）和（7），計(jì)算步長(zhǎng)αk。

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

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

步驟5令k=k+1，進(jìn)入循環(huán)返回步驟2。

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

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

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

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

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

2 全局收斂性

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

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

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

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

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

對(duì)上述不等式進(jìn)行求和，得

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

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

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

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

帶入式（12）中，可得

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

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

3 數(shù)值實(shí)驗(yàn)

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

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

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

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

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

圖2 100維下不同算法迭代消耗CPU時(shí)間對(duì)比

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

圖4 1 000維下不同算法迭代消耗CPU時(shí)間對(duì)比

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

圖6 2 000維下不同算法迭代消耗CPU時(shí)間對(duì)比

4 結(jié)語(yǔ)

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