應用於最優化的牛頓法

牛頓法是微積分學中，通過疊代以求解可微函式 $f$ 的零點的一種演算法 (即求 $x$ 使得 $f(x)=0$ ). 而在最佳化中，牛頓法通常被運用於求解一個二次可微函式 $f$ 的一階導數 $f^{\prime }$ 的零點 (即求 $x$ 使得 $f^{\prime }(x)=0$ ), 同時也是 $f$ 的駐點。因此從另一個角度而言，**應用於最佳化的牛頓法**是搜尋函式 $f(x)$ 的最小值或最大值的一種演算法。

 
一維問題的牛頓法主要步驟如下:
取一個點 $x_{0}$ 為**初值**, 依如下公式**疊代**:

　
: $x_{n+1}=x_{n}-{\frac {f^{\prime }(x_{n})}{f^{\prime \prime }(x_{n})}},$

直至滿足一定條件 (如 $f^{\prime }(x_{n})=0$ 或 $x_{n+1}-x_{n}<\varepsilon $ , 其中 $\varepsilon $ 為一個給定的足夠小的常數) 後，演算法終止。

 

## 方法描述

在一維問題中，牛頓法將構造一個以 $x_{0}$ 為首項，收斂到 $x^{*}$ 的數列 $\{x_{n}\}$ , 其中 $x^{*}$ 使得 $f^{\prime }(x^{*})=0$ 成立.

 $f(x)$ 在 $x=x_{n}$ 處的二階泰勒展開式 $f_{T}(x)$ 為:

　
: $f_{T}(x)=f_{T}(x_{n}+\Delta x)\approx f(x_{n})+f^{\prime }(x_{n})\Delta x+{\frac {1}{2}}f^{\prime \prime }(x_{n})\Delta x^{2}.$

我們希望找到 $\Delta x$ 使 $x_{n}+\Delta x$ 為 $f_{T}(x)$ 的一個駐點。則將上式對 $\Delta x$ 進行求導:

　
: $0={\frac {\text{d}}{{\text{d}}\Delta x}}(f(x_{n})+f^{\prime }(x_{n})\Delta x+{\frac {1}{2}}f^{\prime \prime }(x_{n})\Delta x^{2})=f^{\prime }(x_{n})+f^{\prime \prime }(x_{n})\Delta x.$

上述方程式的解 $\Delta x=-{\frac {f^{\prime }(x_{n})}{f^{\prime \prime }(x_{n})}}$ 滿足

　
: $x_{n+1}=x_{n}+\Delta x=x_{n}-{\frac {f^{\prime }(x_{n})}{f^{\prime \prime }(x_{n})}}$

收斂於 $f_{T}(x)$ 的駐點 $x^{*}$ .

## 幾何意義

牛頓法的幾何意義為：在每一次疊代中，均以一個二次函式去逼近 $f(x)$ . 具體而言: 
在一維問題中，已知 $x_{n}$ , $f(x_{n})$ , $f^{\prime }(x_{n})$ 及 $f^{\prime \prime }(x_{n})$ , 設二次函式表逹式為 $ax^{2}+bx+c$ , 依下列方程式求解未知數 $a,\ b,\ c,$

　
: $ax_{n}^{2}+bx_{n}+c=f(x_{n}),$

　
: $2ax_{n}+b=f^{\prime }(x_{n}),$

　
: $2a=f^{\prime \prime }(x_{n}).$

然後二次函式 $ax^{2}+bx+c$ 的極值點即為下一個疊代點，

　
: $x_{n+1}=-{\frac {b}{2a}}.$

而在高維問題中，上述的極值點也可以是鞍點。值得一提的是，如果 $f(x)$ 恰為一個二次函式，則其極值點只需一次疊代中即可找到.

 

## 高維問題求解

上述的一維問題的疊代法可以被推廣至多維問題。只需將導數替換為梯度 ( $\nabla f(x)$ ), 並將二階導數的倒數替換為 Hessian 矩陣的逆矩陣 ( $\mathbf {H} f(x)$ ), 即:

　
: $x_{n+1}=x_{n}-[\mathbf {H} f(x_{n})]^{-1}\nabla f(x_{n}),n\geq 0.$

通常，使用牛頓法時會加入一個步長變數 $\gamma \in (0,1)$ 作微調以使每一步疊代都滿足 Wolfe 條件，即，

　
: $x_{n+1}=x_{n}-\gamma [\mathbf {H} f(x_{n})]^{-1}\nabla f(x_{n}).$

這個方法被稱為**無約束牛頓法**, 通常用於第一步之後的疊代.

只要牛頓法適用，其收斂於最小值或最大值的速度均頗快於最速下降法。事實上，對於每一個極小值，都存在一個鄰域 $N$ 使得，只要 Hessian 矩陣是可逆的且是一個關於 $x\in N$ 的 Lipschitz 連續函式，以 $x_{0}\in N$ 為初值，步長 $\gamma =1$ 的牛頓法是**二次收斂**的.

 

求一個高維問題的 Hessian 矩陣的逆矩陣是一件頗費工夫的事情。在實際應用中，通常會用向量 $\Delta x=x_{n+1}-x_{n}$ 作為線性方程組

　
: $[\mathbf {H} f(x_{n})]\Delta x=-\nabla f(x_{n})$

的解。這個求解過程中，透過使用各種矩陣分解方法同近似求解方法，求解速度可以大大提升。然而，這些矩陣分解方法或近似求解方法的使用需要滿足一定條件；例如，Cholesky 分解同共軛梯度法只有在 $\mathbf {H} f(x)$ 是正定矩陣時才適用。這看似是一個限制，但有時也能充當檢定答案的工具；例如，在一個最小化問題 ( ${\text{min  }}f(x)$ ) 中，求出一個 $x^{\prime }$ 使得 $\nabla f(x^{\prime })=0$ 但 $\mathbf {H} f(x)$ 不是正定矩陣，那麽 $(x^{\prime },f(x^{\prime }))$ 只是 $f(x)$ 的一個鞍點而非極小值點.

 
另一方面，一個有約束的問題的求解過程可能會遇到**當前解**陷入一個鞍點的情況，這時的 Hessian 矩陣是對稱不定的；此時則要使用其他方法，例如 Cholesky 分解的 $\mathbf {LDL} ^{\mathbf {T} }$ 變形或共軛梯度法等的方法，來疊代得出 $x_{n+1}$ .

 
此外，為規避求 Hessian 矩陣的繁瑣，也存在多種擬牛頓法，通過調整梯度以求出 Hessian 矩陣的近似.

 
如果 Hessian 矩陣 $\mathbf {H} f(x)$ 接近一個奇異矩陣，則其逆矩陣會變得數值不穩定且疊代不會收斂。此種情形下，前人探索出了很多成功的方法來解決問題。目標之一是通過引入**修正矩陣** $B_{n}$ 使得 $\mathbf {H} f(x_{n}):=\mathbf {H} f(x_{n})+B_{n}$ 是對稱正定的。其中一種方法是將 $\mathbf {H} f(x_{n})$ 對角化，選擇 $B_{n}$ 使 $\mathbf {H} f(x_{n})+B_{n}$ 有相同的特徵向量，但每一個 $\mathbf {H} f(x_{n})$ 的負特徵值都被替換成 $\epsilon >0.$

 
一個應用於萊文貝格－馬夸特方法 (其中用到了近似的 Hessian 矩陣) 的方法是引入一個帶係數的單位矩陣 $\mu \mathbf {I} $ , 係數在每一步疊代中調整。對於較大的 $\mu $ 及較小的 Hessian 矩陣，疊代將變得與以 $\mu ^{-1}$ 為步長的最速下降法相似，這將使得疊代收斂變慢，但在 Hessian 矩陣不定或半定的情況下，收斂更穩定.

## 參閱

* 擬牛頓法
* 最速下降法
* 高斯–牛頓演算法
* 萊文貝格－馬夸特方法
* 置信域方法
* 最佳化
* Nelder–Mead 方法

## 參考文獻

* Avriel, Mordecai. Nonlinear Programming: Analysis and Methods. Dover Publishing. 2003. ISBN 0-486-43227-0.
* Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. Numerical optimization: Theoretical and practical aspects. Universitext Second revised ed. of translation of 1997 French. Berlin: Springer-Verlag. 2006: xiv+490 [2017-08-07]. ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5. （原始內容存檔於 2013-07-19）.
* Fletcher, Roger. Practical methods of optimization 2nd. New York: John Wiley & Sons. 1987. ISBN 978-0-471-91547-8.
* Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. Springer-Verlag. 1999. ISBN 0-387-98793-2.

## 外部連結

* Korenblum, Daniel. Newton-Raphson visualization (1D). Bl.ocks. Aug 29, 2015 [2017-08-07]. ffe9653768cb80dfc0da. （原始內容存檔於 2014-07-14）.