BFGS算法

此條目或其章節极大或完全地依赖于某个单一的来源。 (2021年5月24日) 请协助補充多方面可靠来源以改善这篇条目。 致使用者：请搜索一下条目的标题（来源搜索："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