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

第四章共軛梯度法共軛方向法共輾方向法是無約束最優(yōu)化問題的一類重要算法。它一方面克服了最速下降法中，迭代點(diǎn)列呈鋸齒形前進(jìn)，收斂慢的缺點(diǎn)，同時又不像牛頓法中計算牛頓方向耗費(fèi)大量的工作量，尤其是共輾方向法具有所謂二次收斂性質(zhì)，即當(dāng)將其用于二次函數(shù)時，具有有限終止性質(zhì)。一、共軛方向定義4.1設(shè)G是nxn對稱正定矩陣，d1，d2是n維非零向量，若dTGd2=0 （4.1）則稱di，d2是G一共輾的。類似地，設(shè)dj,dm是Rn中一組非零向量。若dTGd=0（i中j） （4.2）則稱向量組d,,dm是G一共輾的。注：（1）當(dāng)G=?I?時，共軛性就變?yōu)檎恍?，故共輾是正交概念的推廣。（2）若dj,dmG一共輾，則它們必線性無關(guān)。???二、共軛方向法共輾方向法就是按照一組彼此共輾方向依次搜索。模式算法：1）給出初始點(diǎn)X，計算g=g（X），計算d，使dTg<0,k:=0（初始共輾方向）；0 0 0 0 002）計算a和x，使得f（x+ad）=minf（x+ad），令x=x+ad；3）計算dk+i，使dTGdj=0,j=0,1,,k，令k:=k+1,轉(zhuǎn)2）。???三、共軛方向法的基本定理共輾方向法最重要的性質(zhì)就是：當(dāng)算法用于正定二次函數(shù)時，可以在有限多次迭代后終止，得到最優(yōu)解（當(dāng)然要執(zhí)行精確一維搜索）。

定理4.2對于正定二次函數(shù)，共軛方向法至多經(jīng)過n步精確搜索終止；且對每個),都是fx)在線性流形Jxx=x+￡ad,Va1中的極小點(diǎn)。【0，J證明：首先證明對所有的i<n-1，都有g(shù)T+idj=0,j=0,1,,i(即每個迭代點(diǎn)處的梯度與以前的搜索方向均正交)事實(shí)上，由于目標(biāo)函數(shù)是二次函數(shù)，因而有g(shù)-g=G(x-x)=aGd1)當(dāng)j<i時，gTd=gTd+￡(g-g>di+1jj+1j k+1jjk=j+1=gTd+￡adTGd=0

j+1j kkjj=j+12)當(dāng)j=i時，由精確搜索性質(zhì)知：gTd=0綜上所述，有 gTd=0(j—0,1,i50)i+1j再證算法的有限終止結(jié)論。若有某個.gi+1-0(i<n-1)，則結(jié)論已知。若不然，那么由上面已證則必有： gTd―0(j—0,n-0)nj而由于d,,d是Rn的一組基，由此可得.g—00故至多經(jīng)過n次精確一維搜索即可獲得最優(yōu)解。0 n-1 n下面證明定理的后半部分。由于f(x)——xtGx+bTx+c2是正定二次函數(shù)，那么可以證明,t)―f(x0+lLtd)j=0是線性流形上的凸函數(shù)。事實(shí)上,3(3(t0,,t)―f(x0+^Ltd)j=0——(x+￡td)tG(x+￡td)+bT(x+Etd)+c2 0jj0jj 0jjj=0 j=0 j—0

=1Et2(dTGd)+2.x JJJJJ=0E[xTGd+bTd]t=1Et2(dTGd)+2.x JJJJJ=00JJJ20 0 0j=0,tj的凸函數(shù)。因而由d：Gd10(尸0,,0知0，,t)為1,tj的凸函數(shù)。因而min(1min(10,,t.)E必+19(t0,(J=0,ON(x+lLtd)Td=0(J=0, ,i)0JJJJ=0注意到：當(dāng)t=a.,(J=0,,i)時，Vi+1x+Etdi+1j=0而由定理前部分證明,在x,+1處有Vf(x+i)Tdj=gT+idj=0(J=0,,i)，故在(10,,t)=(a。，,a)處，①(10,,t)取得極小，.即x二x+Eadi+1 0 iJJ=0是f(x)在線性流形上的極小點(diǎn)?！?.2共軛梯度法上節(jié)一般地討論了共輾方向法，在那里n個共輔方向是預(yù)先給定的，而如何獲得這些共輾方向并為提及。本節(jié)討論一種重要的共輾方向法一一共輾梯度法。這種方法在迭代過程中通過對負(fù)梯度方向進(jìn)行適當(dāng)校正獲得共輾方向，故而稱之為共輾梯度法。一、共軛梯度的構(gòu)造(算法設(shè)計針對凸二次函數(shù))設(shè) f(x)=-2xtGx+bTx+c其中G為nxn正定矩陣，則g(x)=Gx+b。對二次函數(shù)總有 gki-gk=G(x^i-xk)=akGdk1)設(shè)X為初始點(diǎn)。首先取d=-g，令x=x+ad（a為精確步長因子）0 0 1 0 00 01)設(shè)X為初始點(diǎn)。首先取d=-g，令x=x+ad（a為精確步長因子）0 0 1 0 00 0則有：g巴=0（精確一維搜索性質(zhì)）。22今di=-gi+P0d0，適當(dāng)選擇爆，使d1Gd「0，gfGdp= 00dTGd0gT(g-g) gTg=―k—i 0—=i~idT(g-g)gTg0i0 00（從而得到d）

i由前一節(jié)共軛方向法的基本定理有:gTd=0,gTd=0,再由d0與di的構(gòu)造，還可得：gTg=0,gTg=02i 203)再令d2=-g2+P0d0+Pi4,適當(dāng)選擇P0,Pi使得d科=0（i=0」）,由此得:gT(g-g) gTgp=0,p=—2 2 i-=-2―20 i dT(g-g)gTgi2iii4)一般地，在第k次迭代中，令d=-g+tipd適當(dāng)選取P，使diGd=0(i1=0,,k-1),kk ii ikii=0???可得到 p=號Gi=g(gi+i_gi)(i=0,,k-1) (4.3)idrGddr(g-gi)同樣由前一節(jié)共軛方向的基本定理有： ??.gTd=0(i=0,,k-1),ki再由gi與dj的關(guān)系得： …gTg=0(i=0,,k-1)ki將(4.4)與(4.5)代入(4.3)得：當(dāng)i=0,,k-2時，p=0,igT(g—g)….gTg而 p=-k k 1—= k-k-k-idT(g-g)gTgk-1k k-1 k-1k-1共軛梯度法的迭代公式為：（dk為共軛方向,ak為最佳步長因子）對二次函數(shù)gTda=———k——；k drGdkk而對非二次函數(shù)，則采用精確一維搜索得到a。kTOC\o"1-5"\h\z共軛方向的修正公式為：dk1=-g^1+P丸 （4.6）其中，Pk由下面諸式之一計算：p=8k?J號門-（Crowder-Wolfe公式） （4.7）k d（gk「gjgTgP=k.k門 （Fletcher-Reeves公式） （4.8）k gTgkkgT（g—g）p=—1^—I k- （Polak-Ribiere-Polyak公式） （4.9）k gTgkkgTgp=—kj1k. （Dixon公式） （4.10）kdTgkk注：對二次函數(shù)而言，上述四個公式都是等價的。而且求得的搜索方向均為共軛方向；若對非二次函數(shù)，則將導(dǎo)出互不相同的算法，而且據(jù)此求出的搜索方向不再保證是共軛的。（事實(shí)上，此時不存在一個常值正定矩陣G，共軛的提法都已無意義）。二、共朝梯度法的性質(zhì)定理4.3對于正定二次函數(shù)，采用基于精確一維搜索的共軛梯度算法，必定經(jīng)過m<n步迭代后終止。且對1<i<m，下列關(guān)系式成立：1）drGd=0 （j=0,1,,i—1） （4.11）2）gTg=0 （j=0,1,：i—1） （4.12）ij3）dTg=-gTg … （4.13）4）[g°,g1,,g_]=[g0,Gg°,,Gig0] （4.14）5）[d0,d1,…,d.]=[g0,Gg」…,Gig0] （4.15）證明：先用歸納法證明（4.11）???（4.13）。對于i=1,容易驗(yàn)證（4.11）,（4.12）,4.13）成立?，F(xiàn)假設(shè)這些關(guān)系式對某個i<m成立，下面證明對于i+1,這些關(guān)系式仍然成立。事實(shí)上，對于二次函數(shù)，顯然有+1i++1i+1—x)=g+aGd(4.16)對上式左乘dT，并注意到ai是精確步長因子，得drGddrGd(drGddrGd(4.17)利用(4.16),(4.17),得gTg=gTg=gTg+adTGgi+1jij=gTg,~adrG(d-Pjd)(4.18)當(dāng)j=i當(dāng)j=i時，（4.18）成為=gTg一ii■gg^dTGd=0dTGdiiii當(dāng)j<i時，由歸納法假設(shè)可知gLgLgj=gTg—adTG(d-Pd)=0于是（4.12）得證。再由共軛梯度法的迭代公式及（4.17），有當(dāng)j=i時,當(dāng)j<i'時,又由于dTGd=-gTGd+PdT當(dāng)j=i時,當(dāng)j<i'時,又由于dTGd=-gTGd+PdTGd

i+1j i+1jiij由（4.12），山.17）及（4.8），（4.19）gjgj+1+PdTGda. ii成為(4.19)gTg gTgdTGd=-gi+1gi+1dTGd+3+13+1dTGd=0i+1i gTgiigTgiiii ii直接由歸納法假設(shè)知（4.19）為零，于是（4.11）得證。dTg=-gTg+pdTg =-gTgi+1i+1 i+1i+1 iii+1 i+1i+1于是（4.13）得證。下面利用歸納法證明（4.14）與（4.15）。當(dāng)i1=1時,由d0=-g0及g1容易看出:[g0，g1]二[g0cg0]再由d=-g及d=-g+pd=-g-pg，001 1 00 1 00易見:[d0,d1]=[g0,g1]=[g0Gg0]。故當(dāng)i=1時，（4.14）與（4.15）成立。假定（4.14）與（4.15）對i成立。下證結(jié)論對i+1也成立。由于g+1=g.+aGd,由于而從歸納法假設(shè)知g,de[g,Gg而從歸納法假設(shè)知g,de[g,Gg,,Gig]ii0 0故有g(shù)e[g,Gg,?；Gi+ig]i+1 0 0還可證明:g電[g,Gg，…,Gig]=[d,d,,d]i+1 0 0否則由g否則由ge[d,d,?,?d]及gTd=0(j=0,,i)(共軛方向法基本定理)i+1 01i i+1j則必有g(shù)=0（與算法結(jié)束前，不會出現(xiàn)g=0.矛盾）i+1i+1因此[g,g,,g]則必有g(shù)=0（與算法結(jié)束前，不會出現(xiàn)g=0.矛盾）i+1i+1因此[g,g,,g]=[g,Gg,0 1 i+1 0,Gi+1g0]再由立即有:[4，/i+1]=[g0，g1，，gi+1]=[g,Gg,,Gi+1g]。00定理證畢。注：1）上面定理中出現(xiàn)的這些生成子空間通稱為Krylov子空間;2）在共軛梯度法中，dk--8卜+1+P乩，若采用精確一維搜索,則P女不論采用哪種公式計算，都有g(shù)Td =-gTg+pgTd=-gTgk+1k+1 k+1k+1 kk+1k k+1k+1<0，即dk+1總是下降方向，若不采用精確一維搜索，則就不一定了;3）對Dixon公式,使用不精確搜索準(zhǔn)則降dj“gTdk，。e（0,1），能保證搜索方向總是下降的。事實(shí)上，由7 gTg1d=g——k+1-k+1dk+1 k+1 dTgkkkgTdgT+1dkgT+1dk+1=-%gk+11gTd

kkgg3dk?fgTdngTd<-gTdkk k+1kkk

gTdnk/k>一1(由gTd<0)，gTd kkkk由此即得 gT+1dk+1<0故dk+1為下降方向;4）Fletcher4）Fletcher—Reeves公式最為簡潔,使用得最多;5)共軛梯度算法用于非二次函數(shù)時，沒有有限終止性質(zhì)，一般經(jīng)誣次搜索后，就取一次負(fù)梯度方向，稱再開始。Polak-Ribiere-Polyak具有自動再開始的特點(diǎn)，事實(shí)上，當(dāng)算法改進(jìn)不大時，會出現(xiàn)8k+1xgk，這時用Polak-Ribiere-Polyak公式計算出的Pk-0，從而導(dǎo)致d^討?—g^討?！?.3共朝梯度法的收斂性由前面的討論已經(jīng)知道，當(dāng)共軛梯度算法用于正定二次函數(shù)時必定有限終止。本節(jié)研究將其用于一般非二次函數(shù)時的收斂性問題。一、共朝梯度法的總體收斂性定理4.4設(shè)水平集L=｛xf(x)<f(x)｝有界，f是Rn上具有一階連續(xù)偏導(dǎo)數(shù)的凸函數(shù)。｛x｝是0 k由Fletcher-Reeves共軛梯度算法產(chǎn)生的迭代點(diǎn)列。則1)｛f(x))為嚴(yán)格單調(diào)下降序列，且limf(x)存在。k ks k2)｛x｝的任意聚點(diǎn)都是最優(yōu)解，于是：limf(x)=minf(x)。k kfB k xeRn證明：在算法迭代過程中，由于每隔n次采用一次再開始措施。因而搜索方向要么是共軛梯度方向，要么是最速下降方向。但不管是哪種情形都有：gTd=—\|g||2<0 (采用嚴(yán)格一維搜索)kk k"因而｛f(x))單調(diào)下降，又由L有界，故｛f(x)］也有下界，因此limf(x)存在，記為f*。又由k k 7 kkfB｛f(xj｝單調(diào)下降，知｛xjuL，故｛xk｝是有界序列。設(shè)｛xJ1是｛xJ中的這樣的一個子列：從，出發(fā)按最速下降方向-gk得到xk+1。由｛xJ1有界,故存在收斂子列｛x｝，使limx=x*。kK2 kfBk使limx=x，使limx=x，, k+1kfBkeK3IQ又｛x｝也是有界點(diǎn)列，故存在子列｛x｝K2 K3f(x*)=f(x)=limf(x)=fkfBk下面用反證法證明Vf(x*)=0。若不然，設(shè)Vf(x*)豐0，則對充分小的a，有f(x*-aVf(x*))<f(x*)注意當(dāng)keK3時，f(x^+1)= f(x+a k d)= f( x— k gk)< f苫 ga>0

令k-8，則有 f(元)<f(x*—ag*)<f(x*)與(*)式矛盾，故必有Vf(x*)=0。再由f(x)是凸函數(shù)，即知x*是最優(yōu)解。因而有minf(x)=f(x*)=limf(x)xeRn kf8 "進(jìn)一步地，對點(diǎn)列｛x｝的任一極限點(diǎn)x，必存在｛x｝的子列IJ｛x｝，使得limx=x。k k kK0 k-8kkeK0進(jìn)而有 f(x)=f(limx)=limf(x)=f(x*),k, kk-8 k-8keK0這表明：x也是問題的最優(yōu)解。注：由這個定理的證明過程易見：上述收斂定理對其它幾種共軛梯度算法也是成立的。定理4.5假設(shè)水平集L=｛x\f(x)<f(x0)｝是有界集，Vf(x)在其上Lipschitz連續(xù)，則采用精確一維搜索的Crowder-Wolfe再開始共鈍梯度法產(chǎn)生的點(diǎn)列｛xk｝至少存在一個聚點(diǎn)是駐點(diǎn)。證明：與前一定理的證明類似，略。定理4.6(Polak-Ribbiere-Polyak算法的總體收斂性)設(shè)f(x)二階連續(xù)可微，水平集L=｛x\f(x)<f(xj｝有界。又設(shè)存在常數(shù)m>0，使得對xeL，有：m\y\<yTV2f(x)yVyeRn則采用精確一維搜索的P-R-P共鈍梯度算法產(chǎn)生的點(diǎn)列｛xJ收斂于f(x)的唯一極小點(diǎn)。證明：只要證明c0s0k—g證明：只要證明c0s0k—gTd k kdkgk即-gTd2Pkkg』ldk||即可。事實(shí)上，若cos0k一gTd成立。由第二章的定理2.7知，必有Vf(xk)-0,若x*是｛xk｝的極限點(diǎn)，由由f(x)的連續(xù)性，則有Vf(x*)=0，由f(x)的凸性，即知x*是極小點(diǎn)。再由f(x)在水平集L上一致凸，知｛x｝的極限點(diǎn)必唯一。否則設(shè)x是｛x｝的另一極限點(diǎn)，則kk也有Vf(x)=0。因此，0=(x*-x)t(Vf(x*)-Vf(x))=(x*-x)tV2f也)(x*-x)這與一致凸的假設(shè)矛盾，所以｛xJ只有唯一極限點(diǎn)。

可證：有界點(diǎn)列｛%｝若只有唯一極限點(diǎn)%*，則必有l(wèi)im%=%*。故｛%k｝收斂于于（%）的唯一極小點(diǎn)。下證:-gTd>p(1)由于采用了精確一維搜索故有因而（1）式等價于k>p可證：有界點(diǎn)列｛%｝若只有唯一極限點(diǎn)%*，則必有l(wèi)im%=%*。故｛%k｝收斂于于（%）的唯一極小點(diǎn)。下證:-gTd>p(1)由于采用了精確一維搜索故有因而（1）式等價于k>pIdkHk(2)得：其中再注意到，由（3）得又由L有界，因而由前述分析，grd -grd=aJ1drG(% +1akk-1 k-1k-1 k-10k-1 k-1 ,d)ddtak-1Gk-1gkPk-1grd k1k1—

kGk-1dk-1憶』2

k1叱Gk-1dk-（3）=J1G(% +ta d)dt。0 k-1 k-1k-1%)J= G%-1 0 -1OFt-1O) d 碎t Gd-1 -1 -1 -1 -1 -1gT(g,-g,,)—k k k-1-g-1gk-1=ak-1g；Gk111

.J2

k-1憶上

k-1gTG/-drGdk-1k-1k-1KJ陀1d/

mMJP故存在常數(shù)M>0，使得［GJ）y||<M||yPk-1同MdJ二"刈midJk-1MJ/目g」fk-Jidk-Jig』+》gJl=(1+竺)1gllkmk定理得證。上述總體收斂性定理均建立在精確一維搜索基礎(chǔ)之上。Al-Baali（1985）研究了采用不精確一維搜索的Fletcher-Reeves共軛梯度法。發(fā)現(xiàn)若采用Wolfe-Powell不精確一維搜索準(zhǔn)則，也有總體收斂性。10定理4.7若a由不精確一維搜索的Wolfe-Powell準(zhǔn)則產(chǎn)生，那么Fletcher-Reeves共鈍梯度算法具k體下降性質(zhì)：g巴定理4.7若a由不精確一維搜索的Wolfe-Powell準(zhǔn)則產(chǎn)生，那么Fletcher-Reeves共鈍梯度算法具k體下降性質(zhì)：g巴<°。證明：先用歸納法證明:j=ogTdT-)kJ4<—2+￡oj|2j=0i其中。e(0,)是W-P準(zhǔn)則中的。。當(dāng)上=0時，(*)成為等式，故結(jié)論成立。假設(shè)對任何人20,(*)式成立，現(xiàn)考慮左+1情形。gTdgII2k+1”=—1+PkgTdhlkgII2

k+lu=-1+2儲號"grd<Z+lk-agTdkkQTdstd,gTd—1+0-kk-?—^+4-V-1grd<Z+lk-agTdkkQTdstd,gTd—1+0-kk-?—^+4-V-1-O'-k:g/2gII2

k+1"再由歸納法假設(shè)，有Sgj=-1-c)2Lc>j?—1+oj=0J=0grdkk瓦『vgTd<hlhl似II2

k+111<一l—o <-l+c>2Lc>j=-2+Ec>jj=o-2aj<町41<-2+Ec>joJ=oJ=0利用已經(jīng)證明的(*)式，并注意到j(luò)=°j=o—2+