阻尼牛頓法定稿[中小學(xué)堂]

1、LOGO 牛頓法與阻尼牛頓法牛頓法與阻尼牛頓法 團(tuán)隊(duì)成員：崔尚 金英博 郭向姝 多麗婭 趙麗霞 竇永貴 尹遜增 宋紅喜 陳建 王思遠(yuǎn) 馮文秀 牛頓法主講：崔尚 阻尼牛頓法主講：金英博 牛頓法牛頓法 1.1.基本原理基本原理 在第在第K K次迭代的迭代點(diǎn)次迭代的迭代點(diǎn) 的鄰域內(nèi)，把的鄰域內(nèi)，把 展開成展開成 泰勒級數(shù)的泰勒級數(shù)的二次函數(shù)式二次函數(shù)式去近似代替原目標(biāo)函數(shù)去近似代替原目標(biāo)函數(shù) ，然后，然后 求出該求出該二次函數(shù)二次函數(shù)的極小點(diǎn)，作為對原目標(biāo)函數(shù)求優(yōu)的下一個的極小點(diǎn)，作為對原目標(biāo)函數(shù)求優(yōu)的下一個 迭代點(diǎn)迭代點(diǎn)，依此類推，通過多次重復(fù)迭代，使迭代點(diǎn)逐步逼近，依此類推，通過多次重復(fù)迭代，使

2、迭代點(diǎn)逐步逼近 原目標(biāo)函數(shù)的極小點(diǎn)。原目標(biāo)函數(shù)的極小點(diǎn)。 )(k x )(xF )(xF 2課堂特制 . 釋圖： 3課堂特制 設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在點(diǎn)設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在點(diǎn) 按按 泰勒級數(shù)展開，并取到二次項(xiàng)：泰勒級數(shù)展開，并取到二次項(xiàng)： )(k x )()( 2 1 )()()()()( )()()( )()()()( kkTk kTkkk xxxHxx xxxfxfxxf 4課堂特制 對對x x求導(dǎo)，其極值點(diǎn)必滿足一階導(dǎo)數(shù)為零，所以，求導(dǎo)，其極值點(diǎn)必滿足一階導(dǎo)數(shù)為零，所以， 得到得到 式中，式中， 為為HessianHessian矩陣的逆矩陣。矩陣的逆矩陣。 0

3、)()( )( )( )()()( kkk xHxxxf x xf x )()( )( 1 )()( min kkk xfxHxx 1 )( )( k xH 1 5課堂特制 )(xf min x )(xf )(k x )1( k x )(x )(xf )(xf )()( )( 1 )()(1kkkk xfxHxx 2 )(xH )(k x )(xf 1 6 課堂特制課堂特制 式與一維搜索公式 比較，則有搜索方向 ， 步長因子 )()()()1(kkkk sxx )()( )( 1 )()(kTkk xfxHs 1 )( k 2 )()()1( )( 1 )()( )()( kkk kkk sx

4、x xfxHs 牛頓法的牛頓法的 迭代算式迭代算式 其中其中 稱為稱為牛頓方向。牛頓方向。 )(k S 7 課堂特制課堂特制 2.2.迭代步驟迭代步驟 一一 給定給定初始點(diǎn)初始點(diǎn) ，計算精度，計算精度，令，令k=0k=0； 二二 計算計算 點(diǎn)的梯度點(diǎn)的梯度 、 及其逆矩陣及其逆矩陣 。 三三 構(gòu)造搜索方向構(gòu)造搜索方向 )0( x )(k x)( )(k xf)( )(k xH 1 )( )( k xH )()( )( 1 )()(kkk xfxHs 8課堂特制 四四 沿沿 方向進(jìn)行一維搜索，得迭代點(diǎn)方向進(jìn)行一維搜索，得迭代點(diǎn) 五五 收斂判斷：收斂判斷： 若若 ，則，則 為近似最優(yōu)點(diǎn)，迭代停止，

5、為近似最優(yōu)點(diǎn)，迭代停止， 輸出最優(yōu)解輸出最優(yōu)解 和和 終止計算。終止計算。 若不滿足，令若不滿足，令k=k+1，轉(zhuǎn)第二步繼續(xù)迭代。，轉(zhuǎn)第二步繼續(xù)迭代。 )(k s )()()1(kkk sxx )( )1(k xf )1( k x )1( min k xx )()( )1( min k xfxf 9課堂特制 原始牛頓法的特點(diǎn)原始牛頓法的特點(diǎn) 若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解， 則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是完全相同的二次式，則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是完全相同的二次式， 其等值線完全重合，故從任一點(diǎn)出發(fā)，一定可以一次其等值線完全重合，故從任一點(diǎn)出

6、發(fā)，一定可以一次 達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。 因此，牛頓法是具有二次收斂性的算法。其因此，牛頓法是具有二次收斂性的算法。其優(yōu)點(diǎn)優(yōu)點(diǎn) 是：對于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，是：對于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解， 對于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn)對于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn) 入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。 原始牛頓法的原始牛頓法的缺點(diǎn)缺點(diǎn)是：由于迭代點(diǎn)的位置是按照是：由于迭代點(diǎn)的位置是按照 極值條件確定的，并未沿函數(shù)值下降方向搜索，因此，極值條件確定的，并未沿函數(shù)值下降方向搜索，因此

7、， 對于非二次函數(shù)，有時會使函數(shù)值上升，即對于非二次函數(shù)，有時會使函數(shù)值上升，即 f(xk+1) f(xk)，而使計算失敗。，而使計算失敗。 10課堂特制 . 11課堂特制 3.3.舉例舉例 用牛頓法求函數(shù)用牛頓法求函數(shù) 的極小值。的極小值。 60410)( 2121 2 2 2 1 xxxxxxxf 解：解： (1)(1)取初始點(diǎn)取初始點(diǎn) (2)(2)計算牛頓方向計算牛頓方向 0 0 )0( x 4 10 42 102 )( )0( 12 21 xx xx xx xf 12課堂特制 21 12 )( 2 2 2 12 2 21 2 2 1 2 )0( x f xx f xx f x f xH

8、 21 12 3 1 )( 1 )0( xH 6 8 18 24 3 1 4 10 21 12 3 1 )()( )0( 1 )0()0( xfxHs 故故 (3)(3)極小值極小值 8)(min 6 8 6 8 0 0 )0()0(1 xf sxx 13課堂特制 數(shù)學(xué)分析表明，牛頓法具有很好的局部收斂性質(zhì)，對數(shù)學(xué)分析表明，牛頓法具有很好的局部收斂性質(zhì)，對 二次函數(shù)來說，僅一步就達(dá)到優(yōu)化點(diǎn)，二次函數(shù)來說，僅一步就達(dá)到優(yōu)化點(diǎn)， 但對一般函數(shù)來說，在一定條件下，當(dāng)初始點(diǎn)的選取但對一般函數(shù)來說，在一定條件下，當(dāng)初始點(diǎn)的選取 充分接近目標(biāo)函數(shù)的極小點(diǎn)時，有很快的收斂速度，但若充分接近目標(biāo)函數(shù)的極小點(diǎn)時

9、，有很快的收斂速度，但若 初始點(diǎn)選取離最小點(diǎn)比較遠(yuǎn)，就難保證收斂；初始點(diǎn)選取離最小點(diǎn)比較遠(yuǎn)，就難保證收斂； 牛頓法必須求一階、二階導(dǎo)數(shù)及求逆陣，這對較復(fù)雜牛頓法必須求一階、二階導(dǎo)數(shù)及求逆陣，這對較復(fù)雜 的目標(biāo)函數(shù)來說，是較困難的。的目標(biāo)函數(shù)來說，是較困難的。 14課堂特制 1 ()() ()() kk f Xf X 牛頓法的缺點(diǎn)：由于迭代公式中沒有 步長因子，而是定步長迭代，對于非二次 型目標(biāo)函數(shù)，有時會使函數(shù)值上升，即出 現(xiàn)的情況，這表明牛頓 法不能保證函數(shù)值穩(wěn)定的下降，有時甚至 迭代發(fā)散，從而導(dǎo)致計算失敗。 為了消除牛頓法的弊病，提出了”阻尼 牛頓法。 15課堂特制 阻尼牛頓法的迭代公式阻

10、尼牛頓法的迭代公式 1 11 ()()() () ()()() ()()()()() () )() , min )() kkk k kkk kkkkk k SH Xf X fXS XXH Xf X 阻尼牛頓法的迭代方向依然與牛頓法一樣，采用牛 頓方向： -（ 但每次迭代需沿此方向作一維搜索，求其最優(yōu)步長因子 使得 將牛頓法的迭代公式改為 （ 此即阻尼牛頓法的迭代公式。稱為阻尼因子，通 () () ) k f X H X 過牛頓方向進(jìn)行一維搜索獲得。當(dāng)目標(biāo)函數(shù)的赫 森矩陣 （處處正定時，阻尼牛頓法能保證每次迭 代點(diǎn)的目標(biāo)函數(shù)值均為下降，從而保持了二次收斂的 特性。 16課堂特制 阻尼牛頓法的計算

11、過程和算法框阻尼牛頓法的計算過程和算法框 圖圖 0 (1) (2) 0k () , n XR n 阻尼牛頓法的具體迭代步驟如下： 給定初始點(diǎn)迭代精度 ， 維數(shù) 。 置 17課堂特制 12 222 12 (3) () ()()() () ()()() () ()()() (), ()()() ()()()() k kkk kT n kkk k n X fXfXfX fX xxx fXfXfX fX xxx 計算迭代點(diǎn)的梯度 計算梯度的模 18課堂特制 1 1 (4) 5 6 () ()* ()* ()()() ()()() () () ()() ( )(),() () )() k k k kkk

12、 kkk k f X XX f Xf X XH XHX SH Xf X X 檢驗(yàn)是否滿足迭代終止條件？ 若滿足，停止迭代，輸出最優(yōu)解：， 。否則進(jìn)行下一步。 計算處的并求其逆。 計算牛頓方向 -（ 從點(diǎn)出發(fā)，沿牛頓方向進(jìn)行一維搜索求最優(yōu) () ()()() , min k kkk fXS 步 長使得 19課堂特制 (k+1)(k)(k)(k) (7) XXS 計算迭代新點(diǎn) = (8) 13,( )kk 置返回步驟進(jìn)行下一次 迭代計算。 12 222 12 (3) () ()()() () ()()() () ()()() (), ()()() ()()()() k kkk kT n kkk k

13、 n X f Xf Xf X f X xxx f Xf Xf X f X xxx 計算迭代點(diǎn)的梯度 計算梯度的模 20課堂特制 阻尼牛頓法計算框圖阻尼牛頓法計算框圖 否 停 1()()()()kkkk XSX ()() (),() kk f Xf X計算： () ()? k f X 1kk 0 k0 () ,Xn給定初始值：，。置 。 ()()()() ,min kkkk fXS求使得 ()* ()* ()() k k XX f Xf X 輸出：， 。 是 1() () k HX 計算： 1 ()()() )() kkk H Xf XS -（ 21課堂特制 阻尼牛頓法算例阻尼牛頓法算例 22

14、1212 (0) ()4(1)2(2)10 0 00.01 fxxxx, , T X X 已知目標(biāo)函數(shù) 設(shè)初始點(diǎn)迭代梯度精度 ，試用阻尼牛頓 法求目標(biāo)函數(shù)的極小點(diǎn)和極小值。 22課堂特制 )(),( )()(kk XfXf計算 22)0( 79)(Xf ）（XH ）（01 計算 7 7 23課堂特制 )()( ) 0 (1) 0 () 0 ( XfXHS T XfXHS 4 7 8 9 7 9 4/10 08/1 )()( )0(100 (3) 牛頓方向 7 7 10 4 7 8 9 )2 4 7 (2)1 8 9 (4)( 22 aaaaaf 24課堂特制 7 7 8125.10 ?)( )

15、 1 ( Xf 25課堂特制 驗(yàn)證算法的準(zhǔn)確性驗(yàn)證算法的準(zhǔn)確性 Fminsearch（）函數(shù)作 用是找出使這個目標(biāo)函數(shù) 最小化的x值。 26課堂特制 27課堂特制 首先，注意到 時， 所以該問題的目標(biāo)函 數(shù)有極小值，梯度和Hesse矩陣如下： 梯度 ，Hesse陣 ，若取初始點(diǎn) ，則對應(yīng)的梯度 ， Hesse矩陣的逆 此時牛頓方向 不是目標(biāo)函數(shù)的下降方向，牛頓迭代點(diǎn) 對應(yīng)的 函數(shù)值 ，經(jīng)過數(shù)值實(shí)驗(yàn)可以看出，牛 頓法不能求出目標(biāo)函數(shù)的極小值。 求解二維優(yōu)化問題求解二維優(yōu)化問題 2 221 4 1 )1 ()(minxxxxxf x)( xf )1(2 4 )( 21 2 3 1 xx xx xf

16、 21 112 )( 2 12 x xf T x0 , 0 0 T xf)2 , 0()( 01 12 )( 12 xfT S)0 , 2( 0 T x)0 , 2( 1 1)(17)( 01 xfxf 28課堂特制 另外，當(dāng)沿著方向 進(jìn)搜索時，由于目標(biāo)函數(shù) 所以線搜索的最小點(diǎn)仍為 ，無法應(yīng)用阻尼牛頓法解決 該問題。 0 S 116)( 400 aaSxf 0 x 0 )( da adf 0a )0()0()0()0()1( XSaXX 29課堂特制 求目標(biāo)函數(shù) 極小點(diǎn)，初值 此時Hesse矩陣奇異，故無法求出它的逆陣，阻尼牛頓法到 此不能繼續(xù)進(jìn)行。 2 2 3 1 xxy 2 2 1 2 3

17、 )( x x xf 20 00 20 06 )( 1)0(2 x xf T x0 , 0 0 30課堂特制 （阻尼）牛頓法的困難（阻尼）牛頓法的困難 應(yīng)用牛頓法的主要困難是Hesse矩陣可能奇異，或 者接近奇異；即使該矩陣是可逆的，它也未必是 正定矩陣。此時，導(dǎo)出的牛頓法迭代格式的二次 函數(shù)不一定有極小點(diǎn)，甚至沒有駐點(diǎn)。為了保證為了保證 近似目標(biāo)函數(shù)的二次函數(shù)是嚴(yán)格凸的，存在極小近似目標(biāo)函數(shù)的二次函數(shù)是嚴(yán)格凸的，存在極小 點(diǎn)，就需要對二次函數(shù)的點(diǎn)，就需要對二次函數(shù)的Hesse矩陣進(jìn)行修正。矩陣進(jìn)行修正。 修正牛頓法的基本思想是：在確定搜索方向時， 對Hesse矩陣增加一個校正矩陣，使之正定，這樣 可以保證搜索方向是目標(biāo)函數(shù)的下降方向目標(biāo)函數(shù)的下降方向。 31課堂特制 簡介幾種修正方法簡介幾種修正方法 32課堂特制 牛頓法的效能特點(diǎn)牛頓法的效能特點(diǎn) 牛頓 而牛頓法不僅使用函數(shù) 法具有二次收斂性 的一階導(dǎo)數(shù)，還進(jìn)一步 利用了二階導(dǎo)數(shù)，較好的考慮了梯度的變化趨勢， 因而能夠更全面的確定合適的搜索方向