阻尼牛頓法定稿演示

（優(yōu)選）阻尼牛頓法定稿當(dāng)前第1頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)牛頓法

1.基本原理

在第K次迭代的迭代點(diǎn)的鄰域內(nèi)，把展開(kāi)成泰勒級(jí)數(shù)的二次函數(shù)式去近似代替原目標(biāo)函數(shù)，然后求出該二次函數(shù)的極小點(diǎn)，作為對(duì)原目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)，依此類推，通過(guò)多次重復(fù)迭代，使迭代點(diǎn)逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)。

當(dāng)前第2頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn).釋圖：CompanyLogo當(dāng)前第3頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在點(diǎn)按泰勒級(jí)數(shù)展開(kāi)，并取到二次項(xiàng)：當(dāng)前第4頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)對(duì)x求導(dǎo)，其極值點(diǎn)必滿足一階導(dǎo)數(shù)為零，所以，得到式中，為Hessian矩陣的逆矩陣。

當(dāng)前第5頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)

在一般情況下，不一定是二次函數(shù)，因而也不可能是的極值點(diǎn)。但是在點(diǎn)附近，函數(shù)和是近似的，所以可以用點(diǎn)作為下一次迭代，即得

如果目標(biāo)函數(shù)是正定二次函數(shù)，那么是個(gè)常矩陣，逼近式是準(zhǔn)確的。因此由點(diǎn)出發(fā)只要迭代一次既可以求的極小點(diǎn)。

當(dāng)前第6頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)

式與一維搜索公式比較，則有搜索方向，步長(zhǎng)因子

牛頓法的迭代算式其中稱為牛頓方向。當(dāng)前第7頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)2.迭代步驟一給定初始點(diǎn)，計(jì)算精度ε，令k=0；二計(jì)算點(diǎn)的梯度、及其逆矩陣。三構(gòu)造搜索方向當(dāng)前第8頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)

四沿方向進(jìn)行一維搜索，得迭代點(diǎn)五收斂判斷：若，則為近似最優(yōu)點(diǎn)，迭代停止，輸出最優(yōu)解和終止計(jì)算。若不滿足，令k=k+1，轉(zhuǎn)第二步繼續(xù)迭代。當(dāng)前第9頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)。原始牛頓法的特點(diǎn)

若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是完全相同的二次式，其等值線完全重合，故從任一點(diǎn)出發(fā)，一定可以一次達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。

因此，牛頓法是具有二次收斂性的算法。其優(yōu)點(diǎn)是：對(duì)于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，對(duì)于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn)入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。

原始牛頓法的缺點(diǎn)是：由于迭代點(diǎn)的位置是按照極值條件確定的，并未沿函數(shù)值下降方向搜索，因此，對(duì)于非二次函數(shù)，有時(shí)會(huì)使函數(shù)值上升，即f(xk+1)>f(xk)，而使計(jì)算失敗。當(dāng)前第10頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn).當(dāng)前第11頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)3.舉例用牛頓法求函數(shù)的極小值。解：(1)取初始點(diǎn)(2)計(jì)算牛頓方向當(dāng)前第12頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)故(3)極小值當(dāng)前第13頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)

數(shù)學(xué)分析表明，牛頓法具有很好的局部收斂性質(zhì)，對(duì)二次函數(shù)來(lái)說(shuō)，僅一步就達(dá)到優(yōu)化點(diǎn)，但對(duì)一般函數(shù)來(lái)說(shuō)，在一定條件下，當(dāng)初始點(diǎn)的選取充分接近目標(biāo)函數(shù)的極小點(diǎn)時(shí)，有很快的收斂速度，但若初始點(diǎn)選取離最小點(diǎn)比較遠(yuǎn)，就難保證收斂；牛頓法必須求一階、二階導(dǎo)數(shù)及求逆陣，這對(duì)較復(fù)雜的目標(biāo)函數(shù)來(lái)說(shuō)，是較困難的。當(dāng)前第14頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)當(dāng)前第15頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)阻尼牛頓法的迭代公式當(dāng)前第16頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)阻尼牛頓法的計(jì)算過(guò)程和算法框圖當(dāng)前第17頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)當(dāng)前第18頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)當(dāng)前第19頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)當(dāng)前第20頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)阻尼牛頓法計(jì)算框圖當(dāng)前第21頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)阻尼牛頓法算例當(dāng)前第22頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)當(dāng)前第23頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)(3)牛頓方向當(dāng)前第24頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)OK~當(dāng)前第25頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)驗(yàn)證算法的準(zhǔn)確性Fminsearch（）函數(shù)作用是找出使這個(gè)目標(biāo)函數(shù)最小化的x值。當(dāng)前第26頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)當(dāng)前第27頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)首先，注意到時(shí)，所以該問(wèn)題的目標(biāo)函數(shù)有極小值，梯度和Hesse矩陣如下：

梯度，Hesse陣，若取初始點(diǎn)，則對(duì)應(yīng)的梯度，Hesse矩陣的逆此時(shí)牛頓方向不是目標(biāo)函數(shù)的下降方向，牛頓迭代點(diǎn)對(duì)應(yīng)的函數(shù)值，經(jīng)過(guò)數(shù)值實(shí)驗(yàn)可以看出，牛頓法不能求出目標(biāo)函數(shù)的極小值。

求解二維優(yōu)化問(wèn)題當(dāng)前第28頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)另外，當(dāng)沿著方向進(jìn)搜索時(shí)，由于目標(biāo)函數(shù)

所以線搜索的最小點(diǎn)仍為，無(wú)法應(yīng)用阻尼牛頓法解決該問(wèn)題。當(dāng)前第29頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)

求目標(biāo)函數(shù)極小點(diǎn)，初值

此時(shí)Hesse矩陣奇異，故無(wú)法求出它的逆陣，阻尼牛頓法到此不能繼續(xù)進(jìn)行。當(dāng)前第30頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)（阻尼）牛頓法的困難應(yīng)用牛頓法的主要困難是Hesse矩陣可能奇異，或者接近奇異；即使該矩陣是可逆的，它也未必是正定矩陣。此時(shí)，導(dǎo)出的牛頓法迭代格式的二次函數(shù)不一定有極小點(diǎn)，甚至沒(méi)有駐點(diǎn)。為了保證近似目標(biāo)函數(shù)的二次函數(shù)是嚴(yán)格凸的，存在極小點(diǎn)，就需要對(duì)二次函數(shù)的Hesse矩陣進(jìn)行修正。修正牛頓法的基本思想是：在確定搜索方向時(shí)，對(duì)Hesse矩陣增加一個(gè)校正矩陣，使之正定，這樣可以保證搜索方向是目標(biāo)函數(shù)的下降方向。當(dāng)前第31頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)簡(jiǎn)介幾種修正方法當(dāng)前第32頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)牛頓法的效能特點(diǎn)當(dāng)前第33頁(yè)\共有34頁(yè)\編于星期二\15點(diǎn)缺點(diǎn)：