拟牛顿法

拟牛顿法是一种以牛顿法为基础设计的，求解非线性方程组或连续的最优化问题函数的零点或极大、极小值的算法。当牛顿法中所要求计算的雅可比矩阵或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矩阵一般以单位矩阵等作为初期值^[1]. 最优化问题的解 $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法（英语：DFP updating formula）	$\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法（英语：BFGS method）	$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法（英语：Broyden's method）	$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法（英语：SR1 formula）	$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) 的拟牛顿法系列的一个实例。^[2]

实现[编辑]

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

参见[编辑]

参考文献[编辑]

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

[1] William H. Press. Numerical Recepes. Cambridge Press. 2007: 521-526. ISBN 978-0-521-88068-8.

[Gower_and_Richtarik-2] Robert Mansel Gower; Peter Richtarik. Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms. 2015. arXiv:1602.01768  [math.NA].

[1]

[2]