一個(gè)充分下降的修正PRP共軛梯度法

陳孔群 張雁 胡喬喬 陳碧玉

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

關(guān)鍵詞：無(wú)約束優(yōu)化；Wolfe非精確線搜索；共軛梯度法；充分下降；全局收斂

共軛梯度法是求解大規(guī)模優(yōu)化問題最有效的方法之一。本文考慮用共軛梯度法解決如下無(wú)約束優(yōu)化問題：

minx∈Rnf（x）

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

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

dk=gk，k=1，

gk+βkdk1，k2，（2）

其中g(shù)k=

SymbolQC@ f（xk），αk是搜索步長(zhǎng)，通常由非精確線搜索產(chǎn)生。βk為方向調(diào)控參數(shù)，dk為線搜索方向，通常由βk產(chǎn)生。通常由不同參數(shù)產(chǎn)生的搜索方向即稱為不同的共軛梯度法，著名的有代表性的共軛梯度法（統(tǒng)稱為經(jīng)典共軛梯度法）包括HS方法，F(xiàn)R方法，PRP方法和DY方法，記yk=gkgk1，則它們的參數(shù)公式分別為：

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

近二十多年來(lái)，以上四個(gè)共軛梯度法的收斂性以及數(shù)值性質(zhì)已被廣泛研究，并在此基礎(chǔ)上提出了很多理論性質(zhì)和數(shù)值表現(xiàn)均優(yōu)良的新型共軛梯度法，文獻(xiàn)[1]對(duì)FR方法和DY方法進(jìn)行了改進(jìn)，得到兩個(gè)新的βk公式：

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

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

新算法均不依賴任何線搜索條件即可自動(dòng)產(chǎn)生充分下降方向，在標(biāo)準(zhǔn)Wolfe線搜索條件下證明了算法所產(chǎn)生的點(diǎn)列全局收斂。文[2]將FR公式改進(jìn)為

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

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

SymbolcB@ βNk

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

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

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

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

本文第二部分由公式（5）產(chǎn)生新的搜索方向并建立新算法，并證明算法自動(dòng)滿足充分下降條件；第三部分在常規(guī)假設(shè)和Wolfe線搜索條件證明算法是弱斂性的；第四部分用迭代時(shí)間和迭代次數(shù)報(bào)告算法的數(shù)值測(cè)試結(jié)果。

1算法CZHC及其性質(zhì)

算法CZHC

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

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

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

下面證明由算法CZHC所產(chǎn)生的搜索方向自動(dòng)滿足充分下降條件。

引理1對(duì)于任意的k1，設(shè)搜索方向dk由算法CZHC產(chǎn)生，則有g(shù)Tkdk

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

證明：用數(shù)學(xué)歸納法。當(dāng)k=1時(shí)，gT1d1=‖g1‖2

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

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

下面分兩種情況證明當(dāng)k的情形，引理1結(jié)論也成立。設(shè)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）當(dāng)gTkdk1=0時(shí)，有

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

=‖gk‖2

SymbolcB@ （12μ）‖gk‖2

2）當(dāng)gTkdk1≠0時(shí)，有

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

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

=（12μ）‖gk‖2

綜上所述，對(duì)于k1，有g(shù)Tkdk

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

2算法的全局收斂性

本文將采用標(biāo)準(zhǔn)Wolfe非精確線搜索條件求步長(zhǎng)，即αk滿足

fxk+αkdk

SymbolcB@ fxk+δαkgTkdk，（6）

gxk+αkdkTdkσgTkdk。（7）

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

（H1）目標(biāo)函數(shù)f（x）在水平集Λ={x∈Rn|f（x）

SymbolcB@ f（x1）}上有下界，其中x1為初始點(diǎn)。

（H2）目標(biāo)函數(shù)f（x）在水平面集Λ的一個(gè)鄰域U內(nèi)可微，且其梯度函數(shù).g（x）=

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

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

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

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

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

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

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

SymboleB@

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

定理1設(shè)目標(biāo)函數(shù)滿足（H1）（H2），xk由算法CZHC產(chǎn)生，其中步長(zhǎng)αk滿足弱Wolfe條件（6）（7），則有l(wèi)imk→

SymboleB@ inf‖gk‖=0。

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

‖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，

兩邊同時(shí)除以‖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數(shù)值實(shí)驗(yàn)

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

采用Dolan和More的性能圖對(duì)迭代次數(shù)及計(jì)算時(shí)間進(jìn)行刻劃和報(bào)告.從圖1圖2可知，算法CZHC則明顯優(yōu)于HZ方法、AN方法和PRP+方法，故可以說算法CZHC是有效的。

參考文獻(xiàn)：

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

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

[3]簡(jiǎn)金寶，尹江華，江羨珍.一個(gè)充分下降的有效共軛梯度法[J].計(jì)算數(shù)學(xué)，2015，37（4）：415424.

[4]江羨珍，簡(jiǎn)金寶，馬國(guó)棟.具有充分下降性的兩個(gè)共軛梯度法.數(shù)學(xué)學(xué)報(bào)（中文版），2014，57（2）：365372.

基金項(xiàng)目：大學(xué)生創(chuàng)新訓(xùn)練項(xiàng)目—201610606132

作者簡(jiǎn)介：第一作者陳孔群，玉林師范學(xué)院數(shù)統(tǒng)學(xué)院2014級(jí)學(xué)生。