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

1、百度文庫(kù)-讓每個(gè)人平等地提升自我第四章共鈍梯度法/ 共軻方向法共軻方向法是無(wú)約束最優(yōu)化問(wèn)題的一類重要算法。它一方面克服了最速下降法中，迭代點(diǎn)列呈 鋸齒形前進(jìn)，收斂慢的缺點(diǎn)，同時(shí)又不像牛頓法中計(jì)算牛頓方向耗費(fèi)大量的工作量，尤其是共軻方 向法具有所謂二次收斂性質(zhì)，即當(dāng)將其用于二次函數(shù)時(shí)，具有有限終止性質(zhì)。一、共軻方向 TOC o 1-5 h z 定義 設(shè)G是n n對(duì)稱正定矩陣，d1 , 2是n維非零向量，若d；Gd20()則稱d1, 2是6 共軻的。類似地，設(shè) dj/dm是Rn中一組非零向量。若dTGdj 0(i j)()則稱向量組dijdm是G 共軻的。注：(1)當(dāng)G I時(shí)，共軻性就變?yōu)檎恍裕?/p>

2、故共軻是正交概念的推廣。(2)若dij,dm G 共軻，則它們必線性無(wú)關(guān)。二、共軻方向法共軻方向法就是按照一組彼此共軻方向依次搜索。模式算法：1)給出初始點(diǎn)xo,計(jì)算go g(xo),計(jì)算do,使dTg。 0 , k : 0 (初始共軻方向)2)計(jì)算 k 和 Xki,使得 f(Xkkdk) mipf(Xkdk),令 Xki Xkkdk；3)計(jì)算 dk i,使 dTiGdj 0, j 0,1,|,k,令 k: k 1,轉(zhuǎn) 2)。,/三、共軻方向法的基本定理共軻方向法最重要的性質(zhì)就是：當(dāng)算法用于正定二次函數(shù)時(shí)，可以在有限多次迭代后終止，得 到最優(yōu)解(當(dāng)然要執(zhí)行精確一維搜索)。百度文庫(kù)-讓每個(gè)人平等

3、地提升自我定理 對(duì)于正定二次函數(shù)，共軻方向法至多經(jīng)過(guò)n步精確搜索終止；且對(duì)每個(gè)為1,都是f (x)在線性流形x x Xojd j, j中的極小點(diǎn)。、j 0證明：首先證明對(duì)所有的i n 1,都有g(shù)Tidj 0, j 0,1,|,i (即每個(gè)迭代點(diǎn)處的梯度與以前的搜索方向均正交)事實(shí)上，由于目標(biāo)函數(shù)是二次函數(shù)，因而有g(shù)k 1 gk G xk i xkkGdkT , T , iT ,i)當(dāng) j i 時(shí)，gi idjgj idjgk i gk djk j igT idjkdTGdj 0k j i2)當(dāng)j i時(shí)，由精確搜索性質(zhì)知：gTidj 0綜上所述，有g(shù)T1dj 0 (j 0,i1|,i)o再證算法

4、的有限終止結(jié)論。若有某個(gè)gi i 0 ( i n i),則結(jié)論已知。若不然，那么由上面已證則必有：g：dj 0(j 0,| | ,n i)。而由于d0,|,dn i是Rn的一組基，由此可得gn 0。故至多經(jīng)過(guò)n次精確一維搜索即可獲得最優(yōu)解。 下面證明定理的后半部分。由于f (x) xT Gx bTx c 2是正定二次函數(shù)，那么可以證明(t0, ,ti) f(xtjdj) TOC o 1-5 h z j 0/是線性流形上的凸函數(shù)。事實(shí)上，(tJ|,ti) f(xtjdj)j 0iiTiTi二(xtjdj) G(xtjdj) b (xtjdj) c2j 0j 0j 01 i 2 二-tj(djGd

5、j)2 j 0百度文庫(kù)-讓每個(gè)人平等地提升自我_ T _ . T . _1 T _T%Gdj b djtj (2 xoGxo b x c)由 d；Gdj0(j 0,|U，i)知(to,|,ti)為 to,|“,ti 的凸函數(shù)。因而(”限1 (toJl 卜 ti)% 0 (j Ml)f(xotjdj)Tdj 0 (j 0,|1i)j 01注意到：當(dāng)tjj , (j 0,“|,i)時(shí),xtjdjj 0 x0jd j xi 1 j 0而由定理前部分證明，在x 1處有f(x)Tdjg：1dj 0(j 01|,i),故在(t0，Mti)( 0,|, i)處，(t0,|,ti)取得極小，即x 1x0idj

6、j 0是f(x)在線性流形上的極小點(diǎn)。 共輾梯度法上節(jié)一般地討論了共軻方向法，在那里n個(gè)共軻方向是預(yù)先給定的，而如何獲得這些共軻方向并為提及。本節(jié)討論一種重要的共軻方向法一一共軻梯度法。這種方法在迭代過(guò)程中通過(guò)對(duì)負(fù)梯度 方向進(jìn)行適當(dāng)校正獲得共軻方向，故而稱之為共軻梯度法。一、共軻梯度的構(gòu)造(算法設(shè)計(jì)針對(duì)凸二次函數(shù))、一1 TT設(shè)f (x) x Gx b x c2其中G為n n正定矩陣，則g (x) Gx b。對(duì)二次函數(shù)總有g(shù)k 1gkG xk1kGdk百度文庫(kù)-讓每個(gè)人平等地提升自我1）設(shè)x0為初始點(diǎn)。首先取 d0 go,令X1X00 d0（ 0為精確步長(zhǎng)因子）則有：g1Td00 （精確一維搜

7、索性質(zhì)）2)令 d1 g10d0,適當(dāng)選擇 ，使 d：Gd00,g；Gd00 d0Gd0g1 (g1 g。)dT(gi g)T粵如（從而得到djg0 g0由前一節(jié)共軻方向法的基本定理有:gTd10,gTd00,再由d0與d/勺構(gòu)造，還可得:gTg10,3)再令 d2 g20d01d1,適當(dāng)選擇1,使得 d；Gdi 0 (i0,1）,由此得:0,1gT(g2 gi)d1T (g2gi)Tg2 g2Tg1 g1般地，在第k次迭代中,令dkkgk可得到gTGdi i dTGdig：(g 1同樣由前一節(jié)共軻方向的基本定理有：gTdi0 (iidigi)diT(gi 1 gi)0,|,k 1),再由gi

8、與di的關(guān)系得:gTgi 0 ( i 0,將（）與（）代入（）得：當(dāng) i 0,|,kgT(gk gk共物梯度法的迭代公式為對(duì)二次函數(shù)適當(dāng)選取使dTGdi0 (i 0,|,k 1),i 0,|,k 1)（）II2時(shí),1)k 1 dT 1(gk gk 1)OT gkgkT gk 1gk 1Xk 1 Xkkdk （dk為共軻方向，k為最佳步長(zhǎng)因子）百度文庫(kù)-讓每個(gè)人平等地提升自我gTdkdTGdk ；而對(duì)非二次函數(shù)，則采用精確一維搜索得到共軻方向的修正公式為：d其中,gk 1k由下面諸式之kdk1)Tgk1(gk1 gk) dkT(gk 1 gk)C Crowder-Wolfe 公式)2)Tgk 1

9、gk 1Tgkgk()0(Fletcher-Reeves 公式)3)gT1(gk1 gk)Tgkgk(Polak-Ribiere-Polyak 公式)0Tgk 1gk 1dTgk(Dixon 公式)對(duì)二次函數(shù)而言，上述四個(gè)公式都是等價(jià)的。而且求得的搜索方向均為共軻方向；若對(duì)非二次函數(shù)，則將導(dǎo)出互不相同的算法，而且據(jù)此求出的搜索方向不再保證是共軻的。在一個(gè)常值正定矩陣 G ,共軻的提法都已無(wú)意義）（事實(shí)上，此時(shí)不存二、共輾梯度法的性質(zhì)定理 對(duì)于正定二次函數(shù)， 采用基于精確一維搜索的共軻梯度算法，必定經(jīng)過(guò)m n步迭代后終止。且對(duì)1 i m,下列關(guān)系式成立：1) dGdj 0(j 0,1,|,i 1

10、)()2)gTgj 0( j0,1,|,i 1)()3)diTgigTgi/() HYPERLINK l bookmark92 o Current Document 4)g0,g1,|,gi g0,Gg0,(|,Gig0/()5)d0,d1,|,di g0,Gg0,|,Gig0/()證明：先用歸納法證明（）（）。對(duì)于i 1 ,容易驗(yàn)證（），（），）成立?，F(xiàn)假設(shè)這些關(guān)系式對(duì)某個(gè)i m成立，下面證明對(duì)于i 1 ,這些關(guān)系式仍然成立。事實(shí)上，對(duì)于二次函數(shù)，顯然有百度文庫(kù)-讓每個(gè)人平等地提升自我gi i gi G(Xi i x)giiGd對(duì)上式左乘diT,并注意到i是精確步長(zhǎng)因子，得利用(),(),得

11、Tgi gjgTdidiTGdiTgi gidiTGdiT gi igjidiTGgjT gi gjidTG(dji時(shí)，（）成為日T gi igjTgi giTgi gidiT GdidTGdij idi時(shí)，由歸納法假設(shè)可知T gi igjTgi gjdTi iG(djj idj i)0得證。再由共軻梯度法的迭代公式及（）dTiGdjgTiGdjidiTGdjgT1ggj iidTGdj當(dāng)j i時(shí),由（），（）及（），（）成為當(dāng)j i時(shí),又由于dTiGdiTgi遍iTgi gidTGdiTg4gLi diTGdi 0 gi gi直接由歸納法假設(shè)知（）0得證。是（）得證。dTigi iT gi

12、igiidTgi iT gi igi i卜面利用歸納法證明0 與二（）當(dāng)i 1時(shí),看出:goGg。再由d0g0 及 di gi0d0gi0g ，易見(jiàn):g由d0 g。及gig00Gg 0，容易do,di gO,gig0,Gg0。故當(dāng)i i時(shí)，（）與（）成立。假定（）與（）對(duì) i成立。下證結(jié)論對(duì)i i也成立。百度文庫(kù)-讓每個(gè)人平等地提升自我由于giiGdi ,而從歸納法假設(shè)知故有還可證明：否則由則必有因此再由立即有：定理證畢。gi,di g0,Gg0,|,Gig0gi i goGgoJ/Gi 4gi 1 go,Ggo, IGigo do, di,| ,digi 1 d0,dij”,di及 gTid

13、j 0 （j 0,|,i）（共軻方向法基本定理）gi i 0 （與算法結(jié)束前，不會(huì)出現(xiàn)gi i 0矛盾）g0,gi, |（,gi i g0,Gg0,|,Gi ig0di i gi i idid0, |di i g, gi J|, gi i g0,Gg0,|,Gi ig0 o注：i)上面定理中出現(xiàn)的這些生成子空間通稱為Krylov子空間;2)在共軻梯度法中， dk igkikdk ,若采用精確一維搜索，則k不論采用哪種公式計(jì)算，都有 gT idk i gTigk ikgTidkgT igk i 0,即dk總是下降方向，若不采用精確一維搜索，則就不一定了;gjdk,(0,i),能保證搜索方向總是3

14、)對(duì)Dixon公式，使用不精確搜索準(zhǔn)則gT idk下降的。事實(shí)上，由Tgk igk i .dk igk i.Tdkdk gkTTgk idkgk idk igk igk i i -r-，gkdkgT idkgTdkgTidkgTdk ,%哈 i （由 gTdk 。）,gkdk由此即得gT idk i 0故dk1為下降方向;4) FletcherReeves公式最為簡(jiǎn)潔，使用得最多;百度文庫(kù)-讓每個(gè)人平等地提升自我5)共軻梯度算法用于非二次函數(shù)時(shí)，沒(méi)有有限終止性質(zhì)，一般經(jīng)過(guò) n次搜索后，就取一次負(fù)梯 度方向，稱再開(kāi)始。Polak-Ribiere-Polyak具有自動(dòng)再開(kāi)始的特點(diǎn)，事實(shí)上，當(dāng)算法改

15、進(jìn)不大時(shí)，會(huì)出現(xiàn)gk 1 gk,這時(shí)用Polak-Ribiere-Polyak公式計(jì)算出的k 0 ,從而導(dǎo)致dk 1 gk1。 4. 3共軻梯度法的收斂性由前面的討論已經(jīng)知道，當(dāng)共軻梯度算法用于正定二次函數(shù)時(shí)必定有限終止。本節(jié)研究將其用 于一般非二次函數(shù)禰收斂性問(wèn)題。一、共軻梯度法的總體收斂性定理 設(shè)水平集L x f(x) f(x0)有界，f是Rn上具有一階連續(xù)偏導(dǎo)數(shù)的凸函數(shù)xk是由Fletcher-Reeves共軻梯度算法產(chǎn)生的迭代點(diǎn)列。則1) f (xk)為嚴(yán)格單調(diào)下降序列，且 lim f(xk)存在。k2) xk的任意聚點(diǎn)都是最優(yōu)解，于是： lim f (xk) min f(x)。kx

16、Rn證明：在算法迭代過(guò)程中，由于每隔n次采用一次再開(kāi)始措施。因而搜索方向要么是共軻梯度方向，要么是最速下降方向。但不管是哪種情形都有：gTdk|gk|2 0(采用嚴(yán)格一維搜索)因而f (xk)單調(diào)下降，又由L有界，故f(xk)也有下界，因此lim f(xk)存在，記為f 。又由 k f (xk)單調(diào)下降，知xkL ,故xk是有界序列。設(shè)xkK1是*1中的這樣的一個(gè)子列：從xk出發(fā)按最速下降方向gk得到xk1。由xkK1有界,故存在收斂子列xkK 使lim xk x。 TOC o 1-5 h z kZk K2又xk 1K2也是有界點(diǎn)列，故存在子列xk 1 K3 ,使lim xk 1 x ,且23

17、 k/k K3小 HYPERLINK l bookmark110 o Current Document f (x) f (x) lim f(xk) f(*)k k.一、一、一一I*. . .*. . .下面用反證法證明f(x ) 0。若不然，設(shè) f(x ) 0,則對(duì)充分小的 ，有_ * _ * _ *f(x f (x ) f (x )注意當(dāng)k K3時(shí),f (xk i)f (xkkdk)f (xkkgk) f (xkgk)百度文庫(kù)-讓每個(gè)人平等地提升自我令k ，則有f(x) f(x g ) f(x )與(*)式矛盾，故必有f (x ) 0。再由f(x)是凸函數(shù)，即知x是最優(yōu)解。因而有_ _ *m

18、in f (x) f (x )X R1lim f (xk) k進(jìn)一步地，對(duì)點(diǎn)列xk的任一極限點(diǎn)必存在Xk的子列XkK0,使得lim xk X。 kk Ko進(jìn)而有f (X) f (lim Xk)kk Kolim f(Xk) f (x ) k這表明：？也是問(wèn)題的最優(yōu)解。注：由這個(gè)定理的證明過(guò)程易見(jiàn)：上述收斂定理對(duì)其它幾種共軻梯度算法也是成立的定理假設(shè)水平集L x f(x) f(x)是有界集,f (x)在其上Lipschitz連續(xù)，則采用精確一維搜索的Crowder-Wolfe再開(kāi)始共軻梯度法產(chǎn)生的點(diǎn)列xj至少存在一個(gè)聚點(diǎn)是駐點(diǎn)。定理與前一定理的證明類似，略。(Polak-Ribbiere-Poly

19、ak算法的總體收斂性)設(shè)f(x)二階連續(xù)可微，水平集L x f (x)f (Xo)有界。又設(shè)存在常數(shù) m 0 ,使得對(duì)x L ,有:m|y|2yT 2f(x)y yRn則采用精確一維搜索的P-R-P共軻梯度算法產(chǎn)生的點(diǎn)列 xk收斂于f(x)的唯一極小點(diǎn)。證明：只要證明cos kkgTdkgk dk，即 gTdk|gk|dk|即可。事實(shí)上，若cos kgTdkgk dk0)成立。由第二章的定理知，必有f(xk)0,若* _ _ _ .X是Xk的極限點(diǎn)，由 f (x)的連續(xù)性，則有f (x ) 0,由f(x)的凸性，即知x是極小點(diǎn)。再由f (x)在水平集L上一致凸，知xj的極限點(diǎn)必唯一。否則設(shè)/

20、?是xk的另一極限點(diǎn)，則 也有 f(5?) 0。因此,z_ T 9 _*_0 (x X) ( f (x ) f (X) (x X) f ( )(x X)這與一致凸的假設(shè)矛盾，所以 xk只有唯一極限點(diǎn)。百度文庫(kù)-讓每個(gè)人平等地提升自我可證：有界點(diǎn)列Xk若只有唯一極限點(diǎn)*x，則必有kim人*X。故xk收斂于f(x)的唯一極小點(diǎn)。下證:gTdk由于采用了精確一維搜索,故有|gk|g因而(i)1gk dk得:gkA2gkgkdkgk 1dk 1gT1dkdT1G(xk1 t k其中dkGkdk2*1dk Gk 1dk 1Gkgk10G(Xk 1 tgk 1 f (xk)應(yīng) 1)dt 。1f(xk 1)

21、0G 1gT(gk gk 1)T gk & 1gk Gk 1dk 1g；(2)應(yīng) 1)dk 1dt(3)k 1dk 1)k 1dk 1dt k 1Gk 1dk 1由(3)得gTGk 1dk1dk 1Gk 1dk 1gk | Gk 1dk 1m|dk J|又由L有界，故存在常數(shù) M 0,使得|G(x)y| M | y| ,x L, y Rngk M lldk 1m |gk|m dk Jm dk 1因而dkgkdk1 gkM|gk m(1M) gk mllgkllIdkll(1M) 1m由前述分析，定理得證。上述總體收斂性定理均建立在精確一維搜索基礎(chǔ)之上。Al-Baali (1985)研究了采用不

22、精確一維搜索的Fletcher-Reeves共軻梯度法。發(fā)現(xiàn)若采用Wolfe-Powell不精確一維搜索準(zhǔn)則，也有總體收斂性。10百度文庫(kù)-讓每個(gè)人平等地提升自我定理若k由不精確一維搜索的Wolfe-Powell 準(zhǔn)則產(chǎn)生,那么Fletcher-Reeves共軻梯度算法具體下降性質(zhì)：g：dk 0。證明:先用歸納法證明:gTdk其中小1、口(0,2) 是w-p準(zhǔn)則中的0時(shí),(*)成為等式,故結(jié)論成立。假設(shè)對(duì)任何0,(*)式成立，現(xiàn)考慮k 1情形。gk 1dk 17T /gk i( gk 1gk12Tgkkd k )1dkT gk a 1gT 1dkgk2 gk1gTdkk 1dkgk2有g(shù)Tdkgk2gk 1dk 1gk1gTdk gk2再由歸納法假設(shè),1dk 12-gk1A,TgkTgkj 0利用已經(jīng)證明的*)最后得gTdk0,證畢。111dkgk 1gTdk2gk并注意到gkdkgk