拟牛顿法

拟牛顿法是一种以牛顿法为基础设计的，求解非线性方程组或连续的最优化问题函数的零点或极大、极小值的算法。当牛顿法中所要求计算的雅可比矩阵或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].