User:Gaussrz/BFGS算法：修订间差异

删除的内容添加的内容

行内

2021年5月12日 (三) 08:16的版本

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

算法

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

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

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

拓展阅读

[[Category:优化算法与方法]]

参考文献

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

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

[1]

@@ 第1行： / 第1行： @@
-在[[数值分析|数值]][[最优化|优化中]]，  '''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矩陣]]来获得。
+在[[数值分析|数值]][[最优化|优化中]]，  '''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矩陣]]来获得。
@@ 第11行： / 第12行： @@
 # 通过求解方程<math>B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k)</math>，获得下降方向<math>\mathbf{p}_k</math>。
 # 在<math>\mathbf p_k</math><math>\mathbf{p}_k</math>方向上进行一维的优化（[[线搜索]]），找到合适的步长<math>\alpha_k</math><math>\alpha_k</math><math>\alpha_k</math><math>\alpha_k</math>。如果这个搜索是完全的，则<math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math> 。<math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math><math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math><math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math><math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_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>的调节。
+== 拓展阅读 ==
 * [[梯度下降]]
 * [[牛顿法]]
@@ 第20行： / 第25行： @@
 <nowiki>
 [[Category:优化算法与方法]]</nowiki>
+== 参考文献 ==