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

用最近 m 对位移与梯度差计算搜索方向,理解双循环递推为何节省内存。

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

L-BFGSL-BFGS

仅保存有限组向量历史来近似曲率,减少高维问题的存储成本。

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

本课要建立的能力

用最近 m 对位移与梯度差计算搜索方向,理解双循环递推为何节省内存。

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

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为什么这个方法成立

  1. BFGS 矩阵更新包含左、右各一次秩一变换和一个外积补偿。
  2. 把连续更新对向量的作用展开,先逆序应用右侧变换,经过初始 γI,再正序应用左侧变换和补偿,得到双循环。
  3. 因此在相同初始矩阵和历史下,它等价于相应有限序列 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从手算到独立迁移

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

练习 1 · 复现与理解

没有历史时,本实现返回什么?

需要一点提示

q=g,γ=1,没有第二遍。

查看解析与答案

返回 −g,等于负梯度方向。

练习 2 · 边界与辨析

把正序和倒序都写成正序,会怎样?

需要一点提示

BFGS 更新一般不可交换。

查看解析与答案

不能得到同样的隐式矩阵作用,多对历史时结果通常错误。

练习 3 · 变式与迁移

d=100000、m=10 时历史 float64 大约多大?

需要一点提示

每对包含两个 d 维向量,每元素 8 字节。

查看解析与答案

2×10×100000×8=16000000 字节,约 16 MB,不含其他状态。

继续深入这个专题

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

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

理解之后,继续递进

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