北郵最優(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最速下降法最速下降法 考慮無(wú)約束問(wèn)題 min f(x), xRn (10.1.1)其中 f(x)具有一階連續(xù)偏導(dǎo)數(shù)。在處理這類(lèi)問(wèn)題時(shí)，一般策略是，希望從某一點(diǎn)出發(fā)，選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向，沿此方向搜索以期盡快達(dá)到極小點(diǎn)，基于這一思想，Cauchy于1847年提出了最速下降法。這是無(wú)約束最優(yōu)化中最簡(jiǎn)

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

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

4、xStepdxdf xdf xdStepxxdkkStep給定初始點(diǎn)允許誤差置計(jì)算搜索方向若停止 否則 從出發(fā) 沿進(jìn)行一維搜索 求使得 令置轉(zhuǎn)例1.1 用最速下降法求解下列問(wèn)題2212(1)min ( )21(1,1) ,10Tf xxxx初點(diǎn)第一次迭代目標(biāo)函數(shù)f(x)在點(diǎn)x處的梯度124( )2xf xx令搜索方向(1)(1)4()21642 51/10df xd (1)(1),xd1從出發(fā) 沿方向進(jìn)行一維搜索 求步長(zhǎng)即(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在直線上的極小點(diǎn)第二次迭代(2)(2)(2)4/9()8/9451/109df xd (2)( )f xx在點(diǎn)處的最速下降方向?yàn)?2)(2),:xd從出發(fā) 沿方向進(jìn)行一維搜索(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在點(diǎn)處的最速下降方向?yàn)?3)(3),:xd從出發(fā) 沿方向進(jìn)行

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

7、=(x,-f(x),是En En En的映射.每給定一點(diǎn)x,經(jīng)算法D作用,得到點(diǎn)x和在x處的負(fù)梯度(從x出發(fā)的方向d).算法M是En En En 映射.每給定一點(diǎn)x及方向d=-f(x),經(jīng)M作用,即一維搜索,得到一個(gè)新點(diǎn),在這一點(diǎn),與前面的迭代點(diǎn)相比,具有較小的目標(biāo)函數(shù)值,根據(jù)Th1.1,當(dāng) f(x) 0時(shí),M是閉映射.由于f(x)是連續(xù)可微實(shí)函數(shù), 故D連續(xù),據(jù)Th8.1.1推論2,A在x(f(x) 0)處是閉的. 其次,當(dāng)x時(shí), d=-f(x) 0,那么f(x) T d0,因而對(duì)于yA(x),有f(y)0,滿足1,且對(duì)每一個(gè)成立定:(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ù)它在的梯度矩陣正定.若初始點(diǎn)充分靠近并且矩陣滿足條件 即存在使得有 則對(duì),迭代格式(. . )有意義,且迭代點(diǎn)序列以二階的收斂速度收斂到定定理理10.2 牛頓法當(dāng)牛頓法

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

11、止性10.2 牛頓法注意,當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí),牛頓法可能不收斂阻尼牛頓法阻尼牛頓法基本思想:增加了沿牛頓方向的一維搜索.迭代公式為(1)( )( ) kkkkxxd=( )2( )1( )()(),kkkdf xf x k其中為牛頓方向,是由一維搜索所得的步長(zhǎng) 即滿足( )( )( )( )() 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 給定初始點(diǎn)允許誤差置計(jì)算若停止 得解否則 令 從出發(fā) 沿方向作一維搜索 (1)( )( ) 5,:1,2kkkkxxdStepkk令置轉(zhuǎn)10.2 牛頓法10.2.3 修正牛頓法例 用阻尼牛頓法求解下列問(wèn)題421122min( )(1)f xxx xx(1)(1)2(1)(0,0) .,Hessian001(),()212Txf xf x 取初點(diǎn)在該點(diǎn) 函數(shù)的梯度和陣為牛頓方向(1)2(1)1(1)1()()01021220df xf x 10.2 牛頓法(1)(1),xd從出發(fā) 沿方向進(jìn)行一維搜索 令(1)(1)4)=16+1f xd

13、( )= ( 1( )=0=0顯然,用阻尼牛頓法不能產(chǎn)生新點(diǎn), 而點(diǎn)x(1) =(0,0) T并不是問(wèn)題極小點(diǎn).可見(jiàn)從x(1)動(dòng)身,用阻尼牛頓法求不出問(wèn)題的極小點(diǎn), 原因在于 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解決矩陣非正定問(wèn)題的基本思想2( )2( )1(

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

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

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

17、3)2Tf xxxA xx其中A是nn對(duì)稱正定矩陣, x是一個(gè)定點(diǎn).1()()2TxxA xxc是以x為中心的橢球面,( )()0 f xA xxA正定,故x是f(x)的極小值點(diǎn).f(x)的等值面由于10.3共軛梯度法設(shè) x(1)是在某等值面上一點(diǎn),此面在點(diǎn)x(1)處的法向量(1)(1)()()f xA xx又設(shè)d (1)是在該等值面在點(diǎn)x (1)處的一切向量.d (2) = x - x (1)(1)(1)(1)(1),().()0,Tdf xdf x顯然與正交即于是(1)(2)0TdAd 即等值面上一點(diǎn)x(1)處的切向量與由這點(diǎn)指向極小點(diǎn)的向量關(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步 初始化 給定初始點(diǎn)計(jì)算給定一個(gè)搜索方向0,使得0;置步線搜索 求解一維極小化問(wèn)題min若或停止 否則轉(zhuǎn)步3步 計(jì)算共軛方向 計(jì)算一個(gè)非零方向使得(置12 k轉(zhuǎn)步(1)(2)( ),.1.,A1,.03kdddk 設(shè)A是n階對(duì)稱正定矩陣,是 個(gè)共軛的非零向量 則這個(gè)向量組線定理.性無(wú)關(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(擴(kuò)張子空間定理)設(shè)有函數(shù) 其中 是 階對(duì)稱正定矩陣是 共軛的非零向量.以任意的為初始點(diǎn),依次沿進(jìn)行一維搜索 得到點(diǎn)列則是函數(shù)在線性流形 上的唯一極小點(diǎn)特別地 當(dāng)定定理理. . . .(1)( )1(1)(2)( ),( ).,(,),.,. knkiiiiknxf xEx xdddd時(shí)是函數(shù)在上的唯一極小點(diǎn)其中是生成的子空間10.3共軛梯度法(1)(1)(1)(1)( ),( ),().kkkf xxf xxxf x證明:由于嚴(yán)格凸

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

21、ddd由于關(guān)于 共軛 則( )(1)=0 (10.3.11)i TmdAd由二次函數(shù)梯度的表達(dá)式和點(diǎn)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ù)上述證明是在上的極小點(diǎn)由于嚴(yán)格凸故必為此流形上的唯一極小點(diǎn)(1)(2)( )1(1),.,0,.nnnnnkn dddEgxE當(dāng),是的一組基 此時(shí)必有從而是函數(shù)在上的唯一極小點(diǎn)( )1:10.3.2 TjkThgdjk在的條件下, =0, 推論

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

23、.,0 xgdf xgdxxggddd首先, 任意給定一初始點(diǎn),計(jì)算出目標(biāo)函數(shù)在該點(diǎn)的梯度,若,則停止計(jì)算,否則,令沿搜索 得點(diǎn)計(jì)算在處的梯度 若則利用-和構(gòu)造搜索方向,再沿搜索.10.3共軛梯度法( )( )( )(1)(1)( )( )( )( )( )( ) (103.14)()=min ()kkkkkkkkkkkkkxdxdxxdf xdf xd一般地,若已知點(diǎn)和搜索方向, 則從出發(fā),沿進(jìn)行搜索,得其中步長(zhǎng)滿足 ( )( )(1)T( )(1)T( )( )()( )()0 (10.3.15) ()0 kkkkkkf xdf xdAxb d記 令 即k下求 的表達(dá)式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計(jì)算在處的梯度,若,則停止計(jì)算,否則,利用-和構(gòu)造下一搜索方向并使和關(guān)于 共軛,按此設(shè)想.令10.3共軛梯度法 綜上分析,在第一個(gè)搜索方向取負(fù)梯度的前提下,重復(fù)使用公式3.14,3.17-3.19就能伴隨計(jì)算點(diǎn)的增加,構(gòu)造出一組搜索方向.( )( )(1)( )( )( )1k( )1( )

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

26、從而3 成立 對(duì)時(shí)關(guān)系1)和2)成立,從而3)也成立.10.3共軛梯度法設(shè)對(duì)某個(gè)im,這些關(guān)系均成立,我們證明對(duì)于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時(shí)上式為( )(i 1)( )( )1,0,(10.3.21) 0 i Ti TiTiiiTiijidAddAdg ggg當(dāng)時(shí)由歸納假設(shè)根據(jù)10.3共軛梯度法當(dāng)ji時(shí),根據(jù)歸納假設(shè),式(10.3.22)等號(hào)右端各項(xiàng)均為010Tijgg故 再證1),運(yùn)用(10.3.18)和(10.3.20),那么(1)( )( )( )11( )( )1TiTjijiijjTi TjiijdAdgdAdgggdAd 當(dāng)j=i時(shí),把(10.3.19)代入上式第一個(gè)等號(hào)的右端,立得(1)( )0iTjdAd10.3共軛梯度法當(dāng)ji時(shí),由前面已經(jīng)證明的結(jié)論和歸納假設(shè),式中第2個(gè)等

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

29、 ,210 xd 10.3共軛梯度法顯然, 不是目標(biāo)函數(shù)在 處的最速下降方向.(1)d(1)x下面,我們用FR法構(gòu)造兩個(gè)搜索方向.(1)(1),:xd1從出發(fā) 沿方向進(jìn)行搜索,求步長(zhǎng),使?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ā) 沿方向進(jìn)行搜索,求步長(zhǎng),使?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可以驗(yàn)證與關(guān)于 共軛,與關(guān)于 共軛,但與不關(guān)于 共軛,于是,不關(guān)于共軛.10.3共軛梯度法

31、可以證明,對(duì)于正定二次函數(shù),運(yùn)用FR法時(shí)不作矩陣運(yùn)算就能求出因子i定理定理10.3.4 對(duì)于正定二次函數(shù)對(duì)于正定二次函數(shù),FR法中因子法中因子 i具有具有下述表達(dá)式下述表達(dá)式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、法(對(duì)二次凸函數(shù))(1)( )k( )( )(1)1111,1.2,().0, ,. 3,. ,1,0,1(10.3.24). kkkkkkkkkxkgf xgxxdgdkk給定初點(diǎn)置計(jì)算若停止計(jì)算 得點(diǎn)；否則進(jìn)行下一步構(gòu)造搜索方向令其中 當(dāng)時(shí)當(dāng)時(shí)按公式計(jì)算10.3共軛梯度法(1)( )( )(1)4,(10.3.17).5,:1,2kkkkkkxxdknxxkk令 其中按公式計(jì)算步長(zhǎng)若則停止計(jì)算 得點(diǎn) 否則 置轉(zhuǎn)2212min ( )2f xxx例3.2 用FR法求解下列問(wèn)題(1)(5,5)Tx初點(diǎn)10.3共軛梯度法令第一次迭代，目標(biāo)函數(shù)f(x)在點(diǎn)x處的梯度122( )4xf xx(1)1

33、1020dg (1)(1),:xd1從出發(fā) 沿方向進(jìn)行一維搜索 求步長(zhǎng)10.3共軛梯度法(1)11(1)(1)10( 10, 20)205201018( 10, 20)0420TTg ddAd (2)(1)(1)151020/955205/918xxd 第2次迭代目標(biāo)函數(shù)在點(diǎn)x 處的梯度(2)240/920/9g10.3共軛梯度法(2)(1)214100181dgd (2)(2),:xd2從出發(fā) 沿方向作一維搜索 求構(gòu)造搜索方向d .先計(jì)算因子(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顯然點(diǎn)處目標(biāo)函數(shù)的梯度,已達(dá)極小點(diǎn)010.3 共軛梯度法11100 k=0,1,. (10.3.3.1), kkkkkkkkkkxxddgddg其中初始方向步長(zhǎng)參數(shù)由一維搜索得到，的計(jì)算公式通常有如下幾種：一般迭代格式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 給定初始點(diǎn),允許誤差0.置若則停止計(jì)算 否則作一維搜索求滿足 令 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)步可以證明,對(duì)一般函數(shù),共軛梯度法在一定條件下是收斂的,10.3共軛梯度法FR算法中使用精確線搜索，我們有如下收斂性結(jié)果k1:( )Lipschitz.FRArmijo0,0,liminf0(Armijo()()() nkkkkkkkkTkkkfRRf xkggf xdf xcf xd 假設(shè)函數(shù)有下界，梯度是連續(xù)的在共軛梯度法中，步長(zhǎng)參數(shù)是由精確線搜索確定的，并且滿足充分下降條件(即條件).若則 條件:選擇步長(zhǎng)滿

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

38、具有矩陣，同時(shí)具有收斂速度快的優(yōu)點(diǎn)。收斂速度快的優(yōu)點(diǎn)。牛頓法的迭代公式為10.4 擬牛頓法(1)( )( ) (10.4.1)kkkkxxd=( )( )kkdx 其中是在處的牛頓方向( )2( )1( )()()102kkkdf xf x= (.4. )( )k.kx是從出發(fā)沿牛頓方向搜索的最優(yōu)步長(zhǎng)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、點(diǎn)將在點(diǎn)展開(kāi)(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ì)算出和可根據(jù)估計(jì)在處的矩陣的逆令取代牛頓法中的陣的逆則滿足(10.4.8)稱為擬牛頓條件(方程)，也稱為割線方程.怎樣確定滿足這個(gè)條件的H k+1 ?10.4 擬牛頓法( )( )1= (10.4.8)kkkpHq算法 擬牛頓法000011(),(0,1)(),0.2(),3(),(,) |,0, nn nkkkkkkkkkkkkkxRHRgf xkgdH gR x dx xxdxxd初始化 給定初始點(diǎn),正定矩陣,;計(jì)算置平穩(wěn)性檢驗(yàn) 若則停止 否則, 計(jì)算搜索方向線搜索 沿射線進(jìn)行線搜索，求出步長(zhǎng)令10.4 擬牛頓法1114=()

41、,kk kkkkgf xHH(修正擬牛頓方程),計(jì)算對(duì)校正，得使?jié)M足擬牛頓條件，令1，轉(zhuǎn)24. 2 對(duì)稱秩1校正2( )1111(),., ,.kkkkf xnHnHnIHH當(dāng)是 階對(duì)稱正定矩陣時(shí) 滿足擬牛頓條件的矩陣也應(yīng)是 階對(duì)稱矩陣于是 構(gòu)造如此的近似矩陣的一般策略是:取為任意一 階對(duì)稱正定矩陣(如單位陣 ) 然后通過(guò)修正給出令Hk稱為校正矩陣.確定Hk的一個(gè)方法是令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)可寫(xiě)成10.4 擬牛頓法( )(10.4.11),k Tq等號(hào)兩端左乘整理得( )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然后沿方向搜索,求步長(zhǎng),滿足( )( )( )( )0()min()kkkkkf xdf xd 確定后繼點(diǎn)(1)( )( )kkkkxxd(10.4.16)4.3 對(duì)稱秩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 給定初始點(diǎn)允許誤差置計(jì)算出在處的梯度置令從出發(fā) 沿進(jìn)行一維搜索 求使 令),10.4擬牛頓法(1)(1)(1)(1)(1)( )(1)( )( )1115, (),66,2;,77,(),(10.4.18),:1,3kkkkkkkkkkkkStepf xxxStepStepknxxStepSte

45、pStepgf xpxxqggHkkStep 檢驗(yàn)是否滿足收斂準(zhǔn)則 若停止 得否則 轉(zhuǎn)若則令轉(zhuǎn)否則 轉(zhuǎn)令由公式計(jì)算置轉(zhuǎn)例1用DFP方法求解下列問(wèn)題10.4擬牛頓法22121min 242xxx初始點(diǎn)及初始矩陣分別為(1)1210,101 xH12( ,)Txx x在點(diǎn)的梯度124(1)2xgx第1次迭代10.4擬牛頓法(1)x在點(diǎn)處的梯度142g 令搜索方向(1)1142dH g (1)(1),:xd1從出發(fā) 沿方向進(jìn)行一維搜索,求步長(zhǎng)(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計(jì)算(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ā) 沿方向進(jìn)行一維搜索,求步長(zhǎng)(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)造的矩陣為對(duì)稱正定.定矩陣?yán)碜C明:用歸納法 DFP方法中, H1是給定的對(duì)稱正定矩陣.設(shè)Hj是對(duì)稱正定矩陣,下證Hj+1也是對(duì)稱正定矩陣.根據(jù)定義,對(duì)稱性是顯然的,下證正定性(10.4.19)10.4擬牛頓法,nyE對(duì)任意的非零向量有( )( )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又對(duì)稱正定 故存在對(duì)稱正定陣使得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)可寫(xiě)為( )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)右端第一項(xiàng)的分母( )( )( )( )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)不同時(shí)為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方法求解下列問(wèn)題其中A為n階對(duì)稱正定矩陣.取初點(diǎn)x(1) En ,令H1為n階對(duì)稱正定矩陣,則成立:( )( )( )( )1( )(1)( )( )1, 0, 1 (10.4.25)2, , 1 (10.4.26),0,.i TjiikiiiiiipApijkHAppikpxxdkn 其中證明:對(duì)k歸納. k=1時(shí)有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)成立.當(dāng)k=2時(shí),10.4擬牛頓法(1)(2)(1)222(1)(1)22222() 0TTTTpAppAH gg H Apg p 由此結(jié)果,易證k=2時(shí)(10.4.26)亦成立下設(shè)k=m時(shí)(10.4.25-26)成立,下證當(dāng)k=m+1時(shí)上述關(guān)系式也成立.先證k=m+1時(shí)(10.4.25)成立. (1)(1)(2)(

52、),.,.mmppppA與中每一個(gè)關(guān)于 共軛由歸納假設(shè),只需證:由對(duì)(10.4.26)的歸納假設(shè),當(dāng)1im時(shí)有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再證當(dāng)k=m+1時(shí)(10.4.26)成立對(duì)于1im+1有(1)(1)( )21(1)T(1)(1)(1)T( )11(1)T(1)1( )mmTimm

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

54、止性.22( ),0, ( )( )( ),( ).nnnTknfExEmxC xx f xf xyEm yyf x yDFPxfE若 是上的二次連續(xù)可微實(shí)函數(shù) 對(duì)任意的存在常數(shù)使得當(dāng)時(shí)有 則方法產(chǎn)生的序列或終止于或收斂于 在上的唯一極小點(diǎ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)成的對(duì)稱秩校正 故此兩公式的加權(quán)組合仍具有相同的形式顯示表達(dá)式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階對(duì)稱正定矩陣. 則對(duì)于Broyden方法,成立:( )( )( )( )11, 0, 12, , 1i TjiikpApijkHAppik 線搜索方法：每次迭代時(shí)產(chǎn)生一搜索方向，在此方向上進(jìn)行精確或不精確一維搜索，得到下一迭代點(diǎn)。缺點(diǎn)：可能由于步長(zhǎng)過(guò)大導(dǎo)致算法失敗，特別當(dāng)問(wèn)題病態(tài)時(shí)。Ch10.5 信賴域方法主要數(shù)值方法1：主要數(shù)值方法2：信賴域方法： 在每次迭代時(shí)，強(qiáng)制性要求新迭代點(diǎn)與當(dāng)前迭代點(diǎn)之間的距離不超過(guò)某一控制量。實(shí)際上是，在以當(dāng)前迭代點(diǎn)為中心的鄰域內(nèi)對(duì)一近似于原問(wèn)題的簡(jiǎn)單模型求極值。優(yōu)點(diǎn)：算法穩(wěn)定性好、收斂性強(qiáng)。主要內(nèi)容：1 無(wú)約

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

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