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为什么这个方法成立
- 把公式右乘 y,因 (I−ρysᵀ)y=0,第一项消失,第二项等于 s,因此满足割线条件。
- 两项都是对称矩阵,所以对称性保留。
- 对任意非零向量 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
为什么不能让 yᵀs=0 继续代入?
需要一点提示
查看 ρ。
查看解析与答案
会除以零,并失去正曲率条件,需要跳过或修正。
若 H_new y=s,应如何用代码检验?
需要一点提示
矩阵乘向量。
查看解析与答案
计算每一行与 y 的内积,逐项检查是否在容差内等于 s。
d=100000 时,保存稠密 H 的主要困难是什么?
需要一点提示
估算 d²。
查看解析与答案
需要 10¹⁰ 个元素,float64 约 80 GB,仅矩阵就很昂贵,应考虑有限记忆近似。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Boyd 与 Vandenberghe · Convex OptimizationDive into Deep Learning · 优化算法