曹尹平，周光輝

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

0 引言

考慮大規(guī)模無(wú)約束優(yōu)化問(wèn)題，即min{f(x)|x∈Rn}，其中f(x):Rn→R 是一階連續(xù)的可微函數(shù). 在求解上述問(wèn)題時(shí)，共軛梯度法憑借其計(jì)算簡(jiǎn)便，收斂速度快，存儲(chǔ)數(shù)據(jù)少且具有二次終止性等優(yōu)點(diǎn)，被廣泛應(yīng)用于處理諸多最優(yōu)化問(wèn)題，也是目前較為常用的有效方法之一. 其迭代形式為：

其中：gk=?f(xk)為目標(biāo)函數(shù)f的梯度函數(shù)，αk為步長(zhǎng)因子，dk為搜索方向，βk為參數(shù)標(biāo)量. 由式（1）可知，影響共軛梯度法的2個(gè)重要因素就是搜索方向dk與步長(zhǎng)因子αk，而搜索方向dk的改變?nèi)Q于參數(shù)標(biāo)量βk的變化. 自從1964年Fletcher等提出非線性共軛梯度法之后，經(jīng)歷數(shù)十年的發(fā)展，諸多專(zhuān)家學(xué)者提出4種經(jīng)典共軛梯度法，在搜索方向dk上改變其參數(shù)標(biāo)量βk的多種變化形式［1-5］：

其中：yk-1=(gk-gk-1)，‖· ‖ 表示為歐幾里得范數(shù). 當(dāng)目標(biāo)函數(shù)f是嚴(yán)格凸二次函數(shù)且采用精確線搜索確定步長(zhǎng)因子αk時(shí)，上述經(jīng)典共軛梯度法可以相互等價(jià). 但由于精確線搜索要求過(guò)于嚴(yán)格，計(jì)算量較大，且部分算法無(wú)法到達(dá)理想效果. 因此在實(shí)際應(yīng)用中常常采用非精確線搜索確定步長(zhǎng)因子αk，其中較為常用的非精確線搜索有如下幾種：強(qiáng)（弱）Wolfe 線搜索［6-7］，Armijo 線搜索［8］，Grippo-Lucidi 線搜索［9］和Goldstein線搜索［10-11］等. 然而算法在考慮非精確線搜索的時(shí)候，往往需要考慮如下2個(gè)關(guān)鍵問(wèn)題：1.非精確線搜索準(zhǔn)則所確立的步長(zhǎng)因子αk是否存在；2.采用非精確線搜索準(zhǔn)則運(yùn)算的共軛梯度法是否具有全局收斂性. 在實(shí)際的運(yùn)算過(guò)程中，每種線搜索都有其獨(dú)特的優(yōu)點(diǎn)與不足，步長(zhǎng)因子αk的確定需要一定的運(yùn)算時(shí)間，所以線搜索的選擇會(huì)對(duì)算法的運(yùn)算效率有所影響. 因此線搜索的選取也是判定算法優(yōu)劣的重要一步.

2017年，Yuan等［12］提出一種新型非精確線搜索（modified weak Wolfe-Powell line search，簡(jiǎn)稱(chēng)MWWP型線搜索），MWWP型線搜索形式如下：

基于文獻(xiàn)［12］提供的一種新型線搜索，本文將新型線搜索與Dai-Yuan型共軛梯度法結(jié)合，構(gòu)建新算法并證明其全局收斂性. 與其他非精確線搜索進(jìn)行數(shù)值實(shí)驗(yàn)對(duì)比，說(shuō)明新型線搜索條件的Dai-Yuan 型共軛梯度法在求解無(wú)約束最優(yōu)化問(wèn)題時(shí)是有效的.

1 新線搜索下的Dai-Yuan共軛梯度法

基于MWWP型線搜索（3）和（4），構(gòu)造算法框架如下：

算法1

步驟 1 給定初值.且當(dāng)k=1 時(shí)d1=-g1. 如果‖gk‖≤ε，則停止.

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

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

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

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

為證明新型共軛梯度法的全局收斂性，需要下列假設(shè).

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

（H2）目標(biāo)函數(shù)f(x)在水平集Ω的某一領(lǐng)域N內(nèi)連續(xù)可微，梯度函數(shù)gk=?f(xk). 滿(mǎn)足Lipschitz 條件，即存在常數(shù)L>0 使‖g(x)-g(y) ‖≤L‖x-y‖,?x,y∈N.

2 全局收斂性

Yuan等［12］提出MWWP型線搜索具有以下2種形式：

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

引理1序列{xk,αk,dk,gk}均由算法1 產(chǎn)生，且在滿(mǎn)足MWWP 線搜索滿(mǎn)足形式①的條件下，即成立，則關(guān)系式對(duì)于任意k都成立.

證明當(dāng)k=1時(shí)，d1=-g1，則成立

假設(shè)當(dāng)n=k-1時(shí)，有成立，則當(dāng)n=k時(shí)有：

再由Dai-Yuan公式可知

由此可知，搜索方向是充分下降的.

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

證明由假設(shè)（H1），f(xk+αkdk) 與f(xk) 有下界，且δ1<δ和成立. 如果α→∞，則成立.

再由上述假設(shè)與MWWP線搜索結(jié)合可得

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

再由假設(shè)（H2）與MWWP線搜索形式①條件有

可得

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

證明若gk=0 對(duì)于某個(gè)k成立，則xk為點(diǎn)列的穩(wěn)定點(diǎn)，定理恒成立. 否則，采用反正法.

假設(shè)定理不成立，則 ‖gk‖>0，對(duì)于任意k都成立. 設(shè)常數(shù)c，‖gk‖>0，?k，由搜索方向迭代公式對(duì)上式變形得再兩端取模平方，移項(xiàng)得：

如果定理不成立，則存在常數(shù)c>0 使得‖gk‖>c對(duì)于所有k. 將其代入上述不等式中可得由此可知而上述求和與引理2中式（5）相矛盾. 由此可知假設(shè)不成立，定理成立.

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

為檢測(cè)算法的實(shí)際數(shù)值結(jié)果，對(duì)于常用的無(wú)約束測(cè)試函數(shù)集文獻(xiàn)［14］中的算例進(jìn)行模擬測(cè)試，并且與經(jīng)典Dai-Yuan 型共軛梯度法進(jìn)行數(shù)值比較. 經(jīng)典算法將采用標(biāo)準(zhǔn)Wolfe 線搜索準(zhǔn)則進(jìn)行測(cè)試，算法1采用MWWP 線搜索進(jìn)行測(cè)試. 算法的測(cè)試環(huán)境在Matlab 7.0，Win 7.0 操作系統(tǒng)，Intel（R）Core（TM）I5-3210M CPU 2.50GHz 4.00GB 內(nèi)存下進(jìn)行的. 其中算法1 中MWWP 線搜索參數(shù)選取如下：δ=0.49 ，δ1=0.24，σ=0.67.經(jīng)典算法中Wolfe線搜索參數(shù)選取如下：δ=0.49，σ=0.67，ε=10-5，算法終止的條件為‖gk‖<ε或迭代次數(shù)超過(guò)1 000. 當(dāng)終止條件是因?yàn)榈螖?shù)超過(guò)1 000時(shí)，則認(rèn)為該算法對(duì)此算例失效. 在實(shí)驗(yàn)中，對(duì)算法1與經(jīng)典Dai-Yuan型算法分別在100維，1 000維和2 000維3種維數(shù)下，對(duì)函數(shù)進(jìn)行測(cè)試比對(duì). 測(cè)試函數(shù)見(jiàn)表1，將數(shù)值結(jié)果繪制成Dolan 性能對(duì)比圖［15］（見(jiàn)圖1～圖6），其中Algorithm 1所代表的就是算法1，DY-method所代表的就是經(jīng)典Dai-Yuan型算法.

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

圖1 100維迭代次數(shù)對(duì)比

圖2 100維迭代時(shí)間對(duì)比

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

圖4 1 000維迭代時(shí)間對(duì)比

圖5 2 000維迭代次數(shù)對(duì)比

圖6 2 000維迭代時(shí)間對(duì)比

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

通過(guò)Dolan 性能圖可以發(fā)現(xiàn)，采用MWWP 線搜索的Dai-Yuan 型共軛梯度法在迭代次數(shù)上是優(yōu)于Wolfe線搜索下的Dai-Yuan型共軛梯度法的，而迭代時(shí)間的性能曲線在低維度時(shí)出現(xiàn)交叉，但是隨著維度的上升，MWWP線搜索的優(yōu)勢(shì)趨于明顯. 由此說(shuō)明，采用MWWP線搜索的Dai-Yuan 型共軛梯度法適合解決較大規(guī)模的無(wú)約束優(yōu)化問(wèn)題.