擬牛頓法

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

搜索極值

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

${\displaystyle 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.}$

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

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

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

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

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

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

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

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

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

以下為該算法的總結:

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

Method	${\displaystyle \displaystyle B_{k+1}=}$	${\displaystyle H_{k+1}=B_{k+1}^{-1}=}$
DFP法（英語：DFP updating formula）	${\displaystyle \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}}}}$	${\displaystyle 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）	${\displaystyle 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}}}}$	${\displaystyle \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）	${\displaystyle B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{T}\,\Delta x_{k}}}\,\Delta x_{k}^{T}}$	${\displaystyle 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族	${\displaystyle (1-\varphi _{k})B_{k+1}^{BFGS}+\varphi _{k}B_{k+1}^{DFP},\qquad \varphi \in [0,1]}$
SR1法（英語：SR1 formula）	${\displaystyle 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}}}}$	${\displaystyle 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}}}}$

與逆矩陣的關聯

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

實現

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

參見

• 牛頓法
• 應用於最優化的牛頓法

參考文獻

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