01先把问题说具体
BFGS 的 d×d 矩阵装不进内存,能否只计算我们实际需要的 H g?
02一步步得到方法
保留观测,不保留整张矩阵
一次 BFGS 更新由一对 s、y 决定。L-BFGS 只保存最近 m 对这样的向量,丢弃更旧的曲率观测,用它们隐式作用到当前梯度。m 是记忆长度,常远小于参数维度 d。
初始化逆曲率常取 γI,其中 γ=(sᵀy)/(yᵀy) 来自最新一对观测。如果没有历史,本课取 γ=1,方向就是负梯度。历史对必须满足正曲率。
第一遍倒序消去,第二遍正序补回
先设 q=g,按最新到最旧处理历史:αᵢ=ρᵢsᵢᵀq,q←q−αᵢyᵢ,其中 ρᵢ=1/(sᵢᵀyᵢ)。记录 α,随后 r=γq。
再按最旧到最新处理:βᵢ=ρᵢyᵢᵀr,r←r+sᵢ(αᵢ−βᵢ)。最终 r 是隐式逆 Hessian 作用于 g 的结果,搜索方向取 −r。次序与 α 的对应关系不能颠倒。
方向计算只是优化器的一部分
得到方向后仍要线搜索、计算新梯度、维护长度不超过 m 的历史,并处理曲率失败。下面代码覆盖双循环这个完整核心,调用者传入已经截取好的历史。
L-BFGS-B 额外处理变量上下界,不是给无约束方向简单 clip 一下就等价。噪声很大的随机梯度也会使 y 变得不可靠,标准确定性拟牛顿经验不能无条件照搬。
03把一个小例子完全算清楚
一维历史 s=1、y=2,当前梯度 g=4。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 倒序处理 | ρ=0.5,α=2,q=4−2×2=0 | 消去观测方向 |
| 初始尺度 | γ=0.5,r=0 | 由最新曲率估计尺度 |
| 正序补回 | β=0,r=0+1×2=2 | 方向 p=−2 |
窄屏可左右滑动表格,阅读完整计算与理由。
方向等于真实逆曲率 0.5 乘负梯度,与上一课一维 BFGS 的结果一致。
04为什么这个方法成立
- BFGS 矩阵更新包含左、右各一次秩一变换和一个外积补偿。
- 把连续更新对向量的作用展开,先逆序应用右侧变换,经过初始 γI,再正序应用左侧变换和补偿,得到双循环。
- 因此在相同初始矩阵和历史下,它等价于相应有限序列 BFGS 矩阵乘向量,避免显式存储该矩阵。
05把推导翻译成代码
Python · L-BFGS 双循环方向计算
def lbfgs_direction(gradient, history):
dot = lambda a,b: sum(x*y for x,y in zip(a,b))
n = len(gradient)
if any(len(s)!=n or len(y)!=n for s,y in history):
raise ValueError("history shape mismatch")
if any(dot(s,y)<=1e-12 for s,y in history):
raise ValueError("positive curvature required")
q = list(gradient)
alphas = []
for s,y in reversed(history):
alpha = dot(s,q)/dot(s,y)
alphas.append(alpha)
q = [a-alpha*b for a,b in zip(q,y)]
gamma = 1.0
if history:
s,y = history[-1]
gamma = dot(s,y)/dot(y,y)
r = [gamma*a for a in q]
for (s,y),alpha in zip(history, reversed(alphas)):
beta = dot(y,r)/dot(s,y)
r = [a+(alpha-beta)*b for a,b in zip(r,s)]
return [-a for a in r]
print(lbfgs_direction([4.0], [([1.0],[2.0])]))逐个理解关键决定
reversed(history)- 第一遍先用最新观测,第二遍才回到时间正序。
reversed(alphas)- 让每个历史对重新匹配自己的 α。
gamma- 使用标量乘单位阵作基础,保持 O(d) 的初始化成本。
06时间、空间与实现范围
m 对历史向量占 O(md) 空间,双循环需要 O(md) 时间,工作向量额外 O(d)。
若 m 被当作固定小常数,则关于 d 近似线性;完整迭代还要计入线搜索和梯度成本。
07改变条件,检查哪里会出错
历史越多一定越好
更久的曲率可能已不适合当前位置,且增加成本。
没有历史仍计算最新 γ
空列表无最新观测,必须有合理初始尺度。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
没有历史时,本实现返回什么?
需要一点提示
q=g,γ=1,没有第二遍。
查看解析与答案
返回 −g,等于负梯度方向。
把正序和倒序都写成正序,会怎样?
需要一点提示
BFGS 更新一般不可交换。
查看解析与答案
不能得到同样的隐式矩阵作用,多对历史时结果通常错误。
d=100000、m=10 时历史 float64 大约多大?
需要一点提示
每对包含两个 d 维向量,每元素 8 字节。
查看解析与答案
2×10×100000×8=16000000 字节,约 16 MB,不含其他状态。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Boyd 与 Vandenberghe · Convex OptimizationDive into Deep Learning · 优化算法