查看“︁BFGS算法”︁的源代码

{{Onesource|time=2021-05-24T10:30:43+00:00}}
在[[数值分析|数值]][[最优化|优化]]中，  '''Broyden–Fletcher–Goldfarb–Shanno（BFGS）算法'''是一种求解无约束[[非线性规划|非线性优化]]问题的[[迭代法|迭代算法]]。 <ref>{{Citation|last=Fletcher|first=Roger|title=Practical Methods of Optimization|publisher=[[John Wiley & Sons]]|place=New York|edition=2nd|isbn=978-0-471-91547-8|year=1987|url=https://archive.org/details/practicalmethods0000flet}}</ref>和相关的Davidon–Fletcher–Powell算法类似，BFGS算法通过利用[[曲率]]信息对[[梯度]]进行预处理来确定下降方向。曲率信息则是通过维护一个使用广义的[[割线法]]逐步近似的关于[[损失函数]]的[[Hessian矩阵|Hessian矩陣]]来获得。
== 算法 ==
从起始点<math>\mathbf{x}_0</math>和初始的[[Hessian矩阵]]<math>B_0</math>，重复以下步骤，<math>\mathbf{x}_k</math>会收敛到优化问题的解：

# 通过求解方程<math>B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k)</math>，获得下降方向<math>\mathbf{p}_k</math>。
# 在<math>\mathbf p_k</math>方向上进行一维的优化（[[线搜索]]），找到合适的步长<math>\alpha_k</math>。如果这个搜索是完全的，则<math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math> 。在实际应用中，不完全的搜索一般就足够了，此时只要求<math>\alpha_k</math>满足[[Wolfe条件]]。
#令<math> \mathbf{s}_k = \alpha_k \mathbf{p}_k</math>，并且令<math>\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k</math>。
#<math>\mathbf{y}_k = {\nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)}</math>。
#<math>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}</math>。
#

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

== 拓展阅读 ==
* [[梯度下降]]
* [[擬牛頓法|拟牛顿法]]
== 参考文献 ==
<references />

[[Category:最优化算法]]