最優(yōu)化理論與算法

1、第四章共軛梯度法§ 4.1 共軛方向法共軛方向法是無約束最優(yōu)化問題的一類重要算法。它一方面克服了最速下降法中，迭代點列呈 鋸齒形前進，收斂慢的缺點，同時又不像牛頓法中計算牛頓方向耗費大量的工作量，尤其是共軛方 向法具有所謂二次收斂性質，即當將其用于二次函數(shù)時，具有有限終止性質。一、共軛方向定義4.1 設G是n n對稱正定矩陣，d1，d2是n維非零向量，若d； Gd2 = 0（ 4.1 ）則稱a，d2是G 共軛的。類似地，設 dJHdm是Rn中一組非零向量。若dGdj =0（i = j）（4.2 ）則稱向量組djHdm是G 共軛的。注：（1）當G =1時，共軛性就變?yōu)檎恍?，故共軛是?/p>

2、交概念的推廣。（2）若djUmG 共軛，則它們必線性無關。二、共軛方向法共軛方向法就是按照一組彼此共軛方向依次搜索。模式算法：1）給出初始點x0，計算g0g（x0），計算d0，使dg0：0, k:=0（初始共軛方向）2） 計算:k和 Xk 1，使得 f （Xk ： kdk）二 min f（Xk ： dk），令 Xk1 二 Xk *kdk ；3）計算 dk 1，使 dGdj =0 , j =0,1川 l,k,令 kk 1，轉 2 ）。三、共軛方向法的基本定理共軛方向法最重要的性質就是：當算法用于正定二次函數(shù)時，可以在有限多次迭代后終止，得 到最優(yōu)解（當然要執(zhí)行精確一維搜索）。定理4.2 對于正定

3、二次函數(shù)，共軛方向法至多經過 n步精確搜索終止；且對每個x書，都是f(x)在i|線性流形gx x =滄+送otjdj, fa j中的極小點。ij蘭J證明：首先證明對所有的i _n _1，都有gTMj =0，j -0,1|,i (即每個迭代點處的梯度與以前的搜索方向均正交)事實上，由于目標函數(shù)是二次函數(shù)，因而有gk 1 - gk = G Xk 1 - Xk = ： kGdki1) 當 j <i 時，gi'dj =g：卅dj + 送(gk卑g"djk耳卅i=gj 1d j 亠-kdk Gdj = 0k=j卅2) 當j =i時，由精確搜索性質知：gi 1dj = 0綜上所述，

4、有gjdj =0 (j =0,1,111,i)。再證算法的有限終止結論。若有某個g“=0 ( ivn-1)，則結論已知。若不然，那么由上面已證則必有：g：dj =0 (j=0,HI, n-1)。而由于d0,IH,dn是Rn的一組基，由此可得gn =0。故至多經過n次精確一維搜索即可獲得最優(yōu)解。 下面證明定理的后半部分。由于1f (x)xTGx bTx c2是正定二次函數(shù)，那么可以證明imi,.) =f%' tjdj)j=0是線性流形上的凸函數(shù)。事實上，i(to,|l(,ti)二 f(X。' tjdj)j=01 iii=(人' tjdj)TG(x0' tjdj)b

5、T(x。' 射)c2 j =0j =0j =01 ii1t2(d：Gdj) ' x：Gdj bTdjtj ( xjGx。bTx。c)2 jj=02由 djTGdj0(j =0,|,i)知(to,川,ti)為t°，HI,ti的凸函數(shù)。因而min(to川|,tj0 (mii)(to，|時)令牛ctji=；f(xo 二 tjdj)Tdj =0 仃=0川|)j=0注意到：當 tj - j , (j =0,|l,i)時,iiX。+ 瓦 tjdj =x0 +瓦 ctjdj =x。j =0j =0而由定理前部分證明，在xi ,處有f (xi 1) d j - gi id j - 0

6、 (j =0,l|l,i)，故在(t。，川,tj =(：0,IH,：i)處，:(t°,川,tj取得極小，即ix十=x0 +E aidjj=0是f(x)在線性流形上的極小點。§ 4.2 共軛梯度法上節(jié)一般地討論了共軛方向法，在那里n個共軛方向是預先給定的，而如何獲得這些共軛方向并為提及。本節(jié)討論一種重要的共軛方向法一一共軛梯度法。這種方法在迭代過程中通過對負梯度方向進行適當校正獲得共軛方向，故而稱之為共軛梯度法。一、共軛梯度的構造(算法設計針對凸二次函數(shù))1設f (x)xTGx bTx c2其中G為n n正定矩陣，則g (x)二 Gx b。對二次函數(shù)總有gk gG Xk1 訣

7、 kGdk1)設Xo為初始點。首先取 do二-g°,令x X。：心odo （ ： o為精確步長因子）則有：g；dO=：o （精確一維搜索性質）。2)令 d1 = -g -odo，適當選擇'-o，使 dlGd。二 o，g1TGdo gT(g1-go)p =0 dTGdod】© -g。)Tg gTgo go（從而得到a）Tg?g2Tg1 g14）一般地，在第k次迭代中，令dkk -1= -gk 亠- idii 二0適當選取-i，使 djGdj-O（ i=0|l,k-1），可得到:gkGdi diTGdig】(g 1 -gJdiT(g i -gj(i =0川l,k -1)

8、(4.3)由前一節(jié)共軛方向法的基本定理有:再由d0與di的構造，還可得:gg =o.3）再令 d2 二-g2odo ，適當選擇：o， ，使得 d；Gdi = 0 （ i = 0,1），由此得:”o, gT(g2g1)d1 © 5)同樣由前一節(jié)共軛方向的基本定理有:gg =0 ( i = O,Hl,k -1)，(4.4)再由gi與di的關系得:g】gi =0 ( i =o川 I, k -1)(4.5)將（4.4 ）與（4.5 ）代入（4.3 ）得：當 i =0,|l,k -2 時，'-0，rgT(gk-gk_)gb ktdk4(gkgk4) gkXgk4共軛梯度法的迭代公式為X

9、k1=Xk *kdk（ dk為共軛方向， 為最佳步長因子）對二次函數(shù)gddS而對非二次函數(shù)，則采用精確一維搜索得到：k。共軛方向的修正公式為：dk勺二-gk .1 : kdk其中，-k由下面諸式之一計算：(4.6)gk 1(gk 1 gk)dk (gk 1 - gk)(Crowder-Wolfe 公式)(4.7)T2)：k = 亠1( Fletcher-Reeves 公式)gkgkgk 1© 1 - gQTgkgk(Polak-Ribiere-Polyak公式）T4)、二-( Dixon 公式)dkgk（4.8）（4.9）（4.10）注：對二次函數(shù)而言，上述四個公式都是等價的。而且求

10、得的搜索方向均為共軛方向；若對非二次（事實上，此時不存函數(shù)，則將導出互不相同的算法，而且據(jù)此求出的搜索方向不再保證是共軛的。在一個常值正定矩陣 G，共軛的提法都已無意義）二、共軛梯度法的性質定理4.3 對于正定二次函數(shù)，采用基于精確一維搜索的共軛梯度算法，必定經過m _ n步迭代后終止。且對1三i ：Sm，下列關系式成立：1）djGdj =0（ j =0,1,HI,i -1）（4.11 ）2） gTg0（ j =0,1l,i -1）（4.12）3） diTgi 二-ggi（4.13）4） 90,9,112二g0,Gg。,川Gg。（4.14）5） d°,d1,IILdi二g°

11、,Gg0,川Gg°（4.15 ） 證明：先用歸納法證明（4.11 ）（4.13 ）。對于i=1，容易驗證（4.11 ）, （4.12 ）, 4.13 ）成立?，F(xiàn)假設這些關系式對某個i ：m成立，下面證明對于 1，這些關系式仍然成立。事實上，對于二次函數(shù)，顯然有gi 1 F G（Xi 1 7）： iGdi（4.16 ）對上式左乘dT，并注意到冷是精確步長因子，得（4.17）giTdidTGdi利用（4.16），（4.17 ），得TTgi 1gj =gi gj:idiTGgj-giT gj -： idG（dj - jjdjj）（4.18）當j =i時，（4.18 ）成為Tgi 1gjT=

12、gi gi -,TT器 a®Tgigj當j <i時，由歸納法假設可知二 gg -： idG（dj - dj）=0于是（4.12 ）得證。再由共軛梯度法的迭代公式及（4.17），有dTQdj g1GdjdiTGdj 二 gT1 gjgj 1dTGdj（4.19）:j當 j =i 時，由（4.12），（4.17 ）及（4.8），（4.19 ）成為TTdiT1Gdi 二-gi Tgi 1 diTGdi gi ；gi 1 dGd廣 0gi gigi gi當j : i時，直接由歸納法假設知（4.19 ）為零，于是（4.11 ）得證。又由于dT.1gi -gT1gi：idTgi -gT1g

13、i !于是（4.13 ）得證。下面利用歸納法證明（4.14）與（4.15）。當 i =1 時，由d0二-g0及 g = g0 V0Gd0二g0-0Gg0，容易看出：go,9二go,Gg。再由 d° = -go 及 d -god -g - :ogo，易見:do,d1pgo,g1 =go,Ggo。故當i =1時，（4.14 ）與（4.15 ）成立。假定（4.14 ）與（4.15 ）對i成立。下證結論對i 1也成立。由于gi 1 = gi '-：iGdi ,而從歸納法假設知gM g0,Gg。,川 Gg。故有gi + eg0,Gg0j|,GH1g0還可證明：gi 1 go,Gg。,

14、IILG'g。二do,川,di否則由gi 1 do,a,川，dj及gT0 =0 （j =0,川，i）（共軛方向法基本定理）則必有gi 1 = 0 （與算法結束前，不會出現(xiàn) gi 1 =0矛盾）因此g°,g1,川 1g0,Gg0JH,Gi 1g。再由di 1 一 -gi 1idi立即有：d0,ll,di 1 =g°,g,ll|, gi 1 =g0,Gg0,|G 1g。定理證畢。注：1） 上面定理中出現(xiàn)的這些生成子空間通稱為Krylov子空間；2） 在共軛梯度法中，dk十=-gk r - kdk，若采用精確一維搜索，則'-k不論采用哪種公式計算，都有gid&qu

15、ot; = glgk卅十Xgdk = glgk卅，即總是下降方向，若不采用 精確一維搜索，則就不一定了；3） 對Dixon公式，使用不精確搜索準則gldk蘭Ygldk腫（0,1），能保證搜索方向總是 下降的。事實上，由Td _ ggk 心 1 ddk 1 一 一 gk i ,Tdkdk gk若t ,tL丄gk十dj有gk 卅dk = gk 卅gk+ 1+ t，-gkdk 一而9：趙|蘭一呵代=g打dk vg：dk= 八1 （由9代"），gkdk由此即得gk：0故dk 1為下降方向；4）Fletcher Reeves公式最為簡潔，使用得最多；5)共軛梯度算法用于非二次函數(shù)時，沒有有限終

16、止性質，一般經過n次搜索后，就取一次負梯度方向，稱再開始。Polak-Ribiere-Polyak具有自動再開始的特點，事實上，當算法改進不大時，會出現(xiàn)gk1 : gk，這時用Polak-Ribiere-Polyak公式計算出的' k ：、0 ,從而導致dk1 >_gk1。§ 4. 3共軛梯度法的收斂性由前面的討論已經知道，當共軛梯度算法用于正定二次函數(shù)時必定有限終止。本節(jié)研究將其用 于一般非二次函數(shù)時的收斂性問題。、共軛梯度法的總體收斂性定理4.4設水平集L f (x)乞f (x。)？有界，f是Rn上具有一階連續(xù)偏導數(shù)的凸函數(shù)。由Fletcher-Reeves 共軛梯

17、度算法產生的迭代點列。則1)f (xk)為嚴格單調下降序列，且lim f (Xk)存在。 k_；：2)xk的任意聚點都是最優(yōu)解，于是： lim f(Xk)二min f (x)。 X 申證明：在算法迭代過程中，由于每隔 n次采用一次再開始措施。因而搜索方向要么是共軛梯度方向,要么是最速下降方向。但不管是哪種情形都有:(采用嚴格一維搜索)因而f (Xk)單調下降，又由L有界，故 f(Xk)也有下界，因此Ijm f (Xk)存在，記為f。又由 f (Xk)單調下降，知XkL，故Xk是有界序列。設乂訃匕是Xk中的這樣的一個子列：從Xk出發(fā)按最速下降方向-gk得到Xk 1。由乂訃匕有界,故存在收斂子列x

18、kK2，使lim_ xk = x 。k- K2又xk 1 K也是有界點列，故存在子列 xk dK，使lim xk d = x，且 k秋3f(X)= f(x)=kmf (xQ(*)F面用反證法證明、f(x*) =0。若不然，設 f(x*) =0，則對充分小的，有f(X* 7 'f(X*) ： f (X*)f 啟 - ：kgk) - f 啟 - ：gk) 0注意當 k K3時，f (Xk 1) = f (Xk ： kdk)二令 k r ，則有 f (x)乞 f (x - ： g ) ： f (x )與(*)式矛盾，故必有if(x*)=O。再由f(x)是凸函數(shù)，即知x*是最優(yōu)解。因而有miR

19、nf(xf(x*kim f(xk)進一步地，對點列xk的任一極限點5?，必存在xk的子列xkKo，使得lim Xk = ?。*二 f(X )kEKo進而有f (奴)=f (lim xk)二 lim f (xk) k炭f這表明：?也是問題的最優(yōu)解。注：由這個定理的證明過程易見：上述收斂定理對其它幾種共軛梯度算法也是成立的。定理4.5假設水平集L =x f(x)蘭f(xo)是有界集，Vf(x)在其上Lipschitz連續(xù)，則采用精確一維搜索的Crowder-Wolfe再開始共軛梯度法產生的點列xj至少存在一個聚點是駐點。證明：與前一定理的證明類似，略。定理4.6 ( Polak-Ribbiere-

20、Polyak算法的總體收斂性)設f (x)二階連續(xù)可微，水平集L =x f (x)蘭f(X。)有界。又設存在常數(shù) m >0，使得對x乏L，有：2m y < yJ' 2f (x)y-yRn則采用精確一維搜索的P-R-P共軛梯度算法產生的點列 xk收斂于f (x)的唯一極小點。證明：只要證明cos<-g：dkF 即-gkdk -：? gk dk 即可。事實上，若COSk二 gkdk_成立。由第二章的定理2.7知，必有l(wèi)f(xk) > 0，若X*是xk的極限點，由lf(x)的連續(xù)性，則* *有I f(x)=0，由f (x)的凸性，即知x是極小點。再由f(x)在水平集L

21、上一致凸，知xj的極限點必唯一。否則設 ?是©訃的另一極限點，則也有"(幻=0。因此,0 二(x* -x)T (' f (x*)f (幼=(x* -x)T ' 2f ( )(x* -x)這與一致凸的假設矛盾，所以xk只有唯一極限點?？勺C：有界點列兀若只有唯一極限點X*，則必有l(wèi)im_xk =x*。故xk收斂于f（x）的唯一極小點。下證:_g：dk 尬 dk(i)由于采用了精確一維搜索，故有2 g：dk - - gk因而（1）式等價于gkdk(2)TT1 TgkdkA-gkdkA='kA ok Jdk J )dkjdt2得:(3)g爲dk gkjTTd

22、k jGk 二 d k AkJ其中10G(Xkt： kdk)dt。再注意到,1gk-'f (xQf(xk)=0G(xkjt-：ikdk)jkdkdt = - kGkdkg：(gk -gTgk 4gk 4g6d72，gk由（3）得g：Gkvdkddk 4Gk 4dk Jgk | Gk 4dk 4m dk又由L有界，故存在常數(shù) M0,使得G(x)y 乞M y , -x L, y Rn二 gk M |dk4m dk4m |gkm dk4因而dk -J"半)gk|lgk| 去(1+M)=pmlldkll由前述分析，定理得證。上述總體收斂性定理均建立在精確一維搜索基礎之上。Al-Baa

23、li （ 1985）研究了采用不精確一維搜索的Fletcher-Reeves 共軛梯度法。發(fā)現(xiàn)若采用Wolfe-Powell不精確一維搜索準則，也有總體收斂性。定理4.7若二k由不精確一維搜索的Wolfe-Powell準則產生，那么Fletcher-Reeves 共軛梯度算 法具體下降性質：gTdk ：0。證明：先用歸納法證明:kj =01其中三（0,）是W-P準則中的；。2(*)k _ 0 , （ *）式成立，現(xiàn)考慮k - 1情形。gk 1dk 1 _ gk 1( -gk 1 Mk)1 gk 1dkgk1gk.T一1TTgk 1gk 1 gk 1dk2llg|g“|-1 ： gkd2gk2.：.gk 1dk 1 2gk1g：dkgk2再由歸納法假設，有g®gk2k 1jj £-1g：dkkk 1_ _1 八；J = _2 7j =0j =0k 1Tk 1.j 遼 gk 山羅 _ _2 . a c j。j出gk 1j蟲利用已經證明的（*）式，并注意到k7j =0j =0k-2-j< -2 'j =011 一二最后得g：dk ”： 0，證畢。當k =0時，（*）成為等式，故結論成