北郵最優(yōu)化 使用導(dǎo)數(shù)的最優(yōu)化方法ppt課件

1、帥天平帥天平北京郵電大學(xué)數(shù)學(xué)系北京郵電大學(xué)數(shù)學(xué)系:tpshuaigmail,Tel:62281308, Rm:主樓主樓81410， 使用導(dǎo)數(shù)的最優(yōu)化方法使用導(dǎo)數(shù)的最優(yōu)化方法最優(yōu)化理論與算法第十章 使用導(dǎo)數(shù)的最優(yōu)化方法最速下降法牛頓法共軛梯度法擬牛頓法信賴域法10.1最速下降法10.110.1最速下降法最速下降法 考慮無約束問題 min f(x), xRn (10.1.1)其中 f(x)具有一階連續(xù)偏導(dǎo)數(shù)。在處理這類問題時，一般策略是，希望從某一點出發(fā)，選擇一個目標函數(shù)值下降最快的方向，沿此方向搜索以期盡快達到極小點，基于這一思想，Cauchy于1847年提出了最速下降法。這是無約束最優(yōu)化中最簡

2、單的方法。10.1最速下降法1函數(shù)f(x)在點x處沿方向d的變化率可用方向?qū)?shù)表示，當函數(shù)可微時有，方向?qū)?shù)( , )( ) (1.2)TDf x df xd求函數(shù)f(x)在點x處下降最快的方向,歸結(jié)為求min ( ). 1 (1.3)Tf xdstd( )( )( ) ( )( ) (1.4)TTf xdf xdf xf xdf x ,Schwartz由不等式10.1最速下降法2由上式知.當( ) (1.5)( )f xdf x 時等號成立.故在點x處沿(1.5)所定義的方向變化率最小,即負梯度方向為最速下降方向.注意注意:在不同的尺度下最速下降方向是不同的在不同的尺度下最速下降方向是不同的

3、.10.1最速下降法3最速下降算法最速下降算法最速下降算法的迭代公式為(1)( )( )( )( )( )( )( ) (1.6),().kkkkkkkkkxxddxxdf x 其中是從出發(fā)的搜索方向,此處取在點的最速下降方向即 ( )( )( )( )( )( )0 ()() (1.7)minkkkkkkkkxdf xdf xd是從出發(fā)沿方向進行一維搜索的步長,即滿足10.1最速下降法4算法描述算法描述( )( )( )( )( )( )( )( )( )( )0(1)( )( )1,0,12,()3,()()4,:1,2min knkkkkkkkkkkkkkkkStepxEkStepdf

4、xStepdxdf xdf xdStepxxdkkStep給定初始點允許誤差置計算搜索方向若停止 否則 從出發(fā) 沿進行一維搜索 求使得 令置轉(zhuǎn)例1.1 用最速下降法求解下列問題2212(1)min ( )21(1,1) ,10Tf xxxx初點第一次迭代目標函數(shù)f(x)在點x處的梯度124( )2xf xx令搜索方向(1)(1)4()21642 51/10df xd (1)(1),xd1從出發(fā) 沿方向進行一維搜索 求步長即(1)(1)0(1)(1)22min ( )()14141212( )2(14 )(12 )f xdxd 令1( )16(14 )4(12 )0 5/18 (2)(1)(1)

5、11/94/9xxd在直線上的極小點第二次迭代(2)(2)(2)4/9()8/9451/109df xd (2)( )f xx在點處的最速下降方向為(2)(2),:xd從出發(fā) 沿方向進行一維搜索(2)(2)0(2)(2)22min ( )()1/94/9( 14 )/94/98/9(48 )/9216( )( 14 )(12 )8181f xdxd 令21664()( 14)(12)08181 5 /12(3)(2)(2)212127xxd 得到第三次迭代(3)(3)(3)24()127451/1027df xd (3)( )f xx在點處的最速下降方向為(3)(3),:xd從出發(fā) 沿方向進行

6、一維搜索(3)(3)0(3)(3)2222min ( )()1214242111227272784( )(14 )(12 )2727f xdxd 令2()0 5 /18此時(4)(3)(3)21/91224/9427243xxd(4)81()524310f x已經(jīng)滿足精度要求,得近似解124243x問題的最優(yōu)解為x*=(0.0)算法的收斂性算法的收斂性( )( )1.1 ( )( )0 ,.kkTheoremf xxf xxxx設(shè)是連續(xù)可微的實函數(shù),解集合=最速下降法產(chǎn)生的序列含于某個緊集,則序列的每個聚點證明證明:最速下降算法最速下降算法A可表示為合成映射可表示為合成映射A=MD其中D(x)

7、=(x,-f(x),是En En En的映射.每給定一點x,經(jīng)算法D作用,得到點x和在x處的負梯度(從x出發(fā)的方向d).算法M是En En En 映射.每給定一點x及方向d=-f(x),經(jīng)M作用,即一維搜索,得到一個新點,在這一點,與前面的迭代點相比,具有較小的目標函數(shù)值,根據(jù)Th1.1,當 f(x) 0時,M是閉映射.由于f(x)是連續(xù)可微實函數(shù), 故D連續(xù),據(jù)Th8.1.1推論2,A在x(f(x) 0)處是閉的. 其次,當x時, d=-f(x) 0,那么f(x) T d0,因而對于yA(x),有f(y)0,滿足1,且對每一個成立定:(1理)2) .kxxx則牛頓法產(chǎn)生的序列收斂于10.2.

8、2 局部收斂性10.2 牛頓法證明:根據(jù)(10.2.2)，牛頓算法映射定義為21( )( )( )A xxf xf x (a) ,( )-xxx x 定義解集合令函數(shù)=下證(x) 是關(guān)于解集合和算法A的下降函數(shù).2121212A( )0,( )( )()( ) ( )( )( ) ( )( )( )() (b)f xyxxf xf xxxxf xf xxf f xxf xf x xx 根據(jù)算法 的定義及的假設(shè) 有,( ).xXxxyA x令且又令10.2 牛頓法于是可得2121 2( )( )( )( )() (c)yxf xxf xf x xxk kxxxx ( )( )( ),.Akkcy

9、XxXXXxx由可知故迭代產(chǎn)生的序列根據(jù)定義知 是緊集,故迭代產(chǎn)生的序列含于緊集.此外,算法映射 在緊集 上是閉的.綜上,迭代產(chǎn)生的序列必收斂于從而(x) 是關(guān)于解集合和算法A的下降函數(shù)10.2 牛頓法2202()(),*( *)0,Hesse( *)*,Hesse( )( )Lipschitz,L0,( )( ),k10 2 2*. nnkfCRxf xf xxxG xf xx yRG xG yL xyxx局部收斂定理 設(shè)函數(shù)它在的梯度矩陣正定.若初始點充分靠近并且矩陣滿足條件 即存在使得有 則對,迭代格式(. . )有意義,且迭代點序列以二階的收斂速度收斂到定定理理10.2 牛頓法當牛頓法

10、收斂時,有下列關(guān)系2(1)( ) kkxxc xxc,2是某個常數(shù) 因此算法至少是 階收斂的.特別的,對于二次凸函數(shù),用牛頓法求解,經(jīng)一次迭代即達到極小點.設(shè)有二次凸函數(shù)其中A是對稱正定矩陣1( )2TTf xx Axb xc10.2 牛頓法先用極值條件求解.令( )0f xAxb得最優(yōu)解1xA b 下用牛頓法解,任取一初始點x(1)(2)(1)1(1)(1)1(1)1()()xxAf xxAAxbA b (2),.xx顯然即一次迭代即達極小點定義:若一個算法用于求解嚴格二次凸函數(shù)極小值問題時從任意初始點出發(fā),算法在有限次迭代后可到達函數(shù)的極小值點,稱此算法具有二次終止性.于是牛頓法具有二次終

11、止性10.2 牛頓法注意,當初始點遠離極小點時,牛頓法可能不收斂阻尼牛頓法阻尼牛頓法基本思想:增加了沿牛頓方向的一維搜索.迭代公式為(1)( )( ) kkkkxxd=( )2( )1( )()(),kkkdf xf x k其中為牛頓方向,是由一維搜索所得的步長 即滿足( )( )( )( )() kkkkkf xdf xd)=min10.2 牛頓法算法(阻尼牛頓法)(0)( )2( )1( )( )( )2( )1( )( )( )( )( )( )( )1,0,1;2,(),()3,(),;, ()()4,: min() () kkkkkkkkkkkkkkStepxkStepf xf xS

12、tepf xxdf xf xStepxdf xdf xd 給定初始點允許誤差置計算若停止 得解否則 令 從出發(fā) 沿方向作一維搜索 (1)( )( ) 5,:1,2kkkkxxdStepkk令置轉(zhuǎn)10.2 牛頓法10.2.3 修正牛頓法例 用阻尼牛頓法求解下列問題421122min( )(1)f xxx xx(1)(1)2(1)(0,0) .,Hessian001(),()212Txf xf x 取初點在該點 函數(shù)的梯度和陣為牛頓方向(1)2(1)1(1)1()()01021220df xf x 10.2 牛頓法(1)(1),xd從出發(fā) 沿方向進行一維搜索 令(1)(1)4)=16+1f xd

13、( )= ( 1( )=0=0顯然,用阻尼牛頓法不能產(chǎn)生新點, 而點x(1) =(0,0) T并不是問題極小點.可見從x(1)動身,用阻尼牛頓法求不出問題的極小點, 原因在于 Hessian 矩陣 2f (x(1)非正定再令10.2 牛頓法考慮 (10.2.2),記搜索方向d(k) = x- x(k) ( )2( )1( )()() (e)kkkdf xf x 阻尼牛頓法所用搜索方向是上述方程的解2( )( )( )()() (d)kkkf xdf x 此處假設(shè)逆矩陣 存在2( )1()kf x10.2 牛頓法2( )()kHessianf x解決矩陣非正定問題的基本思想2( )2( )1(

14、)( )(),( )(): () (f)kkkkkkkf xGdGf xG df x 修正構(gòu)造一個對稱正定矩陣在方程中用取代矩陣( )1( )() (g)kkkdGf x 再沿此方向作一維搜索2( )k?,() (h)I,.kkkkGGf xI 如何構(gòu)造比如 可令其中 是單位陣是一個適當?shù)恼龜?shù)10.2 牛頓法算法 修正牛頓法(0)( )( )( )2( )( )1( )( )( )1,0,0;2,(),(),;step3 3, (),0),()()4,kkkkkkkkkkkkkkkkStepxkStepgf xf xxStepGf xBGEEGdBf xStepxd 給定初始點允許誤差置計算梯

15、度=若停止 得解否則轉(zhuǎn)計算Hesse矩陣置矩陣其中為修正矩陣(當正定時 它取計算修正牛頓方向 從出發(fā) 沿方向作(精確或( )( )( )( )(1)( )( ): min() () ,:1,2kkkkkkkkkf xdf xdxxdkk非精確)一維搜索 令置轉(zhuǎn)10.2 牛頓法000() :RD D|( )()lim()() 0.nf xkxfRxfSxD f xf xf x設(shè)在某開集上二階連續(xù)可微,且修正牛頓法的初始點使得的水平集是緊集.若矩陣序列定理 全局收斂定滿足有界分性理解特,則10.3共軛梯度法1 1 共軛方向與擴張子空間定理共軛方向與擴張子空間定理定義定義10.3.1 10.3.1

16、設(shè)設(shè)A A是是n nn n對稱矩陣對稱矩陣, ,若若Rn Rn 中的兩個方向中的兩個方向d 1 d 1 和和d2d2滿足滿足 (d 1)T Ad 2 =0 (d 1)T Ad 2 =0 （10.3.110.3.1）則稱這兩個方向關(guān)于則稱這兩個方向關(guān)于A A共軛共軛, ,或稱它們關(guān)于或稱它們關(guān)于A A正交正交. .(1)(2)( )( )( ),.,A0, ,1,2,. . (10.3.2)ki TjdddkdAdiji jkn 若是E 中 個方向,它們兩兩關(guān)于共軛,即 則稱這組方向是A共軛,或稱它們?yōu)锳的k個共軛方向10.3 共軛梯度法幾何意義幾何意義設(shè)有二次函數(shù)1( )()() (10.3.

17、3)2Tf xxxA xx其中A是nn對稱正定矩陣, x是一個定點.1()()2TxxA xxc是以x為中心的橢球面,( )()0 f xA xxA正定,故x是f(x)的極小值點.f(x)的等值面由于10.3共軛梯度法設(shè) x(1)是在某等值面上一點,此面在點x(1)處的法向量(1)(1)()()f xA xx又設(shè)d (1)是在該等值面在點x (1)處的一切向量.d (2) = x - x (1)(1)(1)(1)(1),().()0,Tdf xdf x顯然與正交即于是(1)(2)0TdAd 即等值面上一點x(1)處的切向量與由這點指向極小點的向量關(guān)于A共軛.10.3共軛梯度法x1x2(1)d(

18、2)d(1)xx10.3共軛梯度法0000011111(),(),()02(),();,()01,3(),)0(0,1,., );1 算算法法 共共軛軛方方向向法法nTkkkkkkkknkTjxRf xdf xdkf xdxxdf xkndRdGdjkkR步 初始化 給定初始點計算給定一個搜索方向0,使得0;置步線搜索 求解一維極小化問題min若或停止 否則轉(zhuǎn)步3步 計算共軛方向 計算一個非零方向使得(置12 k轉(zhuǎn)步(1)(2)( ),.1.,A1,.03kdddk 設(shè)A是n階對稱正定矩陣,是 個共軛的非零向量 則這個向量組線定理.性無關(guān).10.3共軛梯度法(1)(2)( )(1)(1)(2)

19、( )(1)(2)(1)(1)(1)1( )2A,.,A,.,.,(,1).0 3 2 TTknkkkf xx Axb xcndddxRdddxxxxf xxk(擴張子空間定理)設(shè)有函數(shù) 其中 是 階對稱正定矩陣是 共軛的非零向量.以任意的為初始點,依次沿進行一維搜索 得到點列則是函數(shù)在線性流形 上的唯一極小點特別地 當定定理理. . . .(1)( )1(1)(2)( ),( ).,(,),.,. knkiiiiknxf xEx xdddd時是函數(shù)在上的唯一極小點其中是生成的子空間10.3共軛梯度法(1)(1)(1)(1)( ),( ),().kkkf xxf xxxf x證明:由于嚴格凸

20、要證明是函數(shù)在線性流形 上的唯一極小點只要證在點,與子空間正交.用歸納法證之,為方便,用g j表示函數(shù)f(x)在x(j)處的梯度,即( )() (10.3.6) jjgf x1,kkgk 證明對 歸納211,.kg 當由一維搜索的定義知121mn,.mmmmkgg 假設(shè)時下證10.3共軛梯度法利用上式可以將 gm+2 和d (i) 的內(nèi)積寫成( )( )( )(1)211 (10.3.8)ii Ti TmmmmdgdgdAd當i=m+1時,由一維搜索定義,知(1)20 (10.3.9)mTmdg當1im+1時,由歸納假設(shè)知( )10 (10.3.10)i Tmdg(1)(2)(1),.,A,m

21、ddd由于關(guān)于 共軛 則( )(1)=0 (10.3.11)i TmdAd由二次函數(shù)梯度的表達式和點x(k+1)的定義,有(2)(1)(1)21(1)11() ( 10.3.7) mmmmmmmmgAxA xdbgAd10.3共軛梯度法即由10.3.8-11,知( )20 i Tmdg21.mmg (1)(1),( ).( ),.kkxf xxf x根據(jù)上述證明是在上的極小點由于嚴格凸故必為此流形上的唯一極小點(1)(2)( )1(1),.,0,.nnnnnkn dddEgxE當,是的一組基 此時必有從而是函數(shù)在上的唯一極小點( )1:10.3.2 TjkThgdjk在的條件下, =0, 推論

22、10.3共軛梯度法上述定理表明,對于二次凸函數(shù),若沿一組共軛方向(非零向量)搜索,經(jīng)有限步迭代必到達極小點.2 線性共軛梯度法與二次終止性線性共軛梯度法與二次終止性Hesteness和Stiefel于1952年為解線性方程組而提出基本思想:把共軛性與最速下降法相結(jié)合,利用已知點處的梯度構(gòu)造一組共軛方向,并沿著這組方向進行搜索,求出目標函數(shù)的極小點10.3共軛梯度法先討論對于二次凸函數(shù)的共軛梯度法,考慮問題1min( ) (10.3.12)2,TTnf xx Axb xcxEAc對稱正定 是常數(shù).求解方法(1)1(1)(1)1(1)(2)(2)2(1)(2)(2)20 () (10.3.13),

23、.,0 xgdf xgdxxggddd首先, 任意給定一初始點,計算出目標函數(shù)在該點的梯度,若,則停止計算,否則,令沿搜索 得點計算在處的梯度 若則利用-和構(gòu)造搜索方向,再沿搜索.10.3共軛梯度法( )( )( )(1)(1)( )( )( )( )( )( ) (103.14)()=min ()kkkkkkkkkkkkkxdxdxxdf xdf xd一般地,若已知點和搜索方向, 則從出發(fā),沿進行搜索,得其中步長滿足 ( )( )(1)T( )(1)T( )( )()( )()0 (10.3.15) ()0 kkkkkkf xdf xdAxb d記 令 即k下求 的表達式10.3共軛梯度法(

24、 )( )T( )( )T( )T( )( )T( )( ()0 ()0 (10.3.16) (10.3.17) kkkkkkkkkkkkkA xdb dgAddg ddAd(1)1( )(1)1(1)( )(1)( )1k( )0,A + (10.3.18) kkkkkkkkkkf xxggdddddgd計算在處的梯度,若,則停止計算,否則,利用-和構(gòu)造下一搜索方向并使和關(guān)于 共軛,按此設(shè)想.令10.3共軛梯度法 綜上分析,在第一個搜索方向取負梯度的前提下,重復(fù)使用公式3.14,3.17-3.19就能伴隨計算點的增加,構(gòu)造出一組搜索方向.( )( )(1)( )( )( )1k( )1( )

25、( )(1)(1),+0 (10.3.19) k Tk Tkk Tk Tkkk Tkkk TkkkdAdAddAgdAddAgdAdxd上式兩端左乘并令再從出發(fā),沿方向搜索.10.3共軛梯度法 定理10.3.3 對于正定二次函數(shù)(10.3.12),具有精確一維搜索的Fletcher-Reeves法在mn次一維搜索后即終止,并且對所有i(1 i m),下列關(guān)系成立:( )( )( )( )1,0, 1,2,.,12,0, 1,2,.,13, (0)i TjTijTiTiiiidAdjig gjig dg gd 蘊涵證明: 顯然m1,下用歸納法(對i)證之. (1)11,),2,idgi 當時由于

26、從而3 成立 對時關(guān)系1)和2)成立,從而3)也成立.10.3共軛梯度法設(shè)對某個im,這些關(guān)系均成立,我們證明對于i+1也成立.先證2),(1)( )( )iiiixxd由迭代公式兩端左乘A,再加上b,得( )1 (10.3.20)iiiiggAd其中 由式(10.3.17)確定,即i( )( )( )( )( )0 (10.3.21)TiTiiiii Tii Tig dg gdAddAd10.3共軛梯度法考慮到(10.3.20)和(10.3.18),那么( )1( )( )(1)1() (10.3.22)TTiijiijTi TjjijijgggAdgg gdAdd( )(1)111)TTi

27、 Tiiiggg gdAd(注:j=1時上式為( )(i 1)( )( )1,0,(10.3.21) 0 i Ti TiTiiiTiijidAddAdg ggg當時由歸納假設(shè)根據(jù)10.3共軛梯度法當ji時,根據(jù)歸納假設(shè),式(10.3.22)等號右端各項均為010Tijgg故 再證1),運用(10.3.18)和(10.3.20),那么(1)( )( )( )11( )( )1TiTjijiijjTi TjiijdAdgdAdgggdAd 當j=i時,把(10.3.19)代入上式第一個等號的右端,立得(1)( )0iTjdAd10.3共軛梯度法當ji時,由前面已經(jīng)證明的結(jié)論和歸納假設(shè),式中第2個等

28、號右端顯然為0,因而(1)( )0iTjdAd最后證3),易知(1)( )11111TiTiTiiiiiigdggdgg 綜上,對i+1,上述三種關(guān)系成立(1)(2)(),Re.,.,A10.3.2mFletcherevesdddTh由上可知共軛梯度法所產(chǎn)生的搜索方向是 共軛的,根據(jù),經(jīng)有限步迭代必達極小點.10.3共軛梯度法注意,初始搜索方向選擇最速下降方向十分重要, 如果選擇別的方向作為初始方向,其余方向均按FR方法構(gòu)造,則極小化正定二次函數(shù)時,這樣構(gòu)造出來的一組方向并不能保證共軛性.例例 考慮下列問題考慮下列問題2221231min 2xxx取初始點和初始搜索方向分別為(1)(1)111

29、 ,210 xd 10.3共軛梯度法顯然, 不是目標函數(shù)在 處的最速下降方向.(1)d(1)x下面,我們用FR法構(gòu)造兩個搜索方向.(1)(1),:xd1從出發(fā) 沿方向進行搜索,求步長,使?jié)M足(1)(1)(1)(1)101()min()23f xdf xd得(2)(1)(1)121/32/31/3 ,1/311xxdg (2)(1)21dgd 令10.3共軛梯度法根據(jù)公式(10.3.19),有(1)21(1)(1)2/3169TTdAgdAd 因而(2)2/315/911/325/99101d (2)(2),:xd2從出發(fā) 沿方向進行搜索,求步長,使?jié)M足(1)(1)(2)(2)202()min(

30、)2126f xdf xd得 10.3共軛梯度法(3)(2)(2)239/7818/789/78,9/785/265/26xxdg(3)(2)32dgd 令根據(jù)公式(10.3.19),有(2)32(2)(2)45676TTdAgdAd10.3共軛梯度法注意注意,在在FR法中法中,初始搜索方向必須取最速下降方向初始搜索方向必須取最速下降方向因而(3)18/785/91314519/785/9536766765/261175d (1)(2)(3)(2)(1)(3)(1)(2)(3),AAAAddddddddd可以驗證與關(guān)于 共軛,與關(guān)于 共軛,但與不關(guān)于 共軛,于是,不關(guān)于共軛.10.3共軛梯度法

31、可以證明,對于正定二次函數(shù),運用FR法時不作矩陣運算就能求出因子i定理定理10.3.4 對于正定二次函數(shù)對于正定二次函數(shù),FR法中因子法中因子 i具有具有下述表達式下述表達式212, (1,0) (10.3.24)iiiigigg證明:( )(1)( )11( )( )( )(1)( )()/()/i TTiiiiiii Tii TiiidAggA xxdAddA xx10.3共軛梯度法2111( )( )12( )() (10.3.23)()10.3.3,. Tiiiii Ti Tiiii Tiiggggdggdgdgg根據(jù)定理因此212, (10.3.24)iiigg10.3共軛梯度法FR

32、法(對二次凸函數(shù))(1)( )k( )( )(1)1111,1.2,().0, ,. 3,. ,1,0,1(10.3.24). kkkkkkkkkxkgf xgxxdgdkk給定初點置計算若停止計算 得點；否則進行下一步構(gòu)造搜索方向令其中 當時當時按公式計算10.3共軛梯度法(1)( )( )(1)4,(10.3.17).5,:1,2kkkkkkxxdknxxkk令 其中按公式計算步長若則停止計算 得點 否則 置轉(zhuǎn)2212min ( )2f xxx例3.2 用FR法求解下列問題(1)(5,5)Tx初點10.3共軛梯度法令第一次迭代，目標函數(shù)f(x)在點x處的梯度122( )4xf xx(1)1

33、1020dg (1)(1),:xd1從出發(fā) 沿方向進行一維搜索 求步長10.3共軛梯度法(1)11(1)(1)10( 10, 20)205201018( 10, 20)0420TTg ddAd (2)(1)(1)151020/955205/918xxd 第2次迭代目標函數(shù)在點x 處的梯度(2)240/920/9g10.3共軛梯度法(2)(1)214100181dgd (2)(2),:xd2從出發(fā) 沿方向作一維搜索 求構(gòu)造搜索方向d .先計算因子(2)1222212221(40/9)( 20/9)4102081gg 令(2)222(2)(2)420 100(2, 1)9811920204100(

34、 4,1)81041TTg ddAd 10.3共軛梯度法(3)(2)(2)220/94091005/9102081xxd (2)200 xg 0顯然點處目標函數(shù)的梯度,已達極小點010.3 共軛梯度法11100 k=0,1,. (10.3.3.1), kkkkkkkkkkxxddgddg其中初始方向步長參數(shù)由一維搜索得到，的計算公式通常有如下幾種：一般迭代格式11()1, (Fletcher-Reeves(FR)()kkkTkk Tggggl3用于一般函數(shù)的共軛梯度法非線性共軛梯度法10.3共軛梯度法11()2, TkkkkTkkgggg g-PRP(Polak-Ribiere-Polyar1

35、11()3, () ()TkkkkTkkgggdggk-SW(Sorenson-Wolfe21121()()4, ()()kTkkkkTkkdf xgdf xd-Daniel115, ()TkkkTkggdgk -Dixon10.3共軛梯度法(1)(1)(1)(1)(1)( )( )( )( )( )(1)( )( )1,(),0.2,(),()min() jjjjjjjjjjjxyxdf ykjf yf ydf ydyyd 給定初始點,允許誤差0.置若則停止計算 否則作一維搜索求滿足 令 FR共軛梯度法10.3共軛梯度法3,如果j n,轉(zhuǎn)步4,否則,轉(zhuǎn)5(1)(1)( )2(1)2( )4,

36、()()():1,2.jjjjjjjdf ydf yf yjj令 =-其中 置轉(zhuǎn)步(1)(1)(1)(1)(1)(1)5,()1, :1,2.jnkxyyxdf yjkk 令 =,置轉(zhuǎn)步可以證明,對一般函數(shù),共軛梯度法在一定條件下是收斂的,10.3共軛梯度法FR算法中使用精確線搜索，我們有如下收斂性結(jié)果k1:( )Lipschitz.FRArmijo0,0,liminf0(Armijo()()() nkkkkkkkkTkkkfRRf xkggf xdf xcf xd 假設(shè)函數(shù)有下界，梯度是連續(xù)的在共軛梯度法中，步長參數(shù)是由精確線搜索確定的，并且滿足充分下降條件(即條件).若則 條件:選擇步長滿

37、足 定定理理4. 1 擬牛頓條件和算法步驟10.4 擬牛頓法基本思想基本思想:牛頓法成功的關(guān)鍵在于利用了牛頓法成功的關(guān)鍵在于利用了Hesse矩陣提供的曲率矩陣提供的曲率信息，而計算信息，而計算Hesse矩陣工作量大，并且有的目標函矩陣工作量大，并且有的目標函數(shù)的數(shù)的Hesse矩陣很難計算，甚至不好求出，這就導(dǎo)致矩陣很難計算，甚至不好求出，這就導(dǎo)致僅利用目標函數(shù)一階導(dǎo)數(shù)的方法僅利用目標函數(shù)一階導(dǎo)數(shù)的方法,擬牛頓法就是利用擬牛頓法就是利用目標函數(shù)值目標函數(shù)值f和一階導(dǎo)數(shù)和一階導(dǎo)數(shù)g的信息的信息,構(gòu)造出目標函數(shù)的構(gòu)造出目標函數(shù)的曲率近似，而不需要明顯形成曲率近似，而不需要明顯形成Hesse矩陣，同時

38、具有矩陣，同時具有收斂速度快的優(yōu)點。收斂速度快的優(yōu)點。牛頓法的迭代公式為10.4 擬牛頓法(1)( )( ) (10.4.1)kkkkxxd=( )( )kkdx 其中是在處的牛頓方向( )2( )1( )()()102kkkdf xf x= (.4. )( )k.kx是從出發(fā)沿牛頓方向搜索的最優(yōu)步長2( )12( )1(),()kkkf xHf x為構(gòu)造的近似矩陣先分析與一階導(dǎo)數(shù)的關(guān)系.10.4擬牛頓法(1)(1)(1)(1)2(1)(1)( )()() ()(kkTkkTkkf xf xf xxxxxf xxx)+1 )2(1)(1),( )Taylorkkkxf xx設(shè)在第 次迭代后,得

39、點將在點展開(1)2(1)(1)( )( )()()(10.4.3)kkkg xf xf xf xxx +) (1)kx于是在附近( )kxx令,則( )(1)2(1)( )(1)()()()(kkkkkf xf xf xxx +)記10.4 擬牛頓法( )(1)( )( )(1)( )(10.4.4)()() (10.4.5)kkkkkkpxxqf xf x 那么( )2(1)( )() (10.4.6)kkkqf xp 2(1)Hessian(),kf x設(shè)矩陣可逆 則( )2(1)1( )() (10.4.7)kkkpf xq ( )( )(1)12(1)11,(10.4.7)Hessi

40、an.Hessian() ,kkkkkkpqxHf xH于是 計算出和可根據(jù)估計在處的矩陣的逆令取代牛頓法中的陣的逆則滿足(10.4.8)稱為擬牛頓條件(方程)，也稱為割線方程.怎樣確定滿足這個條件的H k+1 ?10.4 擬牛頓法( )( )1= (10.4.8)kkkpHq算法 擬牛頓法000011(),(0,1)(),0.2(),3(),(,) |,0, nn nkkkkkkkkkkkkkxRHRgf xkgdH gR x dx xxdxxd初始化 給定初始點,正定矩陣,;計算置平穩(wěn)性檢驗 若則停止 否則, 計算搜索方向線搜索 沿射線進行線搜索，求出步長令10.4 擬牛頓法1114=()

41、,kk kkkkgf xHH(修正擬牛頓方程),計算對校正，得使?jié)M足擬牛頓條件，令1，轉(zhuǎn)24. 2 對稱秩1校正2( )1111(),., ,.kkkkf xnHnHnIHH當是 階對稱正定矩陣時 滿足擬牛頓條件的矩陣也應(yīng)是 階對稱矩陣于是 構(gòu)造如此的近似矩陣的一般策略是:取為任意一 階對稱正定矩陣(如單位陣 ) 然后通過修正給出令Hk稱為校正矩陣.確定Hk的一個方法是令10.4 擬牛頓法1 (10.4.9)kkkHHH ( )( )kk TkkHZZ(10.4.10)( ).kkZn是一常數(shù),是 維列向量( )(10.4.8),kZ的選擇應(yīng)使得到滿足 令( )( )( )( )( )kkkk

42、 TkkkpH qZZq(10.4.11)從而( )( )( )( )( )kkkkk TkkpH qZZq(10.4.12)利用(10.4.10),(10.4.12-13),(10.4.9)可寫成10.4 擬牛頓法( )(10.4.11),k Tq等號兩端左乘整理得( )T( )( )( )( )2()()kkkk TkkkqpH qZq(10.4.13)( )( )( )( )1( )T( )( )()()()kkkkTkkkkkkkkpH qpH qHHqpH q(10.4.14)-秩秩1 1校正公式校正公式利用秩1校正極小化函數(shù)f(x),在第k次迭代中,令搜索方向( )( )()kkk

43、dHf x (10.4.15)10.4 擬牛頓法( )kkd然后沿方向搜索,求步長,滿足( )( )( )( )0()min()kkkkkf xdf xd 確定后繼點(1)( )( )kkkkxxd(10.4.16)4.3 對稱秩2校正10.4 擬牛頓法定義校正矩陣( )( )( )( )T( )T( )( )T( )kk TkkkkkkkkkkppH qqHHpqqH q(10.4.17)DFP(Davidon-Fletcher-Power)公式( )( )( )( )T1( )T( )( )T( )kk TkkkkkkkkkkkppH qqHHHpqqH q(10.4.18)那么1，DFP

44、算法算法(變尺度法變尺度法)DFP算法10.4 擬牛頓法( )(1)1(1)1( )( )( )( )( )( )( )0(1)( )(1,0,2, ()13, 4,()min()knnkkkkkkkkkkkkkkkStepxEStepHIxgf xkStepdH gStepxdf xdf xdxxd 給定初始點允許誤差置計算出在處的梯度置令從出發(fā) 沿進行一維搜索 求使 令),10.4擬牛頓法(1)(1)(1)(1)(1)( )(1)( )( )1115, (),66,2;,77,(),(10.4.18),:1,3kkkkkkkkkkkkStepf xxxStepStepknxxStepSte

45、pStepgf xpxxqggHkkStep 檢驗是否滿足收斂準則 若停止 得否則 轉(zhuǎn)若則令轉(zhuǎn)否則 轉(zhuǎn)令由公式計算置轉(zhuǎn)例1用DFP方法求解下列問題10.4擬牛頓法22121min 242xxx初始點及初始矩陣分別為(1)1210,101 xH12( ,)Txx x在點的梯度124(1)2xgx第1次迭代10.4擬牛頓法(1)x在點處的梯度142g 令搜索方向(1)1142dH g (1)(1),:xd1從出發(fā) 沿方向進行一維搜索,求步長(1)(1)0min()f xd得到1518令10.4擬牛頓法(2)(1)(1)1248/95124/918xxd 284(14/9948/929g第2次迭代1

46、0.4擬牛頓法(1)(1)110/95/9pd(1)2140/910/9qgg2H計算(1)(1)(1)(1)T1121(1)T(1)(1)T(1)1TppH q qHHHpqqH q10.4擬牛頓法10/910/95/9105/940/90110/95/910/91040/91040/910/90110/9011040/940/910/90110/9令10.4擬牛頓法10421641101214118178638138305306(2)2286384/91383058/9306112 451dH g 10.4擬牛頓法(2)(2),:xd2從出發(fā) 沿方向進行一維搜索,求步長(2)(2)0min

47、()f xd得到21736令(3)(3)(2)210 xxd 于是得最優(yōu)解10.4擬牛頓法(3)30()0gf x 12( ,)(1,0)x x2 DFP算法的正定性及二次終止性算法的正定性及二次終止性10.4擬牛頓法0,1,2,., ,DFP(1,2,., )0.1 4.1iiginH in若則方法構(gòu)造的矩陣為對稱正定.定矩陣理證明:用歸納法 DFP方法中, H1是給定的對稱正定矩陣.設(shè)Hj是對稱正定矩陣,下證Hj+1也是對稱正定矩陣.根據(jù)定義,對稱性是顯然的,下證正定性(10.4.19)10.4擬牛頓法,nyE對任意的非零向量有( )( )T( )( )1( )T( )( )T( )( )

48、2( )2( )T( )( )T( )()() TjjTjj TjjTTjjjjjjjTjTjjTjjjjjjy H qqH yy ppyy Hyy H ypqqH qy H qy py H ypqqH q12,jjHH又對稱正定 故存在對稱正定陣使得1122jjjHH H令10.4擬牛頓法11( )22, (10.4.20)jjjpH y qH q那么( )( )T( )TTjTjTjjjTjy H yp py H qp qqH qq q于是(10.4.19)可寫為( )221( )T( )T( )22( )T( )T()()()()()() TjTTTjjjTjTTTjjy pp qy H

49、yp ppqq qy pp p q qp qpqq q(10.4.21)由Schwartz不等式,有10.4擬牛頓法2T()()()0TTTp p q qp qq q(10.4.22)考慮到一維搜索及方向的定義,(10.4.21)右端第一項的分母( )( )( )( )1()()j Tjj Tj TjjjjjTjjjjpqdggdgH gg j0,0,jjgH由于正定,故( )( )0 (10.4.23)j Tjpq于是10.4擬牛頓法( )2( )T( )()0 (10.4.24)Tjjjy ppq下證(10.4.22)和(10.4.24)不同時為0.若不然,(10.4.22)為0,則p/q

50、,即p=q(0).從而( )( )( )T( )0jTijjypy pqp( )2( )T( )()0Tjjjy ppq綜上,知10.4擬牛頓法10Tjy Hy1min( )2TTf xx Axb xc 定理10.4.2 設(shè)用DFP方法求解下列問題其中A為n階對稱正定矩陣.取初點x(1) En ,令H1為n階對稱正定矩陣,則成立:( )( )( )( )1( )(1)( )( )1, 0, 1 (10.4.25)2, , 1 (10.4.26),0,.i TjiikiiiiiipApijkHAppikpxxdkn 其中證明:對k歸納. k=1時有10.4擬牛頓法(1)(1)(1)(1)T(1)

51、(1)1121(1)T(1)(1)T(1)1()TppH q qHH ApHAppqqH q(10.4.27)由于( )(1)( )( )1() (10.4.28)iiiiiiApA xxggq(1)(1)Apq(1)(1)2H App代入(10.4.27)即得即(10.4.26)成立.當k=2時,10.4擬牛頓法(1)(2)(1)222(1)(1)22222() 0TTTTpAppAH gg H Apg p 由此結(jié)果,易證k=2時(10.4.26)亦成立下設(shè)k=m時(10.4.25-26)成立,下證當k=m+1時上述關(guān)系式也成立.先證k=m+1時(10.4.25)成立. (1)(1)(2)(

52、),.,.mmppppA與中每一個關(guān)于 共軛由歸納假設(shè),只需證:由對(10.4.26)的歸納假設(shè),當1im時有10.4擬牛頓法( )( )1iimHApp由此有( )(1)( )111( )( )11111( )11() i Tmi TmmmTiTimmmmmTimimpAppAHggHApgpgd (10.4.29)根據(jù)Th10.3.2的推論,有( )10 (1)Timgdim由(10.4.29),知10.4擬牛頓法( )(1)0i TmpAp再證當k=m+1時(10.4.26)成立對于1im+1有(1)(1)( )21(1)T(1)(1)(1)T( )11(1)T(1)1( )mmTimm

53、mmmmimmmmmppHApHpqHqqHApqHq(10.4.30)當i=m+1時,由(10.4.28)知(1)(1)mmApq將其代入(10.4.30)得10.4擬牛頓法(1)(1)2mmmHApp當im+1時,根據(jù)關(guān)于(10.4.26)的歸納假設(shè)及當k=m+1時(10.4.25)成立,考慮到(10.4.28),則有(1)( )(1)( )(1)( )10mTimi TmTimqHApqppAp從而可得( )( )( )21iiimmHApHAppQ.E.D.推論:在Th10.4.2的條件下,必有10.4擬牛頓法11nHADFP方法中構(gòu)造出來的搜索方向是一組A共軛方向DFP方法具有二次終

54、止性.22( ),0, ( )( )( ),( ).nnnTknfExEmxC xx f xf xyEm yyf x yDFPxfE若 是上的二次連續(xù)可微實函數(shù) 對任意的存在常數(shù)使得當時有 則方法產(chǎn)生的序列或終止于或收斂于 在上的唯一極小點3 BFGS公式及 Broyden簇10.4擬牛頓法2(1)1(),(10.4.6),kkBf x若用不含二階導(dǎo)數(shù)的矩陣近似海塞矩陣則由給出另一種形式的擬牛頓條件 即( )( )1= (10.4.32)kkkqBp( )( )( )( )T1( )T( )( )T( )kk TkkkkkkkkkkkqqB ppBBBqppB p(10.4.33)可得修正公式

55、-關(guān)于矩陣B的BFGS修正公式10.4擬牛頓法1,(10.4.32)kB設(shè)可逆 則由可知( )1( )1 = kkkpBq11(10.4.8), kB于是滿足擬牛頓條件故可令111= (10.4.34)kkHB,HBFGS:ShermanMorrison于是 利用公式可得關(guān)于 的公式( )( )( )( )1( )T( )( )T( )( )( )T( )( )T( )T( )(1) k Tkkk TBFGSkkkkkkkkkkkkkkkqH qppHHpqpqpqHH qppq(10.4.35)上述公式由Broyden,Fletcher,Goldfarb,Shanno(1970)給出.10.

56、4擬牛頓法定義DFPBFGS111(1) (10.4.36)kkkHHH-Broyden簇( )( )DFPBFGS2,kkkpH q和公式都有由和構(gòu)成的對稱秩校正 故此兩公式的加權(quán)組合仍具有相同的形式顯示表達式10.4擬牛頓法( )( )( )( )T( )( )T1( )T( )( )T( )( )( )T1 kk TkkkkkkkkkkkkkDFPkkkppH qqHHHvvpqqH qHvv(10.4.37)( )( )1/2( )( )T( )( )T( )( )T( )kkkkkkkkkkkkpH qvqH qpqqH q其中(10.4.38)10.4擬牛頓法1min( )2TTf

57、 xx Axb xc 定理10.4.3 設(shè)其中A為n階對稱正定矩陣. 則對于Broyden方法,成立:( )( )( )( )11, 0, 12, , 1i TjiikpApijkHAppik 線搜索方法：每次迭代時產(chǎn)生一搜索方向，在此方向上進行精確或不精確一維搜索，得到下一迭代點。缺點：可能由于步長過大導(dǎo)致算法失敗，特別當問題病態(tài)時。Ch10.5 信賴域方法主要數(shù)值方法1：主要數(shù)值方法2：信賴域方法： 在每次迭代時，強制性要求新迭代點與當前迭代點之間的距離不超過某一控制量。實際上是，在以當前迭代點為中心的鄰域內(nèi)對一近似于原問題的簡單模型求極值。優(yōu)點：算法穩(wěn)定性好、收斂性強。主要內(nèi)容：1 無約

58、束優(yōu)化信賴域法： 1.1 算法描述 1.2 收斂性2 約束優(yōu)化帶一個等式約束）： 2.1 逐步二次規(guī)劃法SQP） 2.2 Marotos 效應(yīng) 2.3 信賴域方法1 無約束優(yōu)化信賴域方法問題：基本思想：給定初始迭代點，確定一個以其為中心的鄰域，在此域內(nèi)優(yōu)化目標函數(shù)的二次逼近式，得到下一迭代點。min( )nx Rf x信賴域子問題：信賴域內(nèi)原問題的逼近問題：1.1 算法描述Step1 給定初始點Step2 假設(shè) ，則停止計算，得解；否則，解子問題得最優(yōu)解Step3 計算 ，令選取下一信賴域半徑使其滿足Step4 產(chǎn)生 轉(zhuǎn)step21112134,0,0,01,01, : 1n nx BRk k

59、gkdkr1,0,0kkkkkxdrxxr11341,kkkkkdrdr 1,:1kBkk定理： 是信賴域子問題的解當且僅當它是子問題的K-T點，且 是半正定矩陣。kd*()BI1.2 收斂性在一定條件下，信賴域方法具有全局收斂性。設(shè) 是 上的實函數(shù)， 是給定初始點， 是有界閉集， 和 在 上連續(xù)，用信賴域方法求得序列 ，那么 .( )f xnR1x1|( )()Sx f xf x( ),( )f xf x2( )f xS kxlim()0kkf x2 等式約束非線性優(yōu)化問題(2.1)：其中：21( )()()()2TTkkkf xf xf xddf x d( )()()Tkkc xc xc xdmin( ). .( )0f xstc x 2.1 逐步二次規(guī)劃(SQP)SQP方法是求解非線性規(guī)劃的一般方法，是線搜索方法的一種?；痉椒ǎ呵蠼?/p>