专题进阶 · 优化算法推荐总顺序 · 第 126 / 148 课

用相邻两步的梯度变化估计曲率,推导割线条件与逆 Hessian 更新。

先学会这些,再进入本课 牛顿优化
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 优化算法

BFGSBFGS

用梯度差更新曲率近似,避免显式计算完整 Hessian。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用相邻两步的梯度变化估计曲率,推导割线条件与逆 Hessian 更新。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

Hessian 太贵,但我们已经知道旧梯度和新梯度,能不能用这次变化修正曲率估计?

02一步步得到方法

从一维斜率变化推广

沿一步 s=xₖ₊₁−xₖ,梯度变化 y=gₖ₊₁−gₖ 近似满足 y≈Bs,其中 B 估计 Hessian。若保存逆 Hessian 估计 H,则希望新估计满足 H_new y=s,这叫割线条件。

单个向量等式不足以唯一确定整张矩阵,因此还要选择保持对称性、合适曲率且改动受控的更新。BFGS 是一种拟牛顿更新;它用梯度差学习曲率,没有计算完整的二阶偏导。

逆 Hessian 的 BFGS 公式

令 ρ=1/(yᵀs),则 H_new=(I−ρsyᵀ)H(I−ρysᵀ)+ρssᵀ。代码使用展开的等价式,避免构造与相乘多个完整矩阵。

条件 yᵀs>0 很关键:在 H 正定时,这个条件使新 H 继续正定。若曲率条件失败,真实优化器通常跳过或阻尼修正,而不是盲目除以一个负数或接近零的数。

把一次更新放回优化循环

完整优化过程是:用 p=−Hg 产生方向;线搜索得到步长;更新参数并重新计算梯度;构造 s、y;更新 H。Wolfe 类线搜索可帮助满足曲率条件。

本课代码专门实现并检验逆 Hessian 的一次 BFGS 更新,输入矩阵必须已是对称正定近似。这不是完整的通用最小化器,也没有把线搜索隐藏成一个未实现的函数。

03把一个小例子完全算清楚

一维 H=1,实际目标曲率为 2,观察到 s=1、y=2。

步骤计算与状态为什么这样做
割线条件H_new×2=1要求新估计解释观测到的梯度变化
修正结果H_new=0.5正好得到真实逆曲率
下一次方向p=−0.5g按曲率缩放梯度

窄屏可左右滑动表格,阅读完整计算与理由。

在这个一维二次目标上,一对非零观测就能恢复逆 Hessian。

04为什么这个方法成立

  1. 把公式右乘 y,因 (I−ρysᵀ)y=0,第一项消失,第二项等于 s,因此满足割线条件。
  2. 两项都是对称矩阵,所以对称性保留。
  3. 对任意非零向量 z,二次型等于一个 H 正定二次型加 ρ(sᵀz)²;当 ρ>0 时不会同时为零,因此保持正定。

05把推导翻译成代码

Python · 一次逆 Hessian BFGS 更新

def bfgs_inverse_update(H, s, y):
    n = len(s)
    if len(y) != n or len(H) != n or any(len(row) != n for row in H):
        raise ValueError("shape mismatch")
    sy = sum(a*b for a,b in zip(s,y))
    if sy <= 1e-12:
        raise ValueError("positive curvature required")
    Hy = [sum(H[i][j]*y[j] for j in range(n)) for i in range(n)]
    yHy = sum(y[i]*Hy[i] for i in range(n))
    return [[H[i][j] - (Hy[i]*s[j] + s[i]*Hy[j])/sy
             + (1 + yHy/sy)*s[i]*s[j]/sy
             for j in range(n)] for i in range(n)]

print(bfgs_inverse_update([[1.0]], [1.0], [2.0]))

逐个理解关键决定

sy
内积 yᵀs,而不是逐元素相除;必须具备足够正曲率。
Hy
先进行一次矩阵向量乘法,再用外积完成 O(d²) 更新。
positive curvature required
代码拒绝坏曲率;完整求解器还需选择跳过、阻尼或重启策略。

06时间、空间与实现范围

存储完整 H 需 O(d²),一次矩阵向量乘法与本更新均为 O(d²)。

每轮还要加上梯度和线搜索成本;维度很大时,下一课的 L-BFGS 会避免保存稠密矩阵。

07改变条件,检查哪里会出错

BFGS 保存的是精确 Hessian

它通过梯度观测逐步构造近似,本课变量 H 表示逆 Hessian 近似。

只要满足割线条件就保证正定

还依赖旧 H 正定及 yᵀs>0;单个割线等式不够。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

为什么不能让 yᵀs=0 继续代入?

需要一点提示

查看 ρ。

查看解析与答案

会除以零,并失去正曲率条件,需要跳过或修正。

练习 2 · 边界与辨析

若 H_new y=s,应如何用代码检验?

需要一点提示

矩阵乘向量。

查看解析与答案

计算每一行与 y 的内积,逐项检查是否在容差内等于 s。

练习 3 · 变式与迁移

d=100000 时,保存稠密 H 的主要困难是什么?

需要一点提示

估算 d²。

查看解析与答案

需要 10¹⁰ 个元素,float64 约 80 GB,仅矩阵就很昂贵,应考虑有限记忆近似。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Boyd 与 Vandenberghe · Convex OptimizationDive into Deep Learning · 优化算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。