BFGS 更新 | Codeboy's Blog

形式陈述

BFGS 的输入是当前对称正定矩阵及同维实向量 $s_k,y_k$ 。在拟 Newton 法中，这两个向量通常取为位移与梯度差

s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k),

并假设曲率条件 $s_k^Ty_k>0$ 。若 $B_k$ 是 Hessian 的对称正定近似，BFGS 更新为

B_{k+1} =B_k-\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} +\frac{y_ky_k^T}{y_k^Ts_k}.

它满足割线方程 $B_{k+1}s_k=y_k$ 。若维护逆近似 $H_k=B_k^{-1}$ ，令 $\rho_k=(y_k^Ts_k)^{-1}$ ，则等价的常用乘积形式为

H_{k+1} =(I-\rho_ks_ky_k^T)H_k(I-\rho_ky_ks_k^T) +\rho_ks_ks_k^T.

输入必须包含 $B_k$ 或 $H_k$ 、有效曲率对及数值容差；输出除新矩阵外还应表明更新、阻尼或拒绝状态。更新公式本身不选择 $x_{k+1}$ ，方向和步长仍由外层优化算法负责。在序列二次规划中，应近似 Lagrangian 的曲率：构造梯度差时，用同一个新乘子比较两处的 Lagrangian 梯度，而不是直接沿用无约束目标梯度差。

直觉

第一项先从旧矩阵中移除沿 $s_k$ 的旧曲率预测，第二项再植入观测到的新关系 $s_k\mapsto y_k$ ；其余方向尽量保留旧信息。修正的秩至多为二；稠密存储时，这些外积更新耗时 $O(n^2)$ ，利用位移与梯度差更新曲率，无需重新计算二阶导数。对称性使它仍可解释为二次模型，割线条件让最近一次梯度变化被精确复现，正定性则保证下一搜索方向下降。

同一割线对与同一比例尺下，正定逆 Hessian 更新使 H_{k+1}y_k=s_k — 逆 Hessian 度量的割线校正

图中取 $H_k=\operatorname{diag}(1,2)$ 、 $y_k=(1,1)^\top$ 、 $s_k=(2,1)^\top$ ，所以 $\rho_k=1/3$ ，更新得到 $H_{k+1}=\tfrac13\begin{pmatrix}7&-1\\-1&4\end{pmatrix}$ 。两矩阵的行列式分别为 $2$ 与 $3$ ，且 $H_ky_k=(1,2)^\top$ 、 $H_{k+1}y_k=s_k$ 。两个面板的向量共用比例尺，椭圆表示 $v^\top H^{-1}v=0.9^2$ 。

正定保持可以直接看出。对任意非零 $z$ ，

z^TB_{k+1}z =z^TB_kz-\frac{(z^TB_ks_k)^2}{s_k^TB_ks_k} +\frac{(z^Ty_k)^2}{s_k^Ty_k}.

前两项由 $B_k$ -内积下的Cauchy–Schwarz 不等式非负；若恰为零，则 $z$ 与 $s_k$ 共线，而最后一项因 $s_k^Ty_k>0$ 严格为正。因此 $B_{k+1}$ 仍是正定矩阵。曲率条件不是避免除零的技术细节，而是方向性质的核心。

例子与边界

取

B_0=I,\qquad s=(1,0)^T,\qquad y=(2,1)^T,

则 $s^Ty=2>0$ ，且

B_1 =I-ss^T+\frac{yy^T}{2} =\begin{pmatrix}2&1\\1&3/2\end{pmatrix}.

直接相乘得 $B_1s=(2,1)^T=y$ ，割线条件成立；首个顺序主子式为 $2$ 、行列式为 $2$ ，故矩阵正定。逆公式给

H_1=\begin{pmatrix}3/4&-1/2\\-1/2&1\end{pmatrix},

而 $B_1H_1=I$ ，可逐项复核两种更新确实一致。非对角项显示，一个方向的曲率观测也会改变耦合方向。

若改成 $y=(-1,0)^T$ ，则 $s^Ty=-1$ ，直接更新得到 $B_1=\operatorname{diag}(-1,1)$ ，确实失去正定性。一个阻尼选择是把观测改为 $\widetilde y=0.4y+0.6B_0s=(0.2,0)^T$ ，使 $s^T\widetilde y=0.2s^TB_0s>0$ ；再更新得到 $\operatorname{diag}(0.2,1)$ 。它恢复了正定性，却满足的是修改后的割线方程 $B_1s=\widetilde y$ ，不再精确复现原梯度差。

非凸目标上也可跳过更新，或改用容许不定近似的 SR1；每种选择都改变实际算法，必须记录。若 $s^Ty$ 虽正却接近舍入误差，两个大秩一项相减会损害对称性和条件数。线搜索失败、梯度不一致或变量尺度悬殊同样会污染曲率对。

推论与应用

若 $p_k$ 是下降方向且步长满足弱 Wolfe 曲率条件，则

s_k^Ty_k =\alpha_k\bigl(\phi'(\alpha_k)-\phi'(0)\bigr) \ge\alpha_k(c_2-1)\phi'(0)>0,

所以线搜索为 BFGS 正定更新提供可验证的曲率证书。对光滑强凸目标，在标准有界水平集与线搜索条件下可建立全局收敛；在极小点附近再加 Hessian 正定及 Lipschitz 等条件，完整 BFGS 通常具有超线性局部收敛。函数值下降、矩阵正定与超线性速度是三层不同结论。

大规模问题使用 L-BFGS 保存最近 $m$ 组 $(s_i,y_i)$ ，通过双循环递推计算 $H_kg_k$ ，把存储从 $O(n^2)$ 降到 $O(mn)$ 。它复用了 BFGS 的曲率对，却不显式形成本页矩阵；有限记忆会丢弃旧方向信息，因此不能直接声称与完整 BFGS 有相同有限终止性质。实现还应定期检查 $s^Ty$ 、对称误差和搜索方向内积，发现失效时给出可审计状态。

参考资料

Charles G. Broyden, “The Convergence of a Class of Double-rank Minimization Algorithms,” Journal of the Institute of Mathematics and Its Applications 6, 1970, 76–90；Roger Fletcher, “A New Approach to Variable Metric Algorithms,” Computer Journal 13(3), 1970, 317–322。
Donald Goldfarb, “A Family of Variable-Metric Methods Derived by Variational Means,” Mathematics of Computation 24(109), 1970, 23–26；David F. Shanno, “Conditioning of Quasi-Newton Methods for Function Minimization,” Mathematics of Computation 24(111), 1970, 647–656。
Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer, 2006，§§6.1–6.2 and 7.2，BFGS, positive definiteness, and L-BFGS。

形式陈述 ​

反向链接

形式陈述