數(shù)值最優(yōu)化課件

第五章無約束問題算法（III）——共軛梯度法共軛方向法的思路對于簡單的二次函數(shù)任給一個初始向量x(0),沿著方向e1=(1,0,···,0)T進行搜索,即求解下面問題由于因此注:此處的一維搜索中a1的范圍是整個實數(shù)集,即x(1)是函數(shù)在集合{x(0)+a1e1,a1∈R}中的極小點.共軛方向法的思路x(1)與x(0)唯一不同的是它們的第一個分量.其中x(1)的第一個分量與原問題最優(yōu)解–b的第一個分量一致,其余的分量未發(fā)生變化.下面再沿著方向e2=(0,1,0,···,0)T進行搜索,得到的x(2)的前兩個分量與最優(yōu)解–b

的前兩個分量一致,其余分量不變.顯然,x(2)是函數(shù)在集合{x(0)+a1e1+a2e2,a1,a2∈R}中的極小點.共軛方向法的思路因此,上述的迭代過程每一步在一個分量上達到最優(yōu),且每一步求得了函數(shù)在一個集合中的極小點,這種集合在迭代過程中逐漸擴大,迭代n步之后得到原問題的最優(yōu)解.將此過程進行下去有進行n步后有

x(k)是函數(shù)在{x(0)+a1e1+a2e2+···+akek,a1,a2···,ak∈R}中的極小點.共軛方向法的思路在三維情況下,上面的迭代過程可以用圖形來表示.x(0)x(1)x(2)x(3)xyzO=x*共軛方向法的思路上面的方法對一般的二次函數(shù)是否適用呢?考慮問題其中易見G是正定的,f(x)的極小點為(0,0)T.以x(0)=(-1,-1)T為初始點,在方向e1=(1,0)T上進行一維搜索.即求解問題易求得a1*=3,x(1)=x(0)+a1*e1=(2,-1)T.第一個分量沒有變?yōu)?,進一步沿e2=(0,1)T搜索顯然不能達到f(x)的極小點.共軛方向法的思路在空間Rn上,重新定義內(nèi)積與范數(shù):給定最優(yōu)化問題(其中G對稱正定)則共軛方向法的思路在Rn上,按照上面定義的內(nèi)積給出一組正交基p1,p2,···,pn,因此原問題等價于即p1,p2,···,pn線性無關(guān),且設(shè)問題的最優(yōu)解x*=-G-1b在這組基底下的表示為x*=u1p1+u2p2+···+unpn任取初始點x(0)=s1p1+s2p2+···+snpn,在方向p1上進行一維搜索,即求解問題共軛方向法的思路顯然,當(dāng)a1=u1–s1時,上面的函數(shù)取最小值,x(1)=u1p1+s2p2+···+snpn.即x(1)與最優(yōu)點在基底中第一個向量p1前的系數(shù)達到一致.x(1)是函數(shù)在集合{x(0)+a1p1,a1∈R}中的極小點.共軛方向法的思路最終x(n)=

u1p1+u2p2+···+unpn

=x*即迭代過程同樣在n步之后找到最優(yōu)點.因此,對二次函數(shù)我們可以找到n個方向(向量),對其依次進行一維搜索,最多n步可以找到函數(shù)的最優(yōu)點.類似的,再依次沿著p2,···,pk進行一維搜索,可以得到x(k)=

u1p1+···+uk

pk+sk+1pk+1+···+unpn

,x(k)是函數(shù)在{x(0)+a1p1+a2p2+···+akpk,a1,a2···,ak∈R}中的極小點.共軛方向法的思路定義設(shè)n維向量組p1,···,pk線性無關(guān),x(0)∈Rn,稱向量集合為由點x(0)與p1,p2,···,pk

生成的k維超平面.我們希望x(k)是k維超平面的極小點,于是x(n)是n維超平面(即整個Rn空間)的極小點.若k=1,上述集合表示以p1為方向向量,且過點x(0)的一條直線.超平面上極小點的判斷若函數(shù)f(x)連續(xù)可微,p1,p2,···,pk為一組線性無關(guān)的n維向量,x(0)∈Rn,若是f(x)在Hk上的極小點,則p1,p2,···,pk都不是下降方向,因此

–p1,–p2,···,–pk也不是下降方向,因此于是有超平面上極小點的判斷嚴格證明:Hk上的點可以表示為若是f(x)在Hk上的極小點.則定義其中因此超平面上極小點的判斷反之,若如果f(x)是嚴格凸函數(shù),對于則因此是f(x)在Hk上的唯一極小點.超平面上極小點的判斷引理

設(shè)f(x)為連續(xù)可微的嚴格凸函數(shù),又p1,p2,···,pk為一組線性無關(guān)的n維向量,x1∈Rn,則是f(x)在x1與p1,p2,···,pk所生成的k維超平面Hk上唯一極小點的充分必要條件是注:若k=n,易推出在xk+1的梯度為零向量.因此,這一引理是一常用定理(極小點梯度為0)的推廣.已知k個點與k個方向之后,令xk+1=xk+ak

pk,進行精確一維搜索,確定xk+1,再確定pk+1.共軛方向法(用于二次函數(shù))對于正定二次函數(shù),確定pk的準則是希望

xk+1是目標函數(shù)在k維超平面上的極小點.xn+1就是目標函數(shù)在整個空間的極小點.給定一個初始點x1,給出一個下降方向p1,令x2=x1+a1

p1,進行精確一維搜索,確定x2,再確定p2(方法待定).共軛向量對于f(x)=xTGx/2+bTx+c,有g(shù)(x)=Gx+b,因此gj+1-gj=G(xj+1-xj)=ajGpj,因此根據(jù)引理,左邊應(yīng)為零,于是搜索方向滿足性質(zhì)piTGpj=0(i≠j).共軛向量:設(shè)G為n階正定矩陣,p1,p2,···,pk為n維向量組,如果piTGpj=0(i≠j)則稱向量組p1,p2,···,pk關(guān)于G共軛.實際上是在新的內(nèi)積意義下,這是一組正交向量.共軛方向法(用于二次函數(shù))注:在前面討論思路時,根據(jù)方向的共軛性(正交性)得到xk+1是目標函數(shù)在k維超平面上的極小點(后面的定理將給出嚴格證明).根據(jù)上一頁的推導(dǎo),根據(jù)極小點可以推出共軛性(正交性),即若一種迭代方法每次求出的是二次函數(shù)在k維超平面上的極小點,則對應(yīng)的方向是共軛的.基本概念二次終止性如果一個算法經(jīng)過有限次迭代就得到正定二次函數(shù)的極小點,稱該算法具有二次終止性.共軛方向法是一種迭代方法,每次所取方向與前面的方向關(guān)于G共軛,然后進行精確一維搜索確定步長及下一步的迭代點.定理設(shè)G為n階正定矩陣,非零向量組

p1,p2,···,pk關(guān)于G共軛,則此向量組線性無關(guān).證明:設(shè)存在常數(shù)a1,a2,···,ak使得a1p1+a2p2+···+akpk=0,以piTG左乘上式,顯然有ai

piTGpi=0.又,G是正定矩陣,pi≠0,因此ai=0(i=1,2,···,k)于是p1,p2,···,pk線性無關(guān).共軛方向的性質(zhì)推論1設(shè)G為n階正定矩陣,非零向量組p1,p2,···,pn關(guān)于G共扼,則此向量組構(gòu)成Rn的一組基.推論2設(shè)G為n階正定矩陣,非零向量組p1,p2,···,pn關(guān)于G共扼,若向量v與p1,p2,···,pn

關(guān)于G共扼，則v=0.共軛方向的性質(zhì)共軛方向法(用于二次函數(shù))定理

設(shè)G是n階正定陣,向量組p1,p2,···,pk關(guān)于G共軛,對正定二次函數(shù)f(x)=xTGx/2+bTx+c由任意初始點x1開始,依次進行k次一維搜索,xi+1=xi+aipi(i=1,2,···,k)則(i)gTk+1pi=0

(i=1,2,···,k).(ii)xk+1是二次函數(shù)在k維超平面Hk上的極小點.推論

當(dāng)k=n時,xn+1為二次函數(shù)在Rn上的極小點.共軛方向法(用于二次函數(shù))證明要點:只要證明gTk+1pi=0.精確一維搜索共軛梯度法(共軛方向的形成)我們首先討論針對下面二次函數(shù)的共軛梯度法給定初始點x0,初始下降方向取為p0=-g0從x0出發(fā),沿方向p0進行一維搜索得x1.設(shè)p1是-g1與p0的線性組合p1=-g1+b0p0,p1與p0共軛,于是因此共軛梯度法(共軛方向的形成)假設(shè)已經(jīng)沿k個共軛方向p0,p1,···,pk-1逐次進行一維搜索得xk.若gk=g(xk)=0,則xk已是極小點,否則構(gòu)造下一個方向pk.令pk為-gk以及p0,p1,···,pk的線性組合.用pjTG(j=0,1,···,k-1)左乘上式因此共軛梯度法(共軛方向的形成)再根據(jù)二次函數(shù)的性質(zhì),有由于有因此由于xk是由點x0及向量p0,p1,···,pk-1得到的k維超平面上的極小點,因此gkTpj=0(j=0,1,···,k-1).由pj的構(gòu)造方式因此gkTgj=0(j=0,1,···,k-1).共軛梯度法(共軛方向的形成)因此gkTgj=0(j=0,1,···,k-1)根據(jù)得所以定理對正定二次函數(shù)由上面三式所確定共扼方向并采用精確一維搜索得到的共軛梯度法,在m(≤n)次迭代后可函數(shù)的極小點,并且對所有i(1≤i≤m)有共軛梯度法(用于二次函數(shù))其中FR算法(1)Flecher-Reeves公式為了能將上述方法用于其它函數(shù),我們必須消去系數(shù)中的G.所以(2)Polak-Ribiere-Polyak公式PRP算法由于gkTgk-1=0,所以有對于二次函數(shù),這兩個函數(shù)是等價的,但對于一般的函數(shù),根據(jù)這兩個公式的出的算法的計算效果有差異.FR算法中:注:對于這兩個算法,可以證明pkTgk=-gkTgk<0,因而都是下降算法.由g0=(-2,0)T≠0,故取p0=(2,0)T,從x0出發(fā),沿p0作一維搜索,即求minf(x0+ap0)=6a2-4a的極小點,得a0=1/3,于是x1=x0+a0p0=(2/3,0)T,g1=(0,-2/3)T,由FR公式得b0=g1Tg1/g0Tg0=1/9故p1=-g1+b0p0=(2/9,2/3)T.例

用FR共軛梯度法求解(x0=(0,0)T)共軛梯度法算例解注:此處不需求G.從x1出發(fā),沿p1作一維搜索,求解得a1=3/2,于是此時的極小點故此算例中,f(x)為二元的正定二次函數(shù),因此FR算法迭代兩次得到最優(yōu)點共軛梯度法算例例

用FR方法與PRP方法求解設(shè)初始點為x0=(0,0)T.解:由g0=(-2,0)T≠0,故取p0=(2,0)T,從x0出發(fā),沿p0作一維搜索,即求minf(x0+ap0)=1600a4+4a2-4a+1的極小點,得a0=0.080632,(精確一維搜索方法求得,e=10-5,)于是x1=x0+a0p0=(0.161264,0)T,g1=(0.000065,-5.201215)T.共軛梯度法算例p0=(2,0)T,x1=(0.161264,0)T,g1=(0.000065,-5.201215)T,由FR公式得b0=g1Tg1/g0Tg0=6.763160故p1=-g1+b0p0=(13.526254,5.201215)T.進一步可以以下的迭代,所得的結(jié)果(終止準則為||gk||<10-12,55步收斂)見下表.最終得到x*≈(1,1)T.FR方法計算結(jié)果從最后兩組數(shù)據(jù)可以看出,雖然函數(shù)值下降,但是迭代點離最優(yōu)點的距離卻有所增加.kxkf(xk)||g(xk)||0(0,0)T121(0.161264,0)T0.7711105.2012152(0.292861,0.050603)T0.6237037.53526110(1.006492,1.015405)T6.07e-41.05720420(1.000035,1.000074)T3.02e-90.00184330(1+1.31e-7,1+2.69e-7)T2.21e-142.89e-640(1+0.51e-9,1+1.03e-9)T2.79e-195.40e-950(1+2.10e-12,1+4.26e-12)T4.74e-242.16e-1154(1-1.14e-13,1-2.51e-13)T6.14e-269.63e-1255(1-1.42e-13,1-2.86e-13)T2.06e-265.55e-13對于PRP算法,計算過程類似.計算15步收斂,x*≈(1,1)T對于此例,PRP方法比FR方法收斂快.計算結(jié)果見下表.PRP方法計算結(jié)果kxkf(xk)||g