# 擬牛頓法

## 搜索極值

${\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(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\Delta x.}$

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

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

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

• ${\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}=}$
${\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}}}}$
${\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. [math.NA].