擬牛頓法

擬牛頓法是一種以牛頓法為基礎設計的，求解非線性方程組或連續的最優化問題函數的零點或極大、極小值的算法。當牛頓法中所要求計算的雅可比矩陣或Hessian矩陣難以甚至無法計算時，擬牛頓法便可派上用場。

搜索極值

與牛頓法相同, 擬牛頓法是用一個二次函數以近似目標函數 $f(x)$ . $f(x)$ 的二階泰勒展開是

f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{T}\Delta x+{\frac {1}{2}}\Delta x^{T}B\Delta x.

其中, $\nabla f$ 表示 $f(x)$ 的梯度, $B$ 表示Hessian矩陣 $\mathbf {H} [f(x)]$ 的近似. 梯度 $\nabla f$ 可進一步近似為下列形式

\nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\Delta x.

令上式等於 $0$ , 計算出Newton步長 $\Delta x$ ,

\Delta x=-B^{-1}\nabla f(x_{k}).

然後構造 $\mathbf {H} [f(x)]$ 的近似 $B$ 滿足

\nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\Delta x.

上式稱作割線方程組. 但當 $f(x)$ 是定義在多維空間上的函數時, 從該式計算 $B$ 將成為一個不定問題 (未知數個數比方程式個數多). 此時, 構造 $B$ , 根據Newton步長更新當前解的處理需要回歸到求解割線方程. 幾乎不同的擬牛頓法就有不同的選擇割線方程的方法. 而大多數的方法都假定 $B$ 具有對稱性 (即滿足 $B=B^{\text{T}}$ ). 另外, 下表所示的方法可用於求解 $B_{k+1}$ ; 在此, $B_{k+1}$ 於某些範數與 $B_{k}$ 盡量接近. 即對於某些正定矩陣 $V$ , 以以下方式更新 $B$ :

B_{k+1}=\arg \min _{B}\|B-B_{k}\|_{V}.

近似Hessian矩陣一般以單位矩陣等作為初期值^[1]. 最優化問題的解 $x_{k}$ 由根據近似所得的 $B_{k}$ 計算出的Newton步長更新得出.

以下為該算法的總結:

$\Delta x_{k}=-\alpha B_{k}^{-1}\nabla f(x_{k})$
$x_{k+1}=x_{k}+\Delta x_{k}$
計算新一個疊代點下的梯度 $\nabla f(x_{k+1})$
令 $y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$
利用 $y_{k}$ , 直接近似Hessian矩陣的逆矩陣 $B_{k+1}^{-1}$ . 近似的方法如下表:

Method	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
DFP法（英語：DFP updating formula）	$\left(I-{\frac {y_{k}\,\Delta x_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}$	$H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}-{\frac {H_{k}y_{k}y_{k}^{T}H_{k}^{T}}{y_{k}^{T}H_{k}y_{k}}}$
BFGS法（英語：BFGS method）	$B_{k}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{T}}{\Delta x_{k}^{T}B_{k}\,\Delta x_{k}}}$	$\left(I-{\frac {y_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)^{T}H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}$
Broyden法（英語：Broyden's method）	$B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{T}\,\Delta x_{k}}}\,\Delta x_{k}^{T}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})\Delta x_{k}^{T}H_{k}}{\Delta x_{k}^{T}H_{k}\,y_{k}}}$
Broyden族	$(1-\varphi _{k})B_{k+1}^{BFGS}+\varphi _{k}B_{k+1}^{DFP},\qquad \varphi \in [0,1]$
SR1法（英語：SR1 formula）	$B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{T}}{(y_{k}-B_{k}\,\Delta x_{k})^{T}\,\Delta x_{k}}}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{T}}{(\Delta x_{k}-H_{k}y_{k})^{T}y_{k}}}$

與逆矩陣的關聯

若 $f$ 是一個凸二次函數，且Hessian矩陣 $B$ 正定，總是希望由擬牛頓法生成的矩陣 $H_{k}$ 收斂於Hessian矩陣的逆 $H=B^{-1}$ 。這是基於疊代值更新最小 (least-change update) 的擬牛頓法系列的一個實例。^[2]

實現

擬牛頓法是現在普遍使用的一種最優化算法, 存在多種程式語言的實現方法。

參見

參考文獻

^ William H. Press. Numerical Recepes. Cambridge Press. 2007: 521-526. ISBN 978-0-521-88068-8.
^ Robert Mansel Gower; Peter Richtarik. Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms. 2015. arXiv:1602.01768  [math.NA].

[1] William H. Press. Numerical Recepes. Cambridge Press. 2007: 521-526. ISBN 978-0-521-88068-8.

[Gower_and_Richtarik-2] Robert Mansel Gower; Peter Richtarik. Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms. 2015. arXiv:1602.01768  [math.NA].

[1]

[2]