新線搜索條件下的Dai-Yuan型共軛梯度法

曹尹平，周光輝

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

0 引言

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

其中：gk=?f(xk)為目標(biāo)函數(shù)f的梯度函數(shù)，αk為步長因子，dk為搜索方向，βk為參數(shù)標(biāo)量. 由式（1）可知，影響共軛梯度法的2個重要因素就是搜索方向dk與步長因子αk，而搜索方向dk的改變?nèi)Q于參數(shù)標(biāo)量βk的變化. 自從1964年Fletcher等提出非線性共軛梯度法之后，經(jīng)歷數(shù)十年的發(fā)展，諸多專家學(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ù)且采用精確線搜索確定步長因子αk時，上述經(jīng)典共軛梯度法可以相互等價. 但由于精確線搜索要求過于嚴(yán)格，計算量較大，且部分算法無法到達理想效果. 因此在實際應(yīng)用中常常采用非精確線搜索確定步長因子αk，其中較為常用的非精確線搜索有如下幾種：強（弱）Wolfe 線搜索［6-7］，Armijo 線搜索［8］，Grippo-Lucidi 線搜索［9］和Goldstein線搜索［10-11］等. 然而算法在考慮非精確線搜索的時候，往往需要考慮如下2個關(guān)鍵問題：1.非精確線搜索準(zhǔn)則所確立的步長因子αk是否存在；2.采用非精確線搜索準(zhǔn)則運算的共軛梯度法是否具有全局收斂性. 在實際的運算過程中，每種線搜索都有其獨特的優(yōu)點與不足，步長因子αk的確定需要一定的運算時間，所以線搜索的選擇會對算法的運算效率有所影響. 因此線搜索的選取也是判定算法優(yōu)劣的重要一步.

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

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

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

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

算法1

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

步驟2 采用MWWP線搜索（3）和（4），計算步長αk.

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

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

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

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

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

（H2）目標(biāo)函數(shù)f(x)在水平集Ω的某一領(lǐng)域N內(nèi)連續(xù)可微，梯度函數(shù)gk=?f(xk). 滿足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)生，且在滿足MWWP 線搜索滿足形式①的條件下，即成立，則關(guān)系式對于任意k都成立.

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

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

再由Dai-Yuan公式可知

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

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

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

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

對上述不等式進行求和得

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

可得

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

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

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

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

3 數(shù)值實驗

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

表1 測試函數(shù)

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

圖2 100維迭代時間對比

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

圖4 1 000維迭代時間對比

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

圖6 2 000維迭代時間對比

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

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