應用於最佳化的牛頓法

牛頓法是微積分學中, 通過疊代以求解可微函式 $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矩陣不定或半定的情況下, 收斂更穩定.

參閱

參考文獻

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）.