拟牛顿法

拟牛顿法是一种以牛顿法为基础设计的，求解非线性方程组或连续的最优化问题函数的零点或极大、极小值的算法。当牛顿法中所要求计算的雅可比矩阵或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矩阵一般以单位矩阵等作为初期值. 最优化问题的解$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法	$\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法	$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法	$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法	$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) 的拟牛顿法系列的一个实例。

实现

拟牛顿法是现在普遍使用的一种最优化算法, 存在多种编程语言的实现方法。

参见

• 牛顿法
• 应用于最优化的牛顿法