一個充分下降的修正PRP共軛梯度法

陳孔群 張雁 胡喬喬 陳碧玉

摘要：本文對PRP共軛梯度法參數公式進行修正得到一個新公式，以新公式為方向調控參數產生新的搜索方向，并得到一個新算法。不論采用何種線搜索條件產生步長，均可證明由算法產生的迭代方向每步均自動滿足充分下降條件，且證明了新算法的全局收斂性.最后的數值結果表明新算法是有效的。

關鍵詞：無約束優化；Wolfe非精確線搜索；共軛梯度法；充分下降；全局收斂

共軛梯度法是求解大規模優化問題最有效的方法之一。本文考慮用共軛梯度法解決如下無約束優化問題：

minx∈Rnf（x）

其中f：Rn→R為一階連續可微函數.共軛梯度法的迭代公式的一般形式為：

xk+1=xk+αkdk，（1）

dk=gk，k=1，

gk+βkdk1，k2，（2）

其中gk=

SymbolQC@ f（xk），αk是搜索步長，通常由非精確線搜索產生。βk為方向調控參數，dk為線搜索方向，通常由βk產生。通常由不同參數產生的搜索方向即稱為不同的共軛梯度法，著名的有代表性的共軛梯度法（統稱為經典共軛梯度法）包括HS方法，FR方法，PRP方法和DY方法，記yk=gkgk1，則它們的參數公式分別為：

βHSk=gTkyk1dTk1yk1，βFRk=‖gk‖2‖gk1‖2，βPRPk=gTkyk1‖gk1‖2，βDYk=‖gk‖2dTk1yk1。

近二十多年來，以上四個共軛梯度法的收斂性以及數值性質已被廣泛研究，并在此基礎上提出了很多理論性質和數值表現均優良的新型共軛梯度法，文獻[1]對FR方法和DY方法進行了改進，得到兩個新的βk公式：

βMFRk=‖gk‖2max‖gk1‖2，u|gTkdk1|，

βMDYk=‖gk‖2maxdTk1（gkgk1），u|gTkdk1|。

新算法均不依賴任何線搜索條件即可自動產生充分下降方向，在標準Wolfe線搜索條件下證明了算法所產生的點列全局收斂。文[2]將FR公式改進為

βNk=gTk（gk‖gk‖‖dk1‖dk1）‖gk1‖2，（3）

顯然由（3）式不難得到0

SymbolcB@ βNk

SymbolcB@ 2βFRk，基于文獻，[12]文[3]將（3）式修正為：

βJYJk=‖gk‖2（gTkdk1）2‖dk1‖2‖gk1‖2+ugTkdk1，（4）

借鑒文[1，2，3]的思想，我們將（4）式作進一步修正，得到如下新公式：

βCZHCk=‖gk‖2gTkdk1‖dk1‖‖gk1‖gTkgk1μ·max‖gk1‖2，gTkdk1μ>2（5）

本文第二部分由公式（5）產生新的搜索方向并建立新算法，并證明算法自動滿足充分下降條件；第三部分在常規假設和Wolfe線搜索條件證明算法是弱斂性的；第四部分用迭代時間和迭代次數報告算法的數值測試結果。

1算法CZHC及其性質

算法CZHC

步驟0取初始值x1∈Rn，ε>0，0<δ<σ<1，d1=g1，k：=k+1。

步驟1若‖gk‖<ε，則停止。否則，由某一個非精確線搜索求得步長αk。

步驟2令xk+1=xk+αkdk，由式（5）計算βCZHCk，dk+1=gk+βCZHCkdk，k：=k+1，返回步驟1。

下面證明由算法CZHC所產生的搜索方向自動滿足充分下降條件。

引理1對于任意的k1，設搜索方向dk由算法CZHC產生，則有gTkdk

SymbolcB@ 12μ‖gk‖2μ>2成立。

證明：用數學歸納法。當k=1時，gT1d1=‖g1‖2

SymbolcB@ （12μ）‖g1‖2，引理1結論成立。假設k1的情形，gTk1dk1

SymbolcB@ （12μ）‖gk1‖2成立。

下面分兩種情況證明當k的情形，引理1結論也成立。設gTk，dk1的夾角為θk，gTk，gk1的夾角為νk，則

gTkdk1=‖gk‖·‖dk1‖·cosθk，gTkgk1=‖gk‖·‖gk1‖cosνk。

由式（2）和（5），得

gTkdk=‖gTk‖2+gTkβCZHCkdk1=‖gk‖2+‖gk‖2（1cosθkcosνk）μmax{‖gk1‖2，|gTkdk1|}gTkdk1

1）當gTkdk1=0時，有

gTkdk=‖gk‖2+‖gk‖2（1cosθkcosνk）μmax{‖gk1‖2，|gTkdk1|}gTkdk1

=‖gk‖2

SymbolcB@ （12μ）‖gk‖2

2）當gTkdk1≠0時，有

gTkdk=‖gk‖2+‖gk‖2（1cosθkcosνk）μmax‖gk1‖2，|gTkdk1|gTkdk1

SymbolcB@ ‖gk‖2+2‖gk‖2μ|gTkdk1||gTkdk1|

=（12μ）‖gk‖2

綜上所述，對于k1，有gTkdk

SymbolcB@ （12μ）‖gk‖2成立。即引理1得證。

2算法的全局收斂性

本文將采用標準Wolfe非精確線搜索條件求步長，即αk滿足

fxk+αkdk

SymbolcB@ fxk+δαkgTkdk，（6）

gxk+αkdkTdkσgTkdk。（7）

為了證明新算法的全局收斂性，我們需要用到兩個基本假設條件。[4]

（H1）目標函數f（x）在水平集Λ={x∈Rn|f（x）

SymbolcB@ f（x1）}上有下界，其中x1為初始點。

（H2）目標函數f（x）在水平面集Λ的一個鄰域U內可微，且其梯度函數.g（x）=

SymbolQC@ f（x）滿足Lipschitz連續條件，即存在常數L>0，使‖g（x）g（y）‖

SymbolcB@ L‖xy‖，x，y∈U。

下面的引理是著名的Zoutendijk條件，在算法全局收斂性分析中起著十分重要的作用。

引理2。若假設（H1）和（H2）成立，考慮迭代，其中方向dk滿足gTkdk<0，αk滿足標準Wolfe非精確線性搜索準則（6）（7），則∑

SymboleB@ k=1（gTkdk）2‖dk‖2<

SymboleB@ 。特別地，若dk滿足充分下降條件，則有∑

SymboleB@ k=1‖gk‖4‖dk‖2<

SymboleB@

基于引理1，引理2，我們不難得到算法CZHC的全局收斂性結論。

定理1設目標函數滿足（H1）（H2），xk由算法CZHC產生，其中步長αk滿足弱Wolfe條件（6）（7），則有limk→

SymboleB@ inf‖gk‖=0。

證明：用反證法，假設定理1不成立。注意到‖gk‖>0，易知存在常數γ>0，使得‖gk‖2γ，k。由式（2）得dk+gk=βCZHCkdk1，移項再兩邊平方后得：

‖dk‖2=‖gk‖22βCZHCkgTkdk+（βCZHCk）2‖dk1‖2，（8）

又由式（5）可知

2βCZHCkgTkdk1

SymbolcB@ 2βCZHCk·gTkdk1

SymbolcB@ 4‖gk‖2μ和

βCZHCk

SymbolcB@ ‖gk‖2‖gk1‖2。

于是由（8）式得

‖dk‖2

SymbolcB@ 1+4μ‖gk‖2+‖gk‖4‖gk1‖4‖dk1‖2，

兩邊同時除以‖gk‖4有

‖dk‖2‖gk‖4

SymbolcB@ 1+4μ1‖gk‖2+‖dk1‖2‖gk1‖4。

又‖d1‖2=‖g1‖2，‖gk‖2>γ，于是有

‖dk‖2‖gk‖4

SymbolcB@ 1+4μ∑ki=11‖gi‖2

SymbolcB@ μ+4μγk，

因此‖gk‖4‖dk‖2μγ（μ+4）k，由此可知∑

SymboleB@ k=1‖gk‖4‖dk‖2=

SymboleB@ ，這與引理2矛盾，證畢。

3數值實驗

本節我們測試算法CZHC的數值效果，并與PRP+方法，AN方法和HZ方法進行比較。所有測試問題、算例和方法均采用弱Wolfe線搜索準則（6）（7）求步長，運行環境為Matlab2007，Pentium（R）DualCoreCPUT44001.90GHz2.43GB，測試問題部分取自無約束問題集CUTE，維數最大取200000維，有關參數選取如下：σ=0.9，δ=0.01，u=2.1，HZ方法的參數與原文一致。若‖gk‖<106或Itr>2000，則所測試算法運行終止，并記為“F”。

采用Dolan和More的性能圖對迭代次數及計算時間進行刻劃和報告.從圖1圖2可知，算法CZHC則明顯優于HZ方法、AN方法和PRP+方法，故可以說算法CZHC是有效的。

參考文獻：

[1]JiangXZ，JianJB.AsufficientdescentDaiYuantypenonlinearconjugategradientmethodforunconstrainedoptimizationproblems，NonlinearDyn.，2013，72，pp.101112.

[2]JiangXZ，JianJB.Twomodifiedconjugategradientmethodswithdisturbancefactorsforunconstrainedoptimization[J].NonlinearDynamics，2014，77：387397.

[3]簡金寶，尹江華，江羨珍.一個充分下降的有效共軛梯度法[J].計算數學，2015，37（4）：415424.

[4]江羨珍，簡金寶，馬國棟.具有充分下降性的兩個共軛梯度法.數學學報（中文版），2014，57（2）：365372.

基金項目：大學生創新訓練項目—201610606132

作者簡介：第一作者陳孔群，玉林師范學院數統學院2014級學生。