第四章 共軛梯度法

§ 共軛方向法

共軛方向法是無(wú)約束最優(yōu)化問(wèn)題的一類(lèi)重要算法。它一方面克服了最速下降法中，迭代點(diǎn)列呈鋸齒形前進(jìn)，收斂慢的缺點(diǎn)，同時(shí)又不像牛頓法中計(jì)算牛頓方向耗費(fèi)大量的工作量，尤其是共軛方向法具有所謂二次收斂性質(zhì)，即當(dāng)將其用于二次函數(shù)時(shí)，具有有限終止性質(zhì)。

一、共軛方向

定義 設(shè)G是n?n對(duì)稱(chēng)正定矩陣，d1，d2是n維非零向量，若

d1TGd2?0 （）

則稱(chēng)d1，d2是G－共軛的。類(lèi)似地，設(shè)d1,,dm是Rn中一組非零向量。若

diTGdj?0(i?j) （）

則稱(chēng)向量組d1,,dm是G－共軛的。

注：(1) 當(dāng)G?I時(shí)，共軛性就變?yōu)檎恍?，故共軛是正交概念的推廣。

(2) 若d1,

二、共軛方向法

共軛方向法就是按照一組彼此共軛方向依次搜索。 模式算法：

T1）給出初始點(diǎn)x0，計(jì)算g0?g(x0)，計(jì)算d0，使d0g0?0，k:?0 （初始共軛方向）；

,dmG－共軛，則它們必線性無(wú)關(guān)。

2）計(jì)算?k和xk?1，使得f(xk??kdk)?minf(xk??dk)，令xk?1?xk??kdk；

??03）計(jì)算dk?1，使dk?1Gdj?0，j?0,1,

三、共軛方向法的基本定理

T,k，令k:?k?1，轉(zhuǎn)2）。

共軛方向法最重要的性質(zhì)就是：當(dāng)算法用于正定二次函數(shù)時(shí)，可以在有限多次迭代后終止，得到最優(yōu)解（當(dāng)然要執(zhí)行精確一維搜索）。 1

-

定理 對(duì)于正定二次函數(shù)，共軛方向法至多經(jīng)過(guò)n步精確搜索終止；且對(duì)每個(gè)xi?1，都是f(x)在線

i????性流形?xx?x0???jdj,??j?中的極小點(diǎn)。

j?0????證明：首先證明對(duì)所有的i?n?1，都有

giT?1dj?0，j?0,1,,i（即每個(gè)迭代點(diǎn)處的梯度與以前的搜索方向均正交）

事實(shí)上，由于目標(biāo)函數(shù)是二次函數(shù)，因而有

gk?1?gk?G?xk?1?xk???kGdk

1）當(dāng)j?i時(shí)， gdj?gTi?1Tj?1dj?k?j?1i??gkik?1?gk?dj

T ?gTj?1dj?k?j?1??dTkGdj?0

2）當(dāng)j?i時(shí)，由精確搜索性質(zhì)知：

giT?1dj?0

綜上所述，有 gi?1dj?0 (j?0,1,T,i)。

再證算法的有限終止結(jié)論。若有某個(gè)gi?1?0（i?n?1），則結(jié)論已知。若不然，那么由上面已證則必有： gndj?0 (j?0,而由于d0,T,n?1)。

,dn?1是Rn的一組基，由此可得gn?0。故至多經(jīng)過(guò)n次精確一維搜索即可獲得最優(yōu)解。

下面證明定理的后半部分。由于

f(x)?1TxGx?bTx?c 2是正定二次函數(shù)，那么可以證明

?(t0,,ti)?f(x0??tjdj)

j?0i是線性流形上的凸函數(shù)。事實(shí)上，

?(t0,?,ti)?f(x0??tjdj)j?0iiii1(x0??tjdj)TG(x0??tjdj)?bT(x0??tjdj)?c2j?0j?0j?0

2

-

i1i2T1TT??tj(djGdj)??[x0Gdj?bTdj]tj?(x0Gx0?bTx0?c) 2j?02j?0由dTjGdj?0(j?0,,i)知?(t0,min,ti)為t0,,ti的凸函數(shù)。因而

(t0,,ti)?Ri?1?(t0,i,ti)????0 (j?0,?tj,i)

??f(x0?注意到：當(dāng)tj??j，(j?0,i?tdjj?0j)Tdj?0 (j?0,,i)

,i)時(shí)，

ix0??tjdj?x0???jdj?xi?1。

j?0j?0而由定理前部分證明，在xi?1處有

?f(xi?1)Tdj?giT?1dj?0(j?0,故在(t0,,i)，

,ti)?(?0,,?i)處，?(t0,,ti)取得極小，即

xi?1?x0???dij?0ij是f(x)在線性流形上的極小點(diǎn)。

§ 共軛梯度法

上節(jié)一般地討論了共軛方向法，在那里n個(gè)共軛方向是預(yù)先給定的，而如何獲得這些共軛方向并為提及。本節(jié)討論一種重要的共軛方向法——共軛梯度法。這種方法在迭代過(guò)程中通過(guò)對(duì)負(fù)梯度方向進(jìn)行適當(dāng)校正獲得共軛方向，故而稱(chēng)之為共軛梯度法。

一、共軛梯度的構(gòu)造 （算法設(shè)計(jì)針對(duì)凸二次函數(shù)）

設(shè) f(x)?其中G為n?n正定矩陣，則

1TxGx?bTx?c 2g(x)?Gx?b。

對(duì)二次函數(shù)總有 gk?1?gk?G?xk?1?xk???kGdk 3

-

1）設(shè)x0為初始點(diǎn)。首先取d0??g0，令x1?x0??0d0 （?0為精確步長(zhǎng)因子）

T則有：g1d0?0（精確一維搜索性質(zhì)）。

T2）令d1??g1??0d0，適當(dāng)選擇?0，使d1Gd0?0，

TTTg1Gd0g1(g1?g0)g1g得 ?0?T?T?T1 （從而得到d1）

d0Gd0d0(g1?g0)g0g0由前一節(jié)共軛方向法的基本定理有：

TTg2d1?0，g2d0?0，

再由d0與d1的構(gòu)造，還可得：

TTg2g1?0，g2g0?0

T3）再令d2??g2??0d0??1d1，適當(dāng)選擇?0，?1，使得d2Gdi?0 （i?0,1），由此得：

TTg2(g2?g1)g2g?0?0，?1?T?T2

d1(g2?g1)g1g1k?1i?04） 一般地，在第k次迭代中，令dk??gk???diiT 適當(dāng)選取?i，使dkGdi?0 （i?0,， ,k?1）

TTgkGdigk(g?g)可得到 ?i?T?Ti?1i（i?0,diGdidi(gi?1?gi),k?1） （）

同樣由前一節(jié)共軛方向的基本定理有：

Tgkdi?0（i?0,,k?1）， （）

再由gi與di的關(guān)系得：

Tgkgi?0 （i?0,,k?1） （）

將（）與（）代入（）得：當(dāng)i?0,,k?2時(shí)，?i?0，

TTgk(gk?gk?1)gkg而 ?k?1?T?Tk。

dk?1(gk?gk?1)gk?1gk?1共軛梯度法的迭代公式為：

xk?1?xk??kdk（dk為共軛方向，?k為最佳步長(zhǎng)因子）

對(duì)二次函數(shù) 4

-

Tgkd?k??Tk；

dkGdk而對(duì)非二次函數(shù)，則采用精確一維搜索得到?k。

共軛方向的修正公式為： dk?1??gk?1??kdk （） 其中，?k由下面諸式之一計(jì)算：

Tgk?1(gk?1?gk)1） ?k?T （Crowder-Wolfe公式） （） dk(gk?1?gk)Tgk1gk?12) ?k??T （Fletcher-Reeves公式） （）

gkgkTgk(gk?1?gk)3） ?k??1T （Polak-Ribiere-Polyak 公式） （）

gkgkTgk1gk?14） ?k???T （Dixon公式） （）

dkgk注： 對(duì)二次函數(shù)而言，上述四個(gè)公式都是等價(jià)的。而且求得的搜索方向均為共軛方向；若對(duì)非二次函數(shù)，則將導(dǎo)出互不相同的算法，而且據(jù)此求出的搜索方向不再保證是共軛的。（事實(shí)上，此時(shí)不存在一個(gè)常值正定矩陣G，共軛的提法都已無(wú)意義）。

二、共軛梯度法的性質(zhì)

定理 對(duì)于正定二次函數(shù)，采用基于精確一維搜索的共軛梯度算法，必定經(jīng)過(guò)m?n步迭代后終止。且對(duì)1?i?m，下列關(guān)系式成立：

1）diGdj?0 （j?0,1,2）gigj?0 （j?0,1,TT,i?1） （） ,i?1） （）

TT3）digi??gigi （）

4）[g0,g1,5）[d0,d1,,gi]?[g0,Gg0,,di]?[g0,Gg0,,Gig0] （） ,Gig0] （）

證明：先用歸納法證明（）～（）。對(duì)于i?1，容易驗(yàn)證（），（），）成立?，F(xiàn)假設(shè)這些關(guān)系式對(duì)某個(gè)i?m成立，下面證明對(duì)于i?1，這些關(guān)系式仍然成立。事實(shí)上，對(duì)于二次函數(shù)，顯然有 5

-

gi?1?gi?G(xi?1?xi)?gi??iGdi （）

對(duì)上式左乘di，并注意到?i是精確步長(zhǎng)因子，得

TgiTdigiTgi ?i??T??0 （）

diGdidiTGdi利用（），（），得

giT?1gj?giTgj??idiTGgj?giTgj??idiTG(dj??j?1dj?1) （）

當(dāng)j?i時(shí)，（）成為

giTgiTggj?ggi?TdiGdi?0

diGdiTi?1Ti當(dāng)j?i時(shí)，由歸納法假設(shè)可知

giT?1gj?giTgj??idiTG(dj??j?1dj?1)?0

于是（）得證。

再由共軛梯度法的迭代公式及（），有

diT?1Gdj??giT?1Gdj??idiTGdj?giT?1當(dāng)j?i時(shí)，由（），（）及（），（）成為

gj?gj?1?j??idiTGdj （）

giT?1gi?1TgiT?1gi?1TdGdi??TdiGdi?TdiGdi?0

gigigigiTi?1當(dāng)j?i時(shí)，直接由歸納法假設(shè)知（）為零，于是（）得證。

TTTT又由于 di?1gi?1??gi?1gi?1??idigi?1??gi?1gi?1

于是（）得證。

下面利用歸納法證明（）與（）。當(dāng)i?1時(shí)，由d0??g0及g1?g0??0Gd0?g0??0Gg0，容易看出： [g0,g1]?[g0,Gg0]

再由 d0??g0 及 d1??g1??0d0??g1??0g0，易見(jiàn)：

[d0,d1]?[g0,g1]?[g0,Gg0]。

故當(dāng)i?1時(shí)，（）與（）成立。假定（）與（）對(duì)i成立。下證結(jié)論對(duì)i?1也成立。

6

-

由于 gi?1?gi??iGdi， 而從歸納法假設(shè)知 gi,di?[g0,Gg0,故有 gi?1?[g0,Gg0,還可證明： gi?1?[g0,Gg0,否則由 gi?1?[d0,d1,,Gig0] ,Gi?1g0] ,Gig0]?[d0,d1,,di]

,di]及giT?1dj?0 (j?0,,i)（共軛方向法基本定理）

則必有 gi?1?0（與算法結(jié)束前，不會(huì)出現(xiàn)gi?1?0矛盾） 因此 [g0,g1,,gi?1]?[g0,Gg0,,Gi?1g0]

再由 di?1??gi?1??idi 立即有： [d0,定理證畢。

注：1）上面定理中出現(xiàn)的這些生成子空間通稱(chēng)為Krylov子空間；

2）在共軛梯度法中，dk?1??gk?1??kdk，若采用精確一維搜索，則?k不論采用哪種公式計(jì)

TTTT算，都有g(shù)k?1dk?1??gk?1gk?1??kgk?1dk??gk?1gk?1?0，即dk?1總是下降方向，若不采用

,di?1]?[g0,g1,,gi?1]?[g0,Gg0,,Gi?1g0] 。

精確一維搜索，則就不一定了；

TT3）對(duì)Dixon公式，使用不精確搜索準(zhǔn)則 gk?1dk???gkdk，??(0,1)，能保證搜索方向總是

下降的。事實(shí)上，由

Tgk1gk?1dk?1??gk?1??Tdk

dkgkT?gk??1dk??ggk?1?1?T?，

gkdk??Tk?1有 gTk?1k?1dTgkT?1dkdk?0）而 gd???gdk?gd??gdk?T， ??1（由gkgkdkTk?1kTkTk?1kTkT由此即得 gk?1dk?1?0

故dk?1為下降方向；

4）Fletcher－Reeves公式最為簡(jiǎn)潔，使用得最多； 7

-

5）共軛梯度算法用于非二次函數(shù)時(shí)，沒(méi)有有限終止性質(zhì)，一般經(jīng)過(guò)n次搜索后，就取一次負(fù)梯度方向，稱(chēng)再開(kāi)始。Polak-Ribiere-Polyak具有自動(dòng)再開(kāi)始的特點(diǎn)，事實(shí)上，當(dāng)算法改進(jìn)不大時(shí)，會(huì)出現(xiàn)gk?1?gk，這時(shí)用Polak-Ribiere-Polyak公式計(jì)算出的?k?0，從而導(dǎo)致dk?1??gk?1。

§4. 3 共軛梯度法的收斂性

由前面的討論已經(jīng)知道，當(dāng)共軛梯度算法用于正定二次函數(shù)時(shí)必定有限終止。本節(jié)研究將其用于一般非二次函數(shù)時(shí)的收斂性問(wèn)題。

一、共軛梯度法的總體收斂性

定理 設(shè)水平集L?xf(x)?f(x0)有界，f是Rn上具有一階連續(xù)偏導(dǎo)數(shù)的凸函數(shù)。{xk}是由Fletcher-Reeves共軛梯度算法產(chǎn)生的迭代點(diǎn)列。則

1）{f(xk)} 為嚴(yán)格單調(diào)下降序列，且limf(xk)存在。

k????2）{xk}的任意聚點(diǎn)都是最優(yōu)解，于是：limf(xk)?minf(x)。 nk??x?R證明：在算法迭代過(guò)程中，由于每隔n次采用一次再開(kāi)始措施。因而搜索方向要么是共軛梯度方向，要么是最速下降方向。但不管是哪種情形都有：

Tgkdk??gk2?0 （采用嚴(yán)格一維搜索）

*因而{f(xk)}單調(diào)下降，又由L有界，故{f(xk)}也有下界，因此limf(xk)存在，記為f。又由

k??{f(xk)}單調(diào)下降，知{xk}?L，故{xk}是有界序列。

設(shè){xk}K1是{xk}中的這樣的一個(gè)子列：從xk出發(fā)按最速下降方向?gk得到xk?1。由{xk}K1有界，故存在收斂子列{xk}K2，使limxk?x。

k??k?K2*又{xk?1}K2也是有界點(diǎn)列，故存在子列{xk?1}K3，使limxk?1?x，且

k??k?K3f(x*)?f(x)?limf(xk)?f* （*）

k??下面用反證法證明?f(x)?0。若不然，設(shè)?f(x)?0，則對(duì)充分小的?，有

**f(x*???f(x*))?f(x*)

注意當(dāng)k?K3時(shí)， f(xk?1)?f(xk??kdk)?f(xk??kgk)?f(xk??gk) ???0 8

-

令k??，則有 f(x)?f(x??g)?f(x)

*與（*）式矛盾，故必有?f(x)?0。再由f(x)是凸函數(shù)，即知x是最優(yōu)解。因而有

*****minf(x)?f(x)?limf(xk) nx?Rk???。 ?，必存在{xk}的子列{xk}K0，使得limxk?x進(jìn)一步地，對(duì)點(diǎn)列{xk}的任一極限點(diǎn)xk??k?K0?)?f(limxk)?limf(xk)?f(x) 進(jìn)而有 f(xk??k?K0k??*?也是問(wèn)題的最優(yōu)解。 這表明：x注：由這個(gè)定理的證明過(guò)程易見(jiàn)：上述收斂定理對(duì)其它幾種共軛梯度算法也是成立的。

定理 假設(shè)水平集L?xf(x)?f(x0)是有界集，?f(x)在其上Lipschitz連續(xù)，則采用精確一維搜索的Crowder-Wolfe再開(kāi)始共軛梯度法產(chǎn)生的點(diǎn)列{xk}至少存在一個(gè)聚點(diǎn)是駐點(diǎn)。 證明: 與前一定理的證明類(lèi)似，略。

定理 （Polak-Ribbiere-Polyak算法的總體收斂性）設(shè)f(x)二階連續(xù)可微，水平集

??L??xf(x)?f(x0)?有界。又設(shè)存在常數(shù)m?0，使得對(duì)x?L，有：

my?yT?2f(x)y ?y?Rn

則采用精確一維搜索的P-R-P共軛梯度算法產(chǎn)生的點(diǎn)列{xk}收斂于f(x)的唯一極小點(diǎn)。

T?gkdkT證明：只要證明cos?k???，即?gkdk??gkdk即可。事實(shí)上，若

gkdkT?gkdkcos?k??? （??0）

gkdk2成立。由第二章的定理知，必有?f(xk)?0，若x是{xk}的極限點(diǎn)，由?f(x)的連續(xù)性，則有

*?f(x*)?0，由f(x)的凸性，即知x*是極小點(diǎn)。

?是{xk}的另一極限點(diǎn)，則再由f(x)在水平集L上一致凸，知{xk}的極限點(diǎn)必唯一。否則設(shè)x?)?0。因此， 也有?f(x?)T(?f(x*)??f(x?))?(x*?x?)T?2f(?)(x*?x?) 0?(x*?x這與一致凸的假設(shè)矛盾，所以{xk}只有唯一極限點(diǎn)。 9

-

可證：有界點(diǎn)列{xk}若只有唯一極限點(diǎn)x，則必有l(wèi)imxk?x。故{xk}收斂于f(x)的唯一極小點(diǎn)。

k??**T下證： ?gkdk??gkdk （1）

由于采用了精確一維搜索，故有

Tgkdk??gk

2因而（1）式等價(jià)于

gk?? （2） dkT由 gkdk?1?gk?1dk?1??k?1T?10Tdk?1G(xk?1?t?k?1dk?1)dk?1dt

Tgk?1gkd得： ?k?1??T?1k?1?T （3）

dk?1Gk?1dk?1dk?1Gk?1dk?12其中 Gk?1??G(x01k?1?t?k?1dk?1)dt。

再注意到， gk?gk?1??f(xk)??f(xk?1)??G(x01k?1?t?k?1dk?1)?k?1dk?1dt??k?1Gk?1dk?1

TTgk(gk?gk?1)gkGk?1dk?1??有 ?k?1?， k?12Tgkggk?1?1k?1TgkGk?1dk?1Tdk?1Gk?1dk?1由（3）得 ?k?1??gkGk?1dk?1mdk?12

n又由L有界，故存在常數(shù)M?0，使得 G(x)y?My，?x?L，y?R 故 ?k?1?gkMdk?1mdk?12?Mgk

mdk?1因而 dk?gk?即

?k?1dk?1?gk?MMgk?(1?)gk mmgkM?(1?)?1?? dkm由前述分析，定理得證。

上述總體收斂性定理均建立在精確一維搜索基礎(chǔ)之上。Al-Baali（1985）研究了采用不精確一維搜索的Fletcher-Reeves共軛梯度法。發(fā)現(xiàn)若采用Wolfe-Powell不精確一維搜索準(zhǔn)則，也有總體收斂性。

10

-

定理 若?k由不精確一維搜索的Wolfe-Powell準(zhǔn)則產(chǎn)生，那么Fletcher-Reeves共軛梯度算法具體下

T降性質(zhì)：gkdk?0。

證明：先用歸納法證明：

????jj?0kTgkdkgk2??2???j （*）

j?0k其中??(0,)是W-P準(zhǔn)則中的?。

當(dāng)k?0時(shí)，（*）成為等式，故結(jié)論成立。假設(shè)對(duì)任何k?0，（*）式成立，現(xiàn)考慮k?1情形。 由

Tgk?1dk?112gk?1??1?2?Tgk?1(?gk?1??kdk)gk?1222??1??kTgk?1dkTgk?1dkgk?12

TTgk?1gk?1gk?1dkgkgk?1??1?gk2

TT及 gk?1dk???gkdk

TgkdkTgk?1dk?1Tgkdk有 ?1??再由歸納法假設(shè)，有

gk2?gk?12??1??gk2

?????1??????1??jjj?0j?0k?1kTgkdkgkk2

k?1j?0?Tgk?1dk?1gk?1j2??1??Tgkdkgk2??1??????2???j

jj?0k?1j?0即 ???j?0k?1?Tgk?1dk?1gk?12??2???j。

利用已經(jīng)證明的（*）式，并注意到

?????j?jj?0j?0kk?1 1??1?1?2???0 1??1??有 ?2???j??2?j?0T最后得 gkdk?0，證畢。

11

-

定理 設(shè)f(x)二階連續(xù)可微，水平集L?x?Rnf(x)?f(x0)有界。設(shè)?k由Wolfe-Powell準(zhǔn)則確定，那么Fletcher-Reeves共軛梯度算法產(chǎn)生的點(diǎn)列總體收斂，即有

??liminfgk?0. （1）

k??證明：由Wolfe-Powell準(zhǔn)則，及定理中（*）式得

TTgkdk?1???gk?1dk?1??2gk?1 1??22Tgkgkg又由 dk??gk??k?1dk?1， ?k?1?Tk?gk?1gk?1gk?1

得 dk2?gk?2T?2?k?1gkdk?1??k2?1dk?1

22?gk遞推可得 dk22?gk1??1??2??k2?1dk?1?()gk1??42??k2?1dk?1

221???()gk1??(?gjj?0k?2) （2）

下面用反證法證明（1）成立。若不然，則存在常數(shù)??0，使得對(duì)充分大的k，都有g(shù)k???0。 由gk在水平集L上有界，從（2）即有

dk2?c1k （c1為常數(shù)）

TTkgkgkdkgkdkgk1?2?gkj???(2??)?()由 cos?k?? ?2gkdkdk1??dkgkdkj?0gk1?2?22cos??()??k1??dkkk故級(jí)數(shù)

221?2?2?21?()??c2?

1??kc1kkk?cosk2?k發(fā)散。若設(shè)M為G(x)在L上的上界，

TT2則 gk?1dk?gkdk??kMdk再由Wolfe-Powell準(zhǔn)則

gk?1dk???gkdk （1）

TTT即 ?gkdk?gk?1dk???gkdk

TT故有

TTT ?gkdk?gk?1dk?gkdk??kMdk212

-

因而有

?k??1??Mdk2Tgkdk。

又由Wolfe-Powell準(zhǔn)則

Tfk?1?fk???kgkdk （2）

Tdk?(1??)?gk fk?1?fk??2M?d?k??(1??)?(1??)222??fk?gkcos2?k?fk??cos?k ?MM?2由（2）知{f(xk)}單調(diào)下降且有下界，故limf(xk)存在。再由

?(1??)M由此又推得

?2?0 及

?(1??)M?2cos2?k?fk?fk?1

?cosk2?k收斂，矛盾。從而定理結(jié)論成立。

13