擬牛頓法

與牛頓法相同, 擬牛頓法是用一個二次函數以近似目標函數${\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].