一、牛頓法存在的問題

????在單變量的情況下，如果函數的二階導數f′′<0，牛頓法就無法收斂到極小點。類似的，在多變量的情況下，目標函數的hessian矩陣F(x(k))非正定，牛頓法的搜索方向并不一定是目標函數值的下降方向。甚至在某些情況下F(x(k))>0， 牛頓法也不具有下降特性。比如，當初始點遠離目標函數極小值點時，就有可能出現這種情況。
????牛頓法雖然有上述缺陷，但是如果初始點離極小值點比較近，牛頓法將表現出相當好的收斂特性。

二、兩個定理

????首先選定目標函數為二次型函數f,牛頓法只需一次迭代就可以從任意點收斂到極小點。令目標函數如下：
f(x)=12xTQx?xTb
它的梯度和hessian矩陣分別是：

g(x)=?f(x)=Qx?bF(x)=Q
當 ?f(x)=0時，可求得 f的極小值點x?，且 x?=Q?1b。
利用牛頓法迭代公式可得：
x(1)=x(0)?F(x(0))?1g(x(0))=x(0)?Q?1[Qx(0)?b]=Q?1b=x?
下邊直接給出定理1：
定理1 函數f三階連續可微，點x?∈Rn滿足?f(x?)=0, 且F(x?) 可逆，那么對于所有與x?,足夠接近的x(0), 牛頓法能夠正常運行，且至少以階數2的收斂率收斂到x?。

????上述定理證明略過。上述定理說明如果初始點離極小值點比較近，牛頓法將表現出相當好的收斂特性。否則，可能導致hessian矩陣為奇異矩陣，方法失效。

先給出定理2，然后再解決上述問題。
定理2 {x(k)}是為利用牛頓法求解目標函數f(x)極小點時得到的迭代點序列，如果F(x(k))>0且g(x(k))=?f(x(k))≠0,那么從點x(k)到點x(k+1)的搜索方向

d(k)=?F(x(k))?1g(x(k))=x(k+1)?x(k)
是一個下降方向，即存在一個aˉ>0,使得對于所有α∈(0,aˉ), 都有
f(x(k)+αd(k))<f(x(k))
成立。

三、牛頓法的修正

????根據定理2， 可以對牛頓法的修正如下：

x(k+1)=x(k)?αkF(x(k))?1g(x(k))
其中，
αk=argminα≥0f(x(k)?αF(x(k))?1g(x(k)))
也就是說，每一次的迭代都在方向 ?F(x(k))?1g(x(k)))上開展一次一維搜索，由此確定每次搜索的步長。修正的牛頓法具有下降特性，當 g(x(k))≠0時，有：
f(x(k+1))<f(x(k))

四、修正后存在的問題

????當目標函數維數比較大時，計算hessian矩陣需要計算量比較大，況且還要求解線性方程組F(x(k))d(k)=?g(x(k)),這個問題后續繼續討論。
????牛頓法隱含的另外一個問題是hessian矩陣可能不是正定矩陣。

總結

以上是生活随笔為你收集整理的最优化学习笔记（六）——牛顿法性质分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。