1、牛頓法與阻尼牛頓法,團隊成員：崔尚 金英博 郭向姝 多麗婭 趙麗霞 竇永貴 尹遜增 宋紅喜 陳建 王思遠 馮文秀 牛頓法主講：崔尚 阻尼牛頓法主講：金英博,.,2,牛頓法 1.基本原理 在第K次迭代的迭代點 的鄰域內(nèi)，把 展開成泰勒級數(shù)的二次函數(shù)式去近似代替原目標函數(shù) ，然后求出該二次函數(shù)的極小點，作為對原目標函數(shù)求優(yōu)的下一個迭代點，依此類推，通過多次重復迭代，使迭代點逐步逼近原目標函數(shù)的極小點。,.,3,.,釋圖：,.,4,設目標函數(shù)是連續(xù)二階可微的，將函數(shù)在點 按泰勒級數(shù)展開，并取到二次項：,.,5,對x求導，其極值點必滿足一階導數(shù)為零，所以， 得到 式中， 為Hessian矩陣的逆矩陣。

2、,.,6,在一般情況下， 不一定是二次函數(shù)，因而 也不可能是 的極值點。但是在 點附近，函數(shù) 和 是近似的，所以可以用 點作為下一次迭代，即得 如果目標函數(shù) 是正定二次函數(shù)，那么 是個常矩陣，逼近式 是準確的。因此由 點出發(fā)只要迭代一次既可以求 的極小點。,.,7,式與一維搜索公式 比較，則有搜索方向 ， 步長因子,牛頓法的迭代算式,其中 稱為牛頓方向。,.,8,2.迭代步驟 一 給定初始點 ，計算精度，令k=0； 二 計算 點的梯度 、 及其逆矩陣 。 三 構造搜索方向,.,9,四 沿 方向進行一維搜索，得迭代點 五 收斂判斷： 若 ，則 為近似最優(yōu)點，迭代停止， 輸出最優(yōu)解 和 終止計算。

3、 若不滿足，令k=k+1，轉第二步繼續(xù)迭代。,.,10,。,原始牛頓法的特點 若用原始牛頓法求某二次目標函數(shù)的最優(yōu)解，則構造的逼近函數(shù)與原目標函數(shù)是完全相同的二次式，其等值線完全重合，故從任一點出發(fā)，一定可以一次達到目標函數(shù)的極小點。 因此，牛頓法是具有二次收斂性的算法。其優(yōu)點是：對于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，對于非二次函數(shù)，若函數(shù)二次性較強或迭代點已經(jīng)進入最優(yōu)點的較小鄰域，則收斂速度也很快。 原始牛頓法的缺點是：由于迭代點的位置是按照極值條件確定的，并未沿函數(shù)值下降方向搜索，因此，對于非二次函數(shù)，有時會使函數(shù)值上升，即 f(xk+1) f(xk)，而使計算失敗。,.,11,.,

4、.,12,3.舉例 用牛頓法求函數(shù) 的極小值。,解： (1)取初始點 (2)計算牛頓方向,.,13,故,(3)極小值,.,14,數(shù)學分析表明，牛頓法具有很好的局部收斂性質(zhì)，對二次函數(shù)來說，僅一步就達到優(yōu)化點， 但對一般函數(shù)來說，在一定條件下，當初始點的選取充分接近目標函數(shù)的極小點時，有很快的收斂速度，但若初始點選取離最小點比較遠，就難保證收斂； 牛頓法必須求一階、二階導數(shù)及求逆陣，這對較復雜的目標函數(shù)來說，是較困難的。,.,15,.,16,阻尼牛頓法的迭代公式,.,17,阻尼牛頓法的計算過程和算法框圖,.,18,.,19,.,20,.,21,阻尼牛頓法計算框圖,.,22,阻尼牛頓法算例,.,2

5、3,.,24,(3) 牛頓方向,.,25,OK,.,26,驗證算法的準確性,Fminsearch（）函數(shù)作用是找出使這個目標函數(shù)最小化的x值。,.,27,.,28,首先，注意到 時， 所以該問題的目標函數(shù)有極小值，梯度和Hesse矩陣如下： 梯度 ，Hesse陣 ，若取初始點 ，則對應的梯度 ， Hesse矩陣的逆 此時牛頓方向 不是目標函數(shù)的下降方向，牛頓迭代點 對應的函數(shù)值 ，經(jīng)過數(shù)值實驗可以看出，牛頓法不能求出目標函數(shù)的極小值。,求解二維優(yōu)化問題,.,29,另外，當沿著方向 進搜索時，由于目標函數(shù) 所以線搜索的最小點仍為 ，無法應用阻尼牛頓法解決該問題。,.,30,求目標函數(shù) 極小點，初

6、值 此時Hesse矩陣奇異，故無法求出它的逆陣，阻尼牛頓法到此不能繼續(xù)進行。,.,31,（阻尼）牛頓法的困難,應用牛頓法的主要困難是Hesse矩陣可能奇異，或者接近奇異；即使該矩陣是可逆的，它也未必是正定矩陣。此時，導出的牛頓法迭代格式的二次函數(shù)不一定有極小點，甚至沒有駐點。為了保證近似目標函數(shù)的二次函數(shù)是嚴格凸的，存在極小點，就需要對二次函數(shù)的Hesse矩陣進行修正。修正牛頓法的基本思想是：在確定搜索方向時，對Hesse矩陣增加一個校正矩陣，使之正定，這樣可以保證搜索方向是目標函數(shù)的下降方向。,.,32,簡介幾種修正方法,.,33,牛頓法的效能特點,.,34,缺點： 1. 對目標函數(shù)要求高。函數(shù)必須具有連續(xù)的一階、二階偏導數(shù)。同時其赫森矩陣必須正定且