此部分內容接《02(a)多元無約束優化問題》！

第二類：牛頓法(Newton method)

\[f({{\mathbf{x}}_{k}}+\mathbf{\delta })\text{ }\approx \text{ }f({{\mathbf{x}}_{k}})+{{\nabla }^{T}}f({{\mathbf{x}}_{k}})\cdot \mathbf{\delta }+\frac{1}{2}{{\mathbf{\delta }}^{T}}\cdot {{\nabla }^{2}}f({{\mathbf{x}}_{k}})\cdot \mathbf{\delta }\]

在${{\mathbf{x}}_{k}}$定了的情況下，$f({{\mathbf{x}}_{k}}+\mathbf{\delta })\text{ }$可以看成是$\mathbf{\delta }$的函數，要使函數達到極小值點，即找出使得函數$f({{\mathbf{x}}_{k}}+\mathbf{\delta })$對$\mathbf{\delta }$的一階導數等于0，則有：

\[\begin{aligned}& f({{\mathbf{x}}_{k}}+\mathbf{\delta }{)}'\text{ }=\nabla f({{\mathbf{x}}_{k}})+{{\nabla }^{2}}f({{\mathbf{x}}_{k}})\cdot \mathbf{\delta } \\& \text{???????????????? =}\nabla f({{\mathbf{x}}_{k}})+H({{\mathbf{x}}_{k}})\cdot \mathbf{\delta }=0 \\\end{aligned}\]

則下降方向可寫為：$\mathbf{\delta }=-{{H}^{-1}}({{\mathbf{x}}_{k}})\cdot \nabla f({{\mathbf{x}}_{k}})$。

(聽課的時候就一直在想，一階導數等于零的點就是極小值點嗎？？？$y=a{{x}^{2}}+bx+c$一種簡單的一元二次函數的一階導數等于0的點，是不是極小值點，還的看$a$的正負呢！)

圖 1?

從上圖中可以看出，在點${{\mathbf{x}}_{k}}$處使函數下降最快的方向是$-\nabla f({{\mathbf{x}}_{k}})$方向，但它卻不是使$f({{\mathbf{x}}_{k}})$最快接近最小值的方向(最快接近最小值方向應該是上圖中紅色虛線的方向)；由此見牛頓法的下降方向：$\mathbf{\delta }=-{{H}^{-1}}({{\mathbf{x}}_{k}})\cdot \nabla f({{\mathbf{x}}_{k}})$，就是在$-\nabla f({{\mathbf{x}}_{k}})$乘上了一個該點Hessian陣的逆${{H}^{-1}}({{\mathbf{x}}_{k}})$；我們希望的是在乘上${{H}^{-1}}({{\mathbf{x}}_{k}})$后使得下降方向朝向上圖中紅色虛線的方向；But，在有些情況下乘上${{H}^{-1}}({{\mathbf{x}}_{k}})$后，不但沒有使函數值$f({{\mathbf{x}}_{k}})$下降，反而讓函數值$f({{\mathbf{x}}_{k}})$變大了。只有當${{H}^{-1}}({{\mathbf{x}}_{k}})$在滿足下面的條件下，才能使函數值不斷減小：

\[\begin{aligned}& {{\left( -\nabla f({{\mathbf{x}}_{k}}) \right)}^{T}}\cdot \left( -{{H}^{-1}}({{\mathbf{x}}_{k}})\cdot \nabla f({{\mathbf{x}}_{k}}) \right)=\left\| -\nabla f({{\mathbf{x}}_{k}}) \right\|\cdot \left\| -{{H}^{-1}}({{\mathbf{x}}_{k}})\cdot \nabla f({{\mathbf{x}}_{k}}) \right\|\cos(\theta ) \\& \text{???????? ?????????????????????????????????????????????=}{{\nabla }^{T}}f({{\mathbf{x}}_{k}})\cdot {{H}^{-1}}({{\mathbf{x}}_{k}})\cdot \nabla f({{\mathbf{x}}_{k}})>0 \\\end{aligned}\]

即要使從新獲得的下降方向$-{{H}^{-1}}({{\mathbf{x}}_{k}})\cdot \nabla f({{\mathbf{x}}_{k}})$與最速下降方向$-\nabla f({{\mathbf{x}}_{k}})$之間的夾角$-{\pi }/{2}\;<\theta <{\pi }/{2}\;$。要滿足：

\[{{\nabla }^{T}}f({{\mathbf{x}}_{k}})\cdot {{H}^{-1}}({{\mathbf{x}}_{k}})\nabla f({{\mathbf{x}}_{k}})>0\]

${{H}^{-1}}({{\mathbf{x}}_{k}})$要達到什么樣的條件呢，由正定二次型的性質可知，當${{H}^{-1}}({{\mathbf{x}}_{k}})$為正定陣(等價于${{H}^{-1}}({{\mathbf{x}}_{k}})\succ 0$的全部特征值大于0)時，式(12)恒成立；當${{H}^{-1}}({{\mathbf{x}}_{k}})$不是正定陣的情況下仍然希望使用牛頓法，則需要對最速下降方向$-\nabla f({{\mathbf{x}}_{k}})$前面乘的Hessian陣的逆${{H}^{-1}}({{\mathbf{x}}_{k}})$進行改進；由于${{H}^{-1}}({{\mathbf{x}}_{k}})$為一個實對稱陣，所以一定能正交分解，這里取${{\lambda }_{1}},{{\lambda }_{2}},...,{{\lambda }_{n}}$從大到小排:

?

\[{{H}^{-1}}({{\mathbf{x}}_{k}})=U\left[ \begin{matrix}{{\lambda }_{1}} & {} & {} & {}? \\{} & {{\lambda }_{2}} & {} & {}? \\{} & {} & \ddots? & {}? \\{} & {} & {} & {{\lambda }_{n}}? \\\end{matrix} \right]{{U}^{T}}\]

具體步驟：

s1：找出${{H}^{-1}}({{\mathbf{x}}_{k}})$的最小特征值:Matlab代碼可寫為$\min (eig({{H}^{-1}}({{\mathbf{x}}_{k}})))=-9.8$;

s2：組合得到一個新的${{\hat{H}}^{-1}}({{\mathbf{x}}_{k}})={{H}^{-1}}({{\mathbf{x}}_{k}})+9.9E$；

\[\begin{aligned}& {{{\hat{H}}}^{-1}}({{\mathbf{x}}_{k}})=U\left[ \begin{matrix}{{\lambda }_{1}} & {} & {} & {}? \\{} & {{\lambda }_{2}} & {} & {}? \\{} & {} & \ddots? & {}? \\{} & {} & {} & -9.8? \\\end{matrix} \right]{{U}^{T}}+9.9UE{{U}^{T}} \\& \text{?????????? }=U\left[ \begin{matrix}{{\lambda }_{1}}+9.9 & {} & {} & {}? \\{} & {{\lambda }_{2}}+9.9 & {} & {}? \\{} & {} & \ddots? & {}? \\{} & {} & {} & 0.1? \\\end{matrix} \right]{{U}^{T}}\succ 0 \\\end{aligned}\]

這里由于$U$為正交陣，故由$U{{U}^{T}}=E$，這樣牛頓法的下降方向可寫為：

\[\mathbf{\delta }=-{{\hat{H}}^{-1}}({{\mathbf{x}}_{k}})\cdot \nabla f({{\mathbf{x}}_{k}})\]

Step3：通過Step2確定下降方向${{\mathbfze8trgl8bvbq}_{k}}$之后，$f({{\mathbf{x}}_{k}}+{{\alpha }_{k}}{{\mathbfze8trgl8bvbq}_{k}})$可以看成${{\alpha }_{k}}$的一維函數，這一步的主要方法有(Dichotomous search, Fibonacci search, Goldensection?search, quadratic interpolation method, and cubic interpolation method)；所確定一個步長${{\alpha }_{k}}>0$，${{\mathbf{x}}_{k+1}}={{\mathbf{x}}_{k}}+{{\alpha }_{k}}{{\mathbfze8trgl8bvbq}_{k}}$；

Step4：?if走一步的距離$\left\| {{\alpha }_{k}}{{\mathbfze8trgl8bvbq}_{k}} \right\|<\varepsilon $，則停止并且輸出解${{\mathbf{x}}_{k+1}}$；else $k:=k+1$并返回Step2，繼續迭代。

?

?

轉載于:https://www.cnblogs.com/duyiExplorer/p/11177053.html

總結

以上是生活随笔為你收集整理的02(c)多元无约束优化问题-牛顿法的全部內容，希望文章能夠幫你解決所遇到的問題。

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