想象你在浓雾笼罩的山谷里，目标是找到最低点（最小值）。如果你是位“牛顿型”登山者，会背着一张超精确的地形图（Hessian 矩阵），每到一个位置就查询当地的坡度变化率（曲率），立刻算出最陡的下降方向。但这张图又大又贵：算一次要 O(n²) 的存储和 O(n³) 的运算，在几百万维的问题里根本背不动。聪明的登山者换了一种思路——不带地图，只在兜里揣一个小本本。每走一步，记录“刚才坡度实际变化了多少”（梯度差），再用新记录修正自己对地形的猜测（近似 Hessian 逆）。这种“边走边记账”的算法家族，就叫拟牛顿法。本篇文章的主角：DFP、BFGS、L-BFGS 和 SR1，都是不同记账风格的代表——有的认真记每一笔并保持乐观（正定），有的嫌本子太重只留最近几笔，有的连乐观都不需要专门对付怪地形。读完你就明白，机器学习里的优化器们，在浓雾中是怎么找路的。

岗位关联

拟牛顿法是机器学习模型训练与科学计算的“隐形引擎”，掌握 BFGS / L-BFGS 的原理与适用场景，是 AI 从业者调优大规模优化问题、读懂优化器源码的必备技能。

目录
  1. 可视化演示
  2. 拟牛顿思想：不背地图的登山者
  3. 割线方程：账本必须平账
  4. DFP公式：最小修正原则
  5. BFGS公式：工业级默认记账法
  6. 正定性保障：让账本永远乐观
  7. L-BFGS算法：轻装简行的大规模之王
  8. SR1公式：不怕负面的特种兵
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示BFGS秩2更新公式、L-BFGS双循环递归与多算法收敛对比，支持历史记忆长度调节。

本节配有交互动效（进入视口后自动加载，约 3KB）。

BFGS秩2更新公式 黄色BFGS通过梯度差s,y构造Hessian逆近似H_k 紫色更新满足割线条件H·y=s，保证正定性 H_{k+1} = H + syᵀ/(yᵀs) - HssᵀH/(sᵀHs) 秩2修正保持正定且满足超线性收敛

拟牛顿思想：不背地图的登山者

浓雾中的登山者分两种。第一种是“牛顿型”：背着一张完整地形图（Hessian 矩阵），走到哪儿都能查出当地曲率，据此算出下一步该往哪走。图是好图，但代价吓人——在大规模问题里，算一次 Hessian 需要 O(n²) 存储、一次求逆 O(n³) 运算，相当于每走一步都要重新测绘整座山。第二种是“拟牛顿型”：索性不背地图，裤兜里揣一个小本本，每走一步只记两笔账——“我向前挪了多少”（位移 s_k）和“坡度读数变了多少”（梯度差 y_k）。

牛顿法靠二阶泰勒展开直接写出步长公式，但真正的牛顿法必须拿到准确的 (∇²f)⁻¹。拟牛顿的朴素想法是：用一个小本本 H_k 去模仿 (∇²f)⁻¹ 的效果。H_k 不必一开始就等于真值，只要方向大致靠谱，随着账本越记越多，路线就会一次比一次准。数学家称之为“用一阶导数的动态信息重建二阶导数的曲率结构”。

于是得到统一的迭代框架：每一步沿 H_k 给出的方向走，用线搜索定步长，然后根据新观测到的 (s_k, y_k) 把 H_k 更新成 H_{k+1}。整个家族的分歧只在于“怎么更新 H”——这就是后面各节的主题。

所以拟牛顿不是“不用二阶信息”，而是“用一阶信息的动态记录来复刻二阶信息”——像聪明的登山者，不背地图却靠小本本越走越有感觉。接下来要问的是：这个本本，到底该按什么规矩记账？

xk+1=xk−Hkgk\displaystyle x_{k+1} = x_k - H_k g_k
这是拟牛顿法的总骨架：负梯度告诉你“往哪下山”，H_k 告诉你“脚下的地形有多陡、该弯多少”，两者结合就是每一步的落点。
  1. 搜索方向负号保证迭代往梯度下降方向走，H_k 则把方向“拧”一下，让它更贴合椭圆等高线的地形。
    dk=−Hkgkd_k = -H_k g_k
  2. 迭代更新当前位置加上搜索方向，就是新位置。
    xk+1=xk+dkx_{k+1} = x_k + d_k
  3. 牛顿情形当 H_k 恰好是真实逆 Hessian 时，二次函数一步直达谷底，对应背着完整地形图的登山者。
    xk+1=xk−(∇2f(xk))−1gkx_{k+1} = x_k - (\nabla^2 f(x_k))^{-1} g_k

割线方程：账本必须平账

本本上的账不是随手写的。登山者对自己有个承诺：我更新后的地形判断，必须能解释“刚才那一步观察到的坡度变化”。你往前挪了 s_k，坡度却变了 y_k，那么你新画的地形图在 s_k 方向上的斜率必须等于 y_k。这就是“平账”，数学上叫割线方程。

从二阶泰勒展开看更清楚：对梯度做一阶近似，g_{k+1} ≈ g_k + B s_k，于是要求 B s_k = y_k。这里的 B 是对 Hessian 的近似，若改用逆近似 H = B⁻¹，等价写成 H y_k = s_k。这个约束把账本和真实观测牢牢绑在一起。

但要注意：割线方程无法唯一确定一个矩阵。n 维矩阵有 n² 个自由度，方程只给出 n 个约束。所以割线方程只是“必须满足”的底线，家族成员的差异在于补上哪些额外偏好——对称性、正定性、最小修正原则，各有各的爱好。

回到比喻：不同记账风格都接受“平账”这条底线，只是后续偏好不同。DFP 喜欢把新旧账本差异压到最小，BFGS 喜欢保持乐观心态（正定），SR1 干脆只记最小一笔修正——风格不同，账都能平。

Bk+1sk=yk\displaystyle B_{k+1} s_k = y_k
割线方程是拟牛顿家族的“平账准则”：无论账本怎么改，都不能违背刚刚亲眼看到的坡度变化。
  1. 位移向量s_k 是两次迭代点之差，代表“这一步实际挪了多远”。
    sk=xk+1−xks_k = x_{k+1} - x_k
  2. 梯度差向量y_k 是两次梯度读数之差，代表“坡度读数变了多少”。
    yk=gk+1−gky_k = g_{k+1} - g_k
  3. 割线方程新账本 B_{k+1} 沿 s_k 方向产生的变化，必须复现真实坡度差。
    Bk+1sk=ykB_{k+1} s_k = y_k
  4. 逆矩阵形式换用逆近似 H = B^{-1}，平账条件等价于 H_{k+1} y_k = s_k，这是 BFGS 系列更新逆矩阵时用的版本。
    Hk+1yk=skH_{k+1} y_k = s_k

DFP公式：最小修正原则

DFP（Davidon-Fletcher-Powell）是最早的拟牛顿记账法，也是这个家族的奠基之作。它的记账原则是：在满足平账的所有方案里，挑一个“跟旧账本差别最小”的；同时要求新账本保持对称——因为真实 Hessian 天生是对称矩阵，账本也必须对称才可信。

数学上这是一个带约束的最小化问题，解出来是一个“秩二修正”：H_{k+1} = H_k 减一项再加一项。减掉的那项沿 y_k 方向收缩，把已经过时的信息从账本里擦掉；加上的那项沿 s_k 方向拉伸，把刚刚看到的新位移信息写进去。一减一加，账本就完成了自我更新。

公式里每一项的角色都很明确。第一项的分母 y_k^T H_k y_k 是归一化标量，确保修正幅度合适；第二项的分母 y_k^T s_k 正是曲率条件，它大于零时更新才稳定。整个过程严格保持对称：H_0 对称，后续每一步更新后依然对称。

DFP 在中小规模问题上非常可靠，是第一代“小本本”。但它有个短板：对线搜索误差比较敏感，数值上容易积累噪声。后来 BFGS 横空出世，凭借更稳健的对偶视角，逐渐把它挤下了主力位置——就像记账方法虽好，却在某些地形的细微误差前不够皮实。

Hk+1=Hk−Hkykyk⊤Hkyk⊤Hkyk+sksk⊤yk⊤sk\displaystyle H_{k+1} = H_k - \frac{H_k y_k y_k^{\top} H_k}{y_k^{\top} H_k y_k} + \frac{s_k s_k^{\top}}{y_k^{\top} s_k}
DFP 的记账风格是“最小改动”：在必须平账的前提下，让新账本尽量像旧账本，只动必要的那两笔。
  1. 秩二修正结构整体是“旧账本 + 一项修正”，修正由两个秩一矩阵相加组成，所以叫秩二。
    Hk+1=Hk+修正项H_{k+1} = H_k + \text{修正项}
  2. 收缩项沿 y_k 方向扣除旧账中已不可信的信息，分母是标量归一化系数。
    Hkykyk⊤Hkyk⊤Hkyk\frac{H_k y_k y_k^{\top} H_k}{y_k^{\top} H_k y_k}
  3. 拉伸项沿 s_k 方向写入新观测到的位移信息，分母正是曲率条件。
    sksk⊤yk⊤sk\frac{s_k s_k^{\top}}{y_k^{\top} s_k}
  4. 分母非零条件拉伸项要求 y_k^T s_k > 0 才有意义，这是拟牛顿法共同的安全底线。
    yk⊤sk>0y_k^{\top} s_k > 0

BFGS公式：工业级默认记账法

BFGS（Broyden-Fletcher-Goldfarb-Shanno）是 DFP 的“对偶记账法”：DFP 盯着逆矩阵 H_k 记账，BFGS 则先记 Hessian 本身 B_k 的账，再顺手推导出逆矩阵的更新。把 s 和 y 的角色互换，两条公式就完全等价——数学上证明它们是同一族更新的两个面孔。但数值表现上，BFGS 比 DFP 更稳，因此成了工业级的默认选择。

BFGS 更新 H 的方式像一个“夹心饼干”：先用 (I − ρ s y^T) 从左右两边夹住旧 H_k，再加一层 ρ s s^T 的“脆皮”。夹心变换保证对称性不被破坏，秩一加项保证割线方程被满足。整个更新只有矩阵乘法和一层的秩一加法，实现成本很低。

最珍贵的性质是“对称正定保持”：只要初始 H_0 正定（比如单位阵 I），且每一步满足曲率条件 y_k^T s_k > 0，那么所有 H_k 都自动保持正定。正定意味着搜索方向永远是下降方向——算法永远乐观地朝下走，绝不让函数值上升，这是它能稳定收敛的定海神针。

今天的 SciPy 和 scikit-learn 底层优化器，几乎默认 BFGS 或其实践变体。对登山者来说，BFGS 就是那个“认真记每一笔、心态永远乐观、账本永远对称”的可靠向导。但它也有软肋：H 是完整的 n×n 矩阵，维度一高，本本自己就重得背不动了——这正好引出 L-BFGS。

Hk+1=(I−ρkskyk⊤)Hk(I−ρkyksk⊤)+ρksksk⊤,ρk=1yk⊤sk\displaystyle H_{k+1} = (I - \rho_k s_k y_k^{\top}) H_k (I - \rho_k y_k s_k^{\top}) + \rho_k s_k s_k^{\top}, \qquad \rho_k = \frac{1}{y_k^{\top} s_k}
BFGS 的更新公式像做三明治：两边夹上“新观测的投影”保对称，中间夹入 H_k 保留旧信息，再补一层“位移外积”确保平账。
  1. 归一系数ρ_k 让夹心变换变成规范化的投影，分母正是曲率条件。
    ρk=1yk⊤sk\rho_k = \frac{1}{y_k^{\top} s_k}
  2. 左乘因子I − ρ s y^T 把旧账本沿 s、y 方向做一次“拧转”。
    (I−ρkskyk⊤)(I - \rho_k s_k y_k^{\top})
  3. 右乘因子与左乘因子互为转置配对，保证更新后矩阵对称。
    (I−ρkyksk⊤)(I - \rho_k y_k s_k^{\top})
  4. 秩一收尾外层积 ρ s s^T 补上位移方向的增量，让割线方程精确成立。
    ρksksk⊤\rho_k s_k s_k^{\top}

正定性保障：让账本永远乐观

BFGS 的“乐观”不是天生的，它需要两个条件同时成立：初始账本正定（一般从单位阵 I 开始），并且每一笔账都满足“曲率条件” y_k^T s_k > 0。这两个条件缺一不可，否则“对称正定保持”的魔法就会失效。

曲率条件从哪来？对于凸函数，二阶展开保证 s^T ∇²f s > 0，条件天然成立；但对于非凸函数，如果线搜索不严谨——比如步长迈得太大——就会出现“明明在下坡，坡度读数却变陡”的怪现象，导致 y_k^T s_k < 0。这时候 BFGS 的账本会瞬间变成“负能量矩阵”，搜索方向可能不再下降，算法直接失控。

工程上的标准保障是 Wolfe 条件：一种精心设计的线搜索规则，既要求函数充分下降，又强制每一步满足曲率条件。实现中还常加防御逻辑——检测到 y^T s ≤ 0 就跳过本次更新或重置 H。这就像记账员发现笔误就重抄一页，而不是硬着头皮把错账记下去。

所以正定性不是玄学，而是一套成体系的“风控机制”。登山者之所以永远乐观，是因为每一步都先确认“坡度确实在变缓”，才敢更新自己的判断。这也是拟牛顿法从理论走向工程时，最容易被人忽略却最致命的细节。

yk⊤sk>0\displaystyle y_k^{\top} s_k > 0
曲率条件是拟牛顿法的心脏检查：只有确认“坡度确实在变缓”，账本才允许更新；否则宁可停笔，也不能记一笔坏账。
  1. 曲率条件位移与梯度差的内积必须为正——这是 BFGS 正定保持的前提。
    yk⊤sk>0y_k^{\top} s_k > 0
  2. 凸函数保证对凸函数，曲率条件等价于一个半正定二次型，天然成立。
    sk⊤∇2f(xk)sk>0s_k^{\top} \nabla^2 f(x_k) s_k > 0
  3. Wolfe 条件强制线搜索第二步保证曲率条件自动满足，其中 c_2 通常取 0.9 左右。
    gk+1⊤sk≥c2 gk⊤sk,0<c2<1g_{k+1}^{\top} s_k \geq c_2 \, g_k^{\top} s_k, \qquad 0 < c_2 < 1

L-BFGS算法：轻装简行的大规模之王

当变量维度进入百万级——比如推荐系统里的逻辑回归、大模型的参数训练——BFGS 的账本 H_k 是 n×n 矩阵，光存储就是 O(n²)，直接内存爆炸。L-BFGS 的解法朴素得惊人：不记完整账本，只留最近 m 步的 (s_i, y_i) 对，用它们“重演”出搜索方向。m 通常取 5 到 20，本子一下子从“大字典”变成“袖珍便签”。

核心是一个“两循环递归”算法：先拿着当前梯度 g_k，从最近的一笔往最旧的一笔走，一路提取系数 α_i；然后从最旧往最新走，把修正一层层加回去。全程只做向量内积和加法，复杂度 O(mn)，内存 O(mn)。和 BFGS 的 O(n²) 相比，在高维场景下是质的飞跃。

还有一个精妙细节：L-BFGS 从不显式构造矩阵，而是在递归开头“临时假设”初始矩阵 H_k⁰ = γ_k I，其中 γ_k 用最近一笔账估计步长尺度。这样既继承了 BFGS 的曲率修正能力，又只需一张小纸片记账——真是把“轻装简行”做到了极致。

对登山者，L-BFGS 就是那个“只记最近几笔、走远路反而更轻快”的极简主义者。在亿万级特征的问题上，它是内存与速度的黄金平衡点——深度学习中常用的 SGD 类方法只用了梯度一阶信息，而 L-BFGS 用极小的代价把曲率信息也揣进了兜里。

q←gkαi=ρisi⊤q,q←q−αiyi,for i=k−1,…,k−mr←γkq,γk=sk−1⊤yk−1yk−1⊤yk−1βi=ρiyi⊤r,r←r+si(αi−βi),for i=k−m,…,k−1\displaystyle\begin{aligned}& q \leftarrow g_k \\& \alpha_i = \rho_i s_i^{\top} q, \quad q \leftarrow q - \alpha_i y_i, \qquad \text{for } i = k-1, \ldots, k-m \\& r \leftarrow \gamma_k q, \qquad \gamma_k = \frac{s_{k-1}^{\top} y_{k-1}}{y_{k-1}^{\top} y_{k-1}} \\& \beta_i = \rho_i y_i^{\top} r, \quad r \leftarrow r + s_i(\alpha_i - \beta_i), \qquad \text{for } i = k-m, \ldots, k-1\end{aligned}
L-BFGS 的两循环递归，像登山者把最近几笔账按“先倒着翻、再顺着翻”的方式念一遍，就能得出下一步方向——全程不打开大地图。
  1. 初始化把当前梯度 g_k 作为 q 的初值，开始“读账”。
    q←gkq \leftarrow g_k
  2. 前向循环从最新到最旧，依次提取每笔账对方向的贡献系数 α_i。
    αi=ρisi⊤q,q←q−αiyi\alpha_i = \rho_i s_i^{\top} q, \quad q \leftarrow q - \alpha_i y_i
  3. 初始矩阵用最近一笔账估计步长尺度 γ_k，作为隐含初始矩阵的系数。
    γk=sk−1⊤yk−1yk−1⊤yk−1\gamma_k = \frac{s_{k-1}^{\top} y_{k-1}}{y_{k-1}^{\top} y_{k-1}}
  4. 后向循环从最旧到最新，把修正一层层加回，得到最终方向 r。
    βi=ρiyi⊤r,r←r+si(αi−βi)\beta_i = \rho_i y_i^{\top} r, \quad r \leftarrow r + s_i(\alpha_i - \beta_i)

SR1公式：不怕负面的特种兵

BFGS 坚持永远乐观（正定），但在一些“怪地形”上反而吃亏：如果函数局部是凹的（负曲率），强制正定的近似会忽略向下的弯曲信息，算法不得不绕远路。SR1（Symmetric Rank-One）换了一种哲学：不追求正定，只求用最小幅度的修正满足割线方程——认账，但不假装世界很美好。

SR1 的更新是“秩一”的——整个修正只有一层外积，比 DFP/BFGS 的秩二更吝啬，计算更便宜。代价是分母可能接近零：当残差向量与位移 s 正交时，更新会数值爆炸，此时需要跳过本次更新。这个“跳过”的防御逻辑，恰恰也让 SR1 能捕捉真正的负曲率，把凹地形的信息如实记入账本。

因此在信赖域方法中，SR1 特别吃香：信赖域求解子问题时，允许非正定近似反而信息更全——狗腿法和截断共轭梯度都能从负曲率中获益。选型逻辑很清晰：一般无约束凸优化用 BFGS/L-BFGS；高度非凸的优化问题搭配信赖域框架，SR1 往往优于 BFGS。

SR1 就像登山队伍里的特种兵：不追求心态阳光，只追求用最小的本子记录最真实的地形——包括那些让人沮丧的悬崖（负曲率）。在信赖域框架下信任它，复杂地形里往往有奇效。至此，拟牛顿家族的四位记账员——DFP、BFGS、L-BFGS、SR1——全部登场，你已具备了读懂任何现代优化器源码的底子。

Bk+1=Bk+(yk−Bksk)(yk−Bksk)⊤(yk−Bksk)⊤sk\displaystyle B_{k+1} = B_k + \frac{(y_k - B_k s_k)(y_k - B_k s_k)^{\top}}{(y_k - B_k s_k)^{\top} s_k}
SR1 的更新像在账本上贴一张最小便签：只补“旧账预测与现实之间差的那一笔”，好用又便宜，但遇到夹角太小的情形就得防着别撕破账本。
  1. 残差向量r_k 是当前账本预测的坡度变化与实际坡度变化之间的偏差。
    rk=yk−Bkskr_k = y_k - B_k s_k
  2. 秩一更新用偏差向量的一层外积作修正，只占一个秩，成本最低。
    rkrk⊤rk⊤sk\frac{r_k r_k^{\top}}{r_k^{\top} s_k}
  3. 分母风险当 r_k 与 s_k 接近正交时分母趋近零，必须用阈值判断并跳过更新。
    ∣rk⊤sk∣≥ϵ ∥rk∥ ∥sk∥|r_k^{\top} s_k| \geq \epsilon \, \|r_k\| \, \|s_k\|
  4. 不保正定更新的结果允许非正定，这正是它捕捉负曲率的能力来源。
    Bk+1⊁0B_{k+1} \not\succ 0

AI 应用场景

推荐系统大规模 CTR 预估模型的求解

阶段：模型训练（参数求解）

解决的问题：CTR 预估的逻辑回归特征维度常达上亿，BFGS 的 O(n²) 矩阵根本存不下；而 SGD 收敛慢、对学习率敏感，调参成本高。L-BFGS 只存最近 m 步梯度差，内存 O(mn)，又自带曲率估计，收敛步数远少于 SGD。

具体案例：某广告平台训练亿级特征逻辑回归，采用 L-BFGS 全批量训练，单机内存从“存不下 BFGS 矩阵”降到几个 GB，训练时间缩短约 50%，AUC 提升 0.3 个百分点——这就是“轻装记账”在工业界的直接收益。

机器学习库中的通用求解器

阶段：模型求解与调参阶段

解决的问题：普通用户不想手写优化器，也希望获得超线性收敛。scikit-learn 的 LogisticRegression 默认 solver 就是 "lbfgs"，SciPy 的 minimize 内置 BFGS——框架把这些二阶方法封装成一行代码。

具体案例：数据科学团队做信用评分卡，用 sklearn 的 lbfgs 求解 L2 正则逻辑回归，几十次迭代即收敛，同时输出特征权重供业务解释。用户只感知到“快”，背后是拟牛顿法在扛活。

三维视觉中的信赖域与 SR1

阶段：几何优化（位姿估计 / Bundle Adjustment）

解决的问题：重投影误差函数高度非凸，局部 Hessian 常出现非正定；BFGS 强制正定会损失负曲率信息，绕远路甚至陷入鞍点。SR1 允许非正定近似，恰好适合信赖域框架下的子问题求解。

具体案例：某 SLAM 系统的后端优化中，相机位姿估计的重投影误差 Hessian 存在负曲率区段，改用信赖域配合 SR1 近似后，迭代次数减少约 30%，定位轨迹漂移明显下降。

Python 演示

python40 行
import numpy as np def rosen(x):    """Rosenbrock 测试函数：山谷地形，最低点在 (1,1)"""    return sum(100.0 * (x[1:] - x[:-1] ** 2) ** 2 + (1 - x[:-1]) ** 2) def rosen_grad(x):    """Rosenbrock 的梯度：登山者手中的坡度计"""    g = np.zeros_like(x)    g[1:] += 200.0 * (x[1:] - x[:-1] ** 2)    g[:-1] += -400.0 * (x[1:] - x[:-1] ** 2) * x[:-1] - 2.0 * (1 - x[:-1])    return g def bfgs(f, gf, x0, max_iter=200, tol=1e-6):    """用回溯线搜索实现的 BFGS 拟牛顿法"""    n = len(x0)    x = x0.copy()    H = np.eye(n)          # 小本本：近似 Hessian 逆矩阵    for _ in range(max_iter):        g = gf(x)        if np.linalg.norm(g) < tol:            break        d = -H @ g         # 用近似逆矩阵求出搜索方向        alpha = 1.0        while f(x + alpha * d) > f(x) + 1e-4 * alpha * (g @ d):            alpha *= 0.5   # 回溯：步长太大就折半        s = alpha * d        x_new = x + s        y = gf(x_new) - g  # 记一笔：梯度差        rho = 1.0 / (y @ s)  # 平账系数（曲率条件）        A = np.eye(n) - rho * np.outer(s, y)        H = A @ H @ A.T + rho * np.outer(s, s)  # 夹心更新        x = x_new    return x, f(x) if __name__ == "__main__":    x0 = np.array([-1.2, 1.0])    x_opt, f_opt = bfgs(rosen, rosen_grad, x0)    print("最优解:", x_opt)    print("目标值:", f_opt)
目的：从零实现一个最简 BFGS 优化器，在经典 Rosenbrock 测试函数上验证“梯度差记账”能否收敛到最小值。
  1. H = np.eye(n)小本本初始化为单位阵，从“完全不了解地形”开始。
  2. d = -H @ g用近似逆 Hessian 把负梯度方向“拧”一下，得到搜索方向。
  3. while f(x + alpha * d) > ...回溯线搜索：步长不合适就折半，保证函数充分下降。
  4. y = gf(x_new) - g记账：记录坡度差向量 y_k。
  5. rho = 1.0 / (y @ s)平账系数：分母是曲率条件，必须为正才能稳定更新。
  6. H = A @ H @ A.T + rho * np.outer(s, s)BFGS 夹心更新：保对称、满足割线方程。

常见误区

误区我一直以为凡是不算 Hessian 的方法都是一阶方法，SGD 是一阶，拟牛顿也是。那 BFGS 和 Adam 到底有什么区别？

正解拟牛顿属于“二阶方法家族”。它虽然不显式计算 Hessian，但通过相邻梯度差重建了曲率信息，用 H 矩阵近似逆 Hessian。搜索方向的修正来自估计的曲率，而非单纯的学习率，因此收敛速率是超线性的。判断标准应看“是否利用曲率信息”，而不是只看“是否算了二阶导”。

为何常见：教材通常把“是否计算二阶导”作为一阶/二阶的分类标准，初学者按表面标准分类，忽略了曲率信息才是关键。

误区我以为要想 BFGS 有效，得先把真实 Hessian 算出来当初始值，或者至少做很好的估计，否则前几步会乱走。

正解实践中 H_0 通常取单位阵 I 或对角缩放，甚至 γI 都能保证收敛，且最终收敛速率依然是超线性的。BFGS 的魅力正在于“从最朴素的正定矩阵开始，靠每一步梯度差慢慢长成合适的近似”——前提只是曲率条件 y^T s > 0 得到满足。

为何常见：人们容易把迭代算法想象成“必须从准确起点出发”，忽略了拟牛顿法自带的自修复机制。

误区L-BFGS 一听就是 BFGS 的简化版，内存省了那么多，算出来的最优解肯定精度更差，只能大概用用。

正解L-BFGS 与 BFGS 的最终收敛精度相当，区别主要在每步的存储和计算成本。它用最近 m 步的 (s,y) 对在两循环递归中隐式还原曲率信息；当 m 足够（10~20 步）时，经验上收敛表现与 BFGS 几乎无异，且大规模场景下往往更快更稳。

为何常见：“压缩/截断”容易让人联想到有损压缩（如 JPEG），误以为必定损失精度；但 L-BFGS 截断的是历史信息，而远距离历史对曲率近似的贡献本就迅速衰减。

误区我在写线搜索时从来不管什么曲率条件，反正梯度方向总是下降的，跑几次也能收敛。

正解在非凸问题上，如果步长过大或函数有负曲率，可能出现 y_k^T s_k < 0。此时 BFGS 的正定保持失效，H 可能变成非正定矩阵，搜索方向不再下降，甚至发散。工程实践中要用 Wolfe 条件的第二式保证曲率条件，或加“检测到负曲率就跳过更新/重置 H”的防御逻辑。

为何常见：在凸二次函数或强凸问题上曲率条件自动成立，学习者只在小规模凸问题上跑过，自然以为它是免费午餐。

误区正定是好东西，凡是不能保证正定的方法都应该避开。SR1 连正定都保不了，肯定是被淘汰的算法。

正解SR1 的“不保证正定”恰恰是它在非凸问题上的优势：它能捕捉负曲率信息，帮助算法更快离开鞍点；而 BFGS 强制正定近似，在负曲率区域反而会给出误导方向。在信赖域框架下（求解子问题时允许不定近似），SR1 经常优于 BFGS。

为何常见：教材总强调“保持正定”的优越性，初学者形成“正定=好”的绝对化思维，忽略了方法适用场景的区别。

面试题

Q1. 拟牛顿法族要避免的计算是什么？

单选题 · easy

  • A.一阶梯度向量
  • B.二阶 Hessian 矩阵← 正确答案
  • C.目标函数取值
  • D.线搜索的步长

答案：B。拟牛顿的核心动机就是避免显式计算二阶导数 Hessian，改用梯度差来近似曲率信息。A 是它仍然需要的，C、D 是所有优化方法都绕不开的基础操作。

Q2. 割线方程 B_{k+1}s_k = y_k 中 y_k 的含义是？

单选题 · easy

  • A.两迭代点的位移
  • B.两处梯度的差← 正确答案
  • C.目标函数差值
  • D.搜索方向向量

答案：B。y_k = g_{k+1} − g_k，是相邻两次迭代梯度读数之差，对应比喻中“坡度变化了多少”。s_k 才是两次迭代点的位移，注意不要混淆 A 和 B。

Q3. BFGS 更新公式在什么条件下保持正定性？

单选题 · mid

  • A.曲率条件 y^T s > 0← 正确答案
  • B.步长恒等于 1
  • C.目标函数为线性
  • D.梯度完全为零

答案：A。BFGS 的对称正定保持依赖两个前提：初始 H_0 正定，且每一步 y_k^T s_k > 0。曲率条件一旦被违反，正定魔法就失效。梯度为零时算法已经收敛，谈不上更新。

Q4. 关于 L-BFGS 的描述，正确的有哪些？

多选题 · mid

  • A.只保留最近 m 步历史← 正确答案
  • B.内存随迭代不断增加
  • C.用两循环递归算方向← 正确答案
  • D.每步需要完整 Hessian

答案：AC。L-BFGS 只存最近 m 对 (s,y)，内存固定为 O(mn)，不随迭代次数增长。方向由前向、后向两个循环递归算出。B 错在内存恒定，D 错在它正是为了避免 Hessian 才存在的。

Q5. DFP 与 BFGS 之间的关系是？

单选题 · mid

  • A.完全相同的公式
  • B.s 与 y 互换互相对偶← 正确答案
  • C.一个只能求解凸问题
  • D.两个公式毫无关联

答案：B。DFP 与 BFGS 在互换 s 与 y 的角色后完全等价，是同一族更新的两个面孔，数学上称为对偶。因此 B 正确。它们都能处理非凸问题（配合合适线搜索），并非“完全不同”或“毫无关联”。

Q6. 在非凸函数上 BFGS 可能失效的直接原因是？

单选题 · hard

  • A.Hessian 矩阵太稀疏
  • B.曲率条件被违反← 正确答案
  • C.梯度方向算错
  • D.步长总是太小

答案：B。非凸函数局部可能有负曲率，线搜索不当时出现 y_k^T s_k < 0，导致 BFGS 正定保持失效、搜索方向不再下降。稀疏性、步长大小都不是直接死因，梯度方向本身是准确的。

Q7. 哪些方法属于拟牛顿法家族？

多选题 · easy

  • A.DFP 公式← 正确答案
  • B.BFGS 公式← 正确答案
  • C.随机梯度下降
  • D.L-BFGS 算法← 正确答案

答案：ABD。DFP、BFGS、L-BFGS、SR1 都是拟牛顿家族成员，它们共用割线方程的思想。随机梯度下降只用一阶梯度、没有曲率近似，属于纯一阶方法，不属于拟牛顿族。

Q8. L-BFGS 每步的复杂度大约是？

单选题 · mid

  • A.O(n²)
  • B.O(mn)← 正确答案
  • C.O(n³)
  • D.O(m²n)

答案：B。L-BFGS 的两循环递归只做向量内积和加乘，每步 O(mn)，内存同样是 O(mn)，其中 m 通常取 5~20。O(n²) 是完整 BFGS 的存储量级，O(n³) 是求逆的量级。

Q9. SR1 在信赖域方法中受欢迎的原因是？

多选题 · hard

  • A.允许非正定近似存在← 正确答案
  • B.能捕捉负曲率信息← 正确答案
  • C.一定保持对称正定
  • D.秩一更新代价更低← 正确答案

答案：ABD。SR1 不强制正定，能如实记录负曲率，帮助算法在非凸地形中离开鞍点；同时秩一更新的每步成本比 BFGS 的秩二更低。C 恰恰说反——SR1 的有用之处就是不保正定。

Q10. SR1 更新中分母 r^T s 接近零时的正确处理方式是？

单选题 · extreme

  • A.强制更新保证正定
  • B.跳过本次更新← 正确答案
  • C.将分母改为常数
  • D.直接终止算法

答案：B。SR1 的分母 r^T s 接近零意味着残差向量与位移近乎正交，更新会产生数值爆炸，标准做法是按阈值判断后跳过本次更新。强制更新会破坏数值稳定性，改为常数则不再满足割线方程，直接终止又过于激进。