BFGS算法

在数值优化中， Broyden–Fletcher–Goldfarb–Shanno（BFGS）算法是一种求解无约束非线性优化问题的迭代算法。 ^[1]和相关的Davidon–Fletcher–Powell算法类似，BFGS算法通过利用曲率信息对梯度进行预处理来确定下降方向。曲率信息则是通过维护一个使用广义的割线法逐步近似的关于损失函数的Hessian矩阵来获得。

算法

从起始点${\displaystyle \mathbf {x} _{0}}$和初始的Hessian矩阵${\displaystyle B_{0}}$，重复以下步骤，${\displaystyle \mathbf {x} _{k}}$会收敛到优化问题的解：

1. 通过求解方程${\displaystyle B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$，获得下降方向${\displaystyle \mathbf {p} _{k}}$。
2. 在${\displaystyle \mathbf {p} _{k}}$方向上进行一维的优化（线搜索），找到合适的步长${\displaystyle \alpha _{k}}$。如果这个搜索是完全的，则${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ 。在实际应用中，不完全的搜索一般就足够了，此时只要求${\displaystyle \alpha _{k}}$满足Wolfe条件。
3. 令${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$，并且令${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$。
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$。
5. ${\displaystyle B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}}$。

${\displaystyle f(\mathbf {x} )}$表示要最小化的目标函数。可以通过检查梯度的范数 ${\displaystyle ||\nabla f(\mathbf {x} _{k})||}$来判断收敛性。如果${\displaystyle B_{0}}$初始化为${\displaystyle B_{0}=I}$，第一步将等效于梯度下降，但接下来的步骤会受到近似于Hessian矩阵的${\displaystyle B_{k}}$的调节。

拓展阅读

• 梯度下降
• 拟牛顿法

参考文献

1. Fletcher, Roger, Practical Methods of Optimization 2nd, New York: John Wiley & Sons, 1987, ISBN 978-0-471-91547-8