最優(yōu)化：擬Newton法

1、最優(yōu)化最優(yōu)化主講：劉陶文課件制作：劉陶文課件制作：劉陶文唯楚有材唯楚有材 於斯為盛於斯為盛學(xué)好最優(yōu)化，走遍天下都不怕學(xué)好最優(yōu)化，走遍天下都不怕第四章第四章 無約束問題算法無約束問題算法(II)(II) 擬擬NewtonNewton法法( (變尺度法變尺度法) ) 第一節(jié)第一節(jié) 擬擬NewtonNewton法及其性質(zhì)法及其性質(zhì) 1、擬Newton方程與Dennis-Mor 條件 2、對稱秩1(SR1)修正公式 3、BFGS修正公式與BFGS算法 4、Broyden族算法及其性質(zhì)1 -22)( )( : Hessian:NewtonNewtonkkkkkxfHxfBH或滿足構(gòu)造對稱正定矩陣或法方矩

2、陣且要求其正定需計算克服其缺陷快速收斂性；保持其優(yōu)點法的一種改善法是對擬1 1、擬、擬NewtonNewton法的思想法的思想. )3(Newton, , 0 )2(NewtonNewton )( ) 1 (2易于計算方向為下降方向；使得產(chǎn)生的擬對稱正定方向；方向近似使得產(chǎn)生的擬的要求如下：構(gòu)造kkkkkBBkxfBB(4.1) ),(min nRxxf考慮無約束問題：)Newton( )(- : )Newton( )(-k1-方向擬或方向擬計算搜索方向：kkkkkxfHdxfBd 2 2、擬、擬NewtonNewton方程與方程與Dennis-Mor 條件條件)-)()-(21)-()()(

3、)()( ,Taylor,)(112T11111kkkkTkkkxxxfxxxxxfxfxfxxfxf處的近似二次函數(shù)為在點我們得到展開式利用二次連續(xù)可微設(shè)函數(shù)并求梯度得：令kxx )-)()()(1121kkkkkxxxfxfxf)-()(-)( )(111121kkkkkkkxxBxfxfxfB并取等號得：取代用(4.2) ,-),(-)( 111kkkkkkkkkysBxxsxfxfy上式簡寫成：記. )Newton(Newton)2 . 4(條件或擬方程或割線方程稱為擬方程方程第一擬為而稱方程為第二擬我們稱為方便起見等價地寫成：則若令Newton (4.2),Newton(4.3),

4、(4.3) )2 . 4(,11-11kkkkksyHBH.Newton,)()(HessianNewton)(1 -22矩陣我們稱之為擬的近似或它的逆矩陣法中是或它的逆由于產(chǎn)生的矩陣kkkkxfxfHB方向我們稱之為擬方向的近似顯然該方向是即來計算搜索方向方程組：現(xiàn)在我們通過求解線性Newton ,Newton )(-)(- ,)4 . 4( 0)( 1 -kkkkkkkkxfHxfBddxfdB. ,NewtonNewton即超線性收斂速度收斂速度法保持較快的矩陣的這種近似能使擬擬(4.5) |)(-(|lim .)(,)(,(4.4) )( , , , , :,: 1 . 1 . 4*k

5、kkkkkkkkkkknddxfBxxfxfxxxfdBdkdxxRRf線性收斂當(dāng)且僅當(dāng)超則正定且收斂于設(shè)的解是線性方程組其中過程考察如下迭代二次連續(xù)可微設(shè)函數(shù)定理該定理是擬Newton法具有快速收斂性及良好數(shù)值效果的理論基礎(chǔ)定理的證明：|)o(|)(-(| |)(-)(|)(-(| |)(-(|)()(| 0)(,*2*22*222*kkkkkkkkkkkkkkkkkkddxfBdxfdxfdxfBdxfBdxfxfxfdBxx，則及收斂于充分性：由于. 2 . 5 . 2*xxk超線性收斂于知序列由定理 0|)(-(|lim |)()(|lim ,)5 . 4(,*22kkkkkkkkkd

6、dxfBddxfxf則得到成立若所以 (4.6) 0|-|-|lim , :*1*xxxxxxkkkk即超線性收斂于若必要性|-|-|-|-|-|-|-|-| *1*xxxxxxxdxxxdxxxxkkkkkkkkk由三角不等式可推出(4.7) 1|-|lim )6 . 4(*kkkdxx得：即可從.4.5|)o(|)-o(|)-)(|)-)(-)(-)(|)()(| |)(-(|(4.4)*1*2*2*2*2）成立即得（可得從而由kkkkkkkkkdxxxxxfxxxfxfxfdxfxfdxfB 0|)(-(|lim*2kkkkssxfB可以等價地寫成：注意到)5 . 4( ,-1kkkxx

7、s條件稱為上式或eMor-Dennis)5 . 4(:Newton的計算矩陣在下面我們來介紹擬kB2.1, .Newton)8 . 4( , 0 , ,10或其秩為通常為低秩對稱矩陣其中矩陣序列產(chǎn)生擬然后由修正公式：給定初始對稱正定矩陣kkkkknnBkBBRB法同的擬不同的構(gòu)造方式對應(yīng)不的構(gòu)造方式不是惟一的注意：Newton ,k三類重要的修正公式：修正公式修正公式：對稱秩修正公式：對稱秩 DFP BFGS2 1 SR2 2、對稱秩、對稱秩1 (SR1)1 (SR1)修正公式修正公式 (4.9) - ,)2 . 4(Newton , 1, )8 . 4(1kkkkTkkkTkkkkknkkT

8、kkkkksBysuuuuBBRuRuu得并整理方程將其代入第一擬因而其中則的秩為中選若在kTkkkkTkkkkkkkkkkssBysusByusByu)-(11 , - -|則不妨取上式說明：:1修正公式由此即得對稱秩(4.10) )-()-( )-(1kTkkkTkkkkkkkkssBysBysByBB(4.10) )-()-( )-(1kTkkkTkkkkkkkkssBysBysByBB修正得到：進行對稱秩方程利用第二擬類似地1) 3 . 4(Newton,(4.11) )-()-( )-(1kTkkkTkkkkkkkkyyHsyHsyHsHH比較上述兩式：kkkkysHB 具有二次終止

9、性無需搜索),1( k特點：自對偶性質(zhì)遺傳性質(zhì)：;,kiysBiik不一定成立因缺點：正定性無保證，0)-( kTkkkssBy2 2、 BFGS BFGS 修正公式與修正公式與 BFGS BFGS 算法算法(4.12) - kkkkTkkkkTkkksBysvvbsuua一簡單的取法是兩邊一對的取法不唯一上式中顯然 ,nkkkkRvuRba得并整理方程將其代入第一擬因而其中則的秩為中選若在,)2 . 4(Newton , 2, )8 . 4(1TkkkTkkkkknkkkkTkkkTkkkkkvvbuuaBBRvuRbavvbuua;11 , kTkkTkkkksysuayu得令;11 ,

10、kkTkkTkkkkksBssvbsBv得令(4.12) - kkkkTkkkkTkkksBysvvbsuua得然后再代入將它們代入),8 . 4(k(4.13) 1kTkTkkkkTkkTkkkkksyyysBsBssBBB:BFGS修正公式該公式由：該公式由：Broyden-Fletcher-Goldfarb-Shanno 提出提出BFGS公式是迄今為止最好的擬公式是迄今為止最好的擬Newton修正公式修正公式具有二次終止性精確搜索下,特點：)(,二次且精確遺傳性質(zhì)：kiysBiik較易成立正定性保證 , 0 :kTksy. ,0 .)13. 4(BFGS , 1 . 1 . 311對稱正

11、定時當(dāng)且僅當(dāng)則確定修正公式由對稱正定設(shè)命題kkTkkkBsyBB0. , Newton,11kTkkkTkkTkksysBssyB我們有顯然方程得到則由第一擬對稱正定證明：若nkTkkTkRddBdBsy0, 00 1正定且在下面我們來證明：kTkTkkTkTkkTkkkTkTkTsydyydsBsdBssBddBddBd- BFGS1修正公式得由.0)( ,| | |)()(Schwarz-Cauchy,:2/ 12/ 12/ 12/ 1T22/ 122/ 122/ 12/ 122/ 12/ 1式取等號時上或即當(dāng)且僅當(dāng)不等式得然后由正定有正定分解由于kkkkkkkkkkkkkkTkkkkkk

12、TkkTkkkksdsBdBsBdBsBsdBdsBdBsBBdsBdBBBB0- 221kTkkkTkkTkTkTkkTkTkTkTsysyydsydyyddBddBddBd）（.,0, 0, 11正定即綜上分析knkTBRddBd則若所以,kksd0- ,1kTkTkkTkTkTkTsydyyddBddBddBd否則)(BFGS 1 . 4算法算法. 3 , 1: 6;(4.13 . , ,|)(| , 5; 4; (4.16) 0)( 3; . , ,|)(| 2; 0 . 0, 1111k1k00轉(zhuǎn)步令步）計算否則由公式終止算法則得解若令步由線性搜索計算步長步得解解線性方程組步否則轉(zhuǎn)下

13、一步算法終止則得解若步令精度初始對稱正定矩陣給定初始點步kkBxxfdxxdxfdBxxfkBRxkkkkkkkkkkkn.,BFGS,Newton大幅減少計算量數(shù)算法避免了計算二階導(dǎo)法比較與. 0 , 0 ,3.1.1 , ,BFGS ,)16. 4(kTkksykB要求對所有知進一步由命題是正定的要求矩陣序列是下降的方向算法每一步產(chǎn)生的搜索為確保知由方程? 0 kTksy問題：如何保證析本身以及迭代過程來分分析：從函數(shù) fkkkkkkkkTkdxfxfsxfxfsyT1T1)(-)()(-)( 由于,0,) ( ,)(,)()(-)( Lagrange ) 1 (22T1成立時如一致凸具有

14、某種凸性即正定當(dāng)因此中值定理可知由kTkkkkkkTkkkkkTksyfxfxsdxfssxfxfsy. 0,Powell-Wolfe, . 0)()(1)-( )(-)( )( )( Powell-Wolfe (2)TT2T1T2T1成立搜索時當(dāng)采用因此這里知搜索的第二個條件由kTkkkkkkkkkkkTkkkkksydxfdxfdxfxfsydxfdxf總結(jié)為如下命題：.)(, 2Powell-Wolfe ) 1 (0 , 0 ,. 0)( 4.1.22T正定二次連續(xù)可微且函數(shù)）（搜索或精確搜索；算法中采用則若下面條件之一成立滿足設(shè)命題xfRxfksydxfdnkTkkkk修正公式的改進：

15、BFGS：人們提出一些改進形式為此性是沒有保證的的正定矩陣擬非凸時或目標(biāo)函數(shù)搜索如索算法中使用弱的線性搜當(dāng)在由前面的分析知,Newton,)Armijo( BFGS ,kBf.BFGS關(guān)條件修正公式中使用某種開第一類方法：在 ,0 , Powell1否則如果提出：如kkTkkTkTkkkkTkkTkkkkkBsysyyysBsBssBBB ,|)(| ,Fukushima - LI1否則如果提出：如kkkTkkTkkTkTkkkkTkkTkkkkkBxfsssysyyysBsBssBBB.多樣其它類改進方法：形式0BFGS kTkksyy 確保公式中修改在kTkTkkkkTkkTkkkkksy

16、yysBsBssBBB1:Newton方程為擬上面的公式實際修改了然后得到依據(jù)某種開關(guān)條件取值這里參數(shù) .ktkkkysB1kkTkkkkkyysyyyyTkk , Li-Cheng 2)(提出：如0)( ,)(-)( Fukushima -Li (1)1kkkkkkktstxfxfyy提出：如：修正公正公式的逆修正關(guān)于BFGS(4.13) 1kTkTkkkkTkkTkkkkksyyysBsBssBBB(4.18) - BFGS,(1.16) Morison-Sherman, 11-111-kTkTkkTkTkTkkkkTkTkkkkkkksysssyysIHsyysIHBHBH公式的逆修正公

17、式為：可以得到兩次公式利用及令TkkkkkTkkTkkkTkkkkysI- VsyssVHVH,1 1這里或簡寫成以一小時為限下公式大家可以自己去推導(dǎo)一),18. 4(.,) 1 , 1 (2-21)(min :BFGS 1 . 1 . 40)0(1212221IBxxxxxxxfT初始矩陣其中初始點問題算法求解下面的無約束用精確搜索的例22221222111211212121)(22 0,)(),()(.,2-2-)(ddddxdxddxdxdxfdddxxxxxf即可得精確搜索的步長并令由令解：第一次迭代：2/12 21,12)(,12-)(,11)0(0)0()1(0)0(10)0()0

18、()0(dxxxfBdxfx所以第二次迭代：1B先計算51254-54-10115856-56-1095152-52-54-1001 2-2/ 3)(-)(,2/ 1-1-1(0)1(0(0)1(0Bxfxfyxxs)2(*)2(1)1)1()2(1-1)1(11(1) ,00)( ,24 2 ,121-51254-54-109)( xxxfdxxxfBd從而所以 4 4、BroydenBroyden族及族及DFPDFP算法算法:2,BFGS :Newton1修正公式名的秩我們可以得到另一個著公式的推導(dǎo)類似于方程由第二擬kkksyH(4.20) 1kTkTkkkkTkkTkkkkksyssyH

19、yHyyHHH.DFP,Powell-Fletcher-Davidon修正公式稱為提出該公式由即得到換而公式經(jīng)過簡單的符號交公式可由實際上,BFGSDFP,kkkkysHB :BFGS1kTkTkkkkTkkTkkkkksyyysBsBssBBB公式逆修正公式公式的我們得到公式由類似地DFP ,Morison-Sherman,(4.19) - 1kTkTkkTkTkTkkkkTkTkkksyyysysyIBsysyIBTkkkkkTkkTkkkTkkkksyI- VsyyyVBVB,1 1這里及簡寫形式修正則是數(shù)值穩(wěn)定的而矩陣有時產(chǎn)生數(shù)值上奇異的不穩(wěn)定性修正具有數(shù)值但進一步研究發(fā)現(xiàn)具有相同的性

20、質(zhì)兩者修正公式公式是兩個重要的秩公式和BFGS,Hessian,DFP, .,2BFGSDFP. 3 , 1: 6;(4.20 . , ,|)(| , 5; 4)(- : 3; . , ,|)(| 2; 0 . 0, 1111k1k00轉(zhuǎn)步令步）計算否則由公式終止算法則得解若令步由線性搜索計算步長步解線性方程組計算搜索方向步否則轉(zhuǎn)下一步算法終止則得解若步令精度初始對稱正定矩陣給定初始點步kkHxxfdxxxfHdxxfkHRxkkkkkkkkkkkn)(DFP 2 . 4算法算法.0)( :,)1 . 4(DFPkkkkdxfdBB獲得搜索方向線性方程組然后解計算矩陣算法中也可以先由公式在.217 ,61- ,3224 ,DFP1kkkkHsyH請計算計算出算法求解某問題時假如用思考題：有什么想法沒有？. kH看看我的計算結(jié)果：:DFPBFGS單對偶圖來描述的關(guān)系可以用下面的簡式之間公式及它們的逆修正公公式和關(guān)于)BFGS(1kH)DFP(1kB)DFP(1kH)BFGS(1kB交換交換逆求逆求對偶對偶:Broyden族族矩陣修正公式一類重要的擬公式進行加權(quán)組合得到公式和由互為對偶的Br