对应 note_8_quasinewton.pdf。这一章回答一个实际问题：Newton 法快，但 Hessian 太贵；能不能只用梯度差来“学”一个 Hessian 或逆 Hessian？答案就是 quasi-Newton，核心是 secant equation、Wolfe line search、DFP/BFGS/L-BFGS。

0. 一句话理解这一章

拟牛顿法 = 用最近两次迭代的位移 $s_k$ 和梯度变化 $y_k$ 拟合曲率，逐步构造 $B_k\approx {\mathrm{\nabla }}^{2}f(x_k)$ 或 $H_k\approx [{\mathrm{\nabla }}^{2}f(x_k){]}^{-1}$，从而用接近 Newton 的方向但避免显式 Hessian。

1. 知识地图

                    Newton 法瓶颈
              Hessian 计算/存储/分解太贵
                          │
                          ▼
                    Quasi-Newton
        d_k = -B_k^{-1}∇f(x_k) 或 d_k=-H_k∇f(x_k)
                          │
                          ▼
                    Secant equation
                    s_k=x_{k+1}-x_k
                  y_k=∇f(x_{k+1})-∇f(x_k)
             B_{k+1}s_k=y_k 或 H_{k+1}y_k=s_k
                          │
                          ▼
                  Curvature condition
                      s_k^T y_k>0
              Wolfe line search 保证它成立
                          │
                          ▼
                       更新公式
                  DFP / BFGS / L-BFGS
                          │
                          ▼
                        相关方法
      BB 步长 / Gauss-Newton / Levenberg-Marquardt

2. Secant equation：拟牛顿的核心

定义

$$s_k=x_{k+1}-x_k,y_k=\mathrm{\nabla }f(x_{k+1})-\mathrm{\nabla }f(x_k).$$

若 $f$ 近似二次，则有

$$y_k\approx {\mathrm{\nabla }}^{2}f(x_k)s_k.$$

因此希望新的 Hessian 近似满足

$$B_{k+1}{s}_k=y_k.$$

如果直接近似逆 Hessian，则写成

$$H_{k+1}{y}_k=s_k.$$

这两条就是 secant equation。

曲率条件

为了让 $B_{k+1}\succ 0$ 或 $H_{k+1}\succ 0$，必须有

$$s_k^T{y}_k>0.$$

对强凸函数，这个量天然倾向于为正；对一般目标函数，要靠 Wolfe line search 保证。

3. 为什么用 Wolfe 而不是只用 Armijo

拟牛顿方向 $p_k$ 一般配 Wolfe 条件：

$$f(x_k+t_k{p}_k)\le f(x_k)+c_1{t}_k\mathrm{\nabla }f(x_k{)}^T{p}_k,$$$$\mathrm{\nabla }f(x_k+t_k{p}_k{)}^T{p}_k\ge c_2\mathrm{\nabla }f(x_k{)}^T{p}_k,0<c_1<c_2<1.$$

第一条是 Armijo sufficient decrease；第二条是 curvature condition。

由第二条可得

$$y_k^T{s}_k=t_k(\mathrm{\nabla }f(x_{k+1})-\mathrm{\nabla }f(x_k){)}^T{p}_k\ge t_k(c_2-1)\mathrm{\nabla }f(x_k{)}^T{p}_k>0,$$

因为 $p_k$ 是下降方向，$\mathrm{\nabla }f(x_k{)}^T{p}_k<0$。这就是 Wolfe 在 quasi-Newton 中不可替代的原因。

4. DFP 与 BFGS 更新

4.1 DFP

DFP 从 Hessian 近似 $B_k$ 的“最小改动 + secant equation”出发。讲义给出的 $B$-形式是

$$B_{k+1}=(I-{\rho }_k{y}_k{s}_k^T)B_k(I-{\rho }_k{s}_k{y}_k^T)+{\rho }_k{y}_k{y}_k^T,{\rho }_k=\frac{1}{y_k^T{s}_k}.$$

其逆 Hessian 形式常写为

$$H_{k+1}=H_k-\frac{H_k{y}_k{y}_k^T{H}_k}{y_k^T{H}_k{y}_k}+\frac{s_k{s}_k^T}{y_k^T{s}_k}.$$

4.2 BFGS

BFGS 更常用。逆 Hessian 近似的更新为

$$H_{k+1}=(I-{\rho }_k{s}_k{y}_k^T)H_k(I-{\rho }_k{y}_k{s}_k^T)+{\rho }_k{s}_k{s}_k^T,{\rho }_k=\frac{1}{y_k^T{s}_k}.$$

对应的 Hessian 近似更新：

$$B_{k+1}=B_k-\frac{B_k{s}_k{s}_k^T{B}_k}{s_k^T{B}_k{s}_k}+\frac{y_k{y}_k^T}{y_k^T{s}_k}.$$

要记住的性质：

• 若 $H_k\succ 0$ 且 $s_k^T{y}_k>0$，则 $H_{k+1}\succ 0$；
• 方向 $d_k=-H_k\mathrm{\nabla }f(x_k)$ 是下降方向；
• 配 Wolfe 条件有全局收敛结果；
• 在适当条件下 BFGS 可超线性收敛。

5. BFGS 实现建议

讲义给出的实际设置：

项	常用选择
初始步长	先试 $t_k=1$
Wolfe 参数	$c_1={10}^{-4},c_2=0.9$
初始逆 Hessian 近似	可用 $\gamma I$，例如 $\gamma =\frac{s_k^T{y}_k}{y_k^T{y}_k}$
终止	$|\mathrm{\nabla }f(x_k)|\le ϵ$

注意：BFGS 每步要存一个 dense $H_k$ 或 $B_k$，存储和乘法都可能是 $O(n^2)$。大规模问题用 L-BFGS。

6. 收敛性结论

6.1 Zoutendijk 定理

若方向满足 Wolfe 条件、$f$ 下有界、$\mathrm{\nabla }f$ 在 level set 上 Lipschitz，则

$$\sum _{k=0}^{\mathrm{\infty }}{\cos }^2{\theta }_k\parallel \mathrm{\nabla }f(x_k){\parallel }^2<\mathrm{\infty },$$

其中 ${\theta }_k$ 是搜索方向 $p_k$ 与负梯度 $-\mathrm{\nabla }f(x_k)$ 的夹角。

直观解释：

• 若方向没有越来越接近“正交于负梯度”，则梯度必须趋于 0；
• BFGS 的证明核心之一就是排除方向长期变坏。

6.2 BFGS 全局收敛

在强凸、Hessian 有上下界等标准假设下，BFGS 生成的序列收敛到唯一最优解。

讲义的证明用到了矩阵函数

$$\psi (B)=\mathrm{tr}(B)-\log detB,$$

通过控制 $\psi (B_k)$ 来说明 $B_k$ 不会退化到让方向完全失效。

6.3 超线性收敛

若 ${\mathrm{\nabla }}^{2}f$ 在 $x^{\ast }$ 附近 Lipschitz，且 BFGS 迭代满足相应可和性条件，则

$$\parallel x_{k+1}-x^{\ast }\parallel =o(\parallel x_k-x^{\ast }\parallel ).$$

这就是 BFGS 在实践中很快的理论来源。

7. L-BFGS

BFGS 存 dense $H_k$，大规模时不现实。L-BFGS 只保存最近 $m$ 对

$$(s_i,y_i),i=k-m,\dots ,k-1.$$

这样每步计算 $H_k\mathrm{\nabla }f(x_k)$ 的成本和存储都是

$$O(mn),$$

其中 $m$ 通常远小于 $n$。

Two-loop recursion

核心思想：不用显式形成 $H_k$，只通过最近 $m$ 对 $(s_i,y_i)$ 递推计算 $H_{k}q$。

记忆版流程：

1. $q\leftarrow \mathrm{\nabla }f(x_k)$。
2. 从新到旧扫一遍，计算 ${\alpha }_i={\rho }_i{s}_i^{T}q$，并令 $q\leftarrow q-{\alpha }_i{y}_i$。
3. 乘初始矩阵 $r\leftarrow H_k^{0}q$。
4. 从旧到新扫一遍，计算 $\beta ={\rho }_i{y}_i^{T}r$，并令 $r\leftarrow r+s_i({\alpha }_i-\beta )$。
5. 方向 $d_k=-r$。

考试/作业重点通常不是手写完整代码，而是知道为什么 L-BFGS 不存 $H_k$、成本是 $O(mn)$、需要保存 $s_i,y_i$。

8. Barzilai-Borwein (BB) 梯度法

BB 方法仍是梯度法：

$$x_{k+1}=x_k-t_k\mathrm{\nabla }f(x_k),$$

但步长 $t_k$ 用 secant equation 的标量近似得到。

两种常见 BB 步长：

$$t_k^{BB1}=\frac{s_{k-1}^T{s}_{k-1}}{s_{k-1}^T{y}_{k-1}},t_k^{BB2}=\frac{s_{k-1}^T{y}_{k-1}}{y_{k-1}^T{y}_{k-1}}.$$

直观：用 $tI$ 或 $t^{-1}I$ 去近似 Hessian / inverse Hessian 的 secant relation。

注意：

• BB 常常比固定步长 GD 快很多；
• 它通常不是单调下降；
• 实践中常把步长截断到 $[t_{min},t_{max}]$，再配 nonmonotone line search。

9. Gauss-Newton 与 Levenberg-Marquardt

考虑非线性最小二乘：

$$\underset{x}{min}\frac{1}{2}\parallel g(x){\parallel }^2.$$

Gauss-Newton 每步解线性化后的最小二乘：

$$x_{k+1}=\arg \underset{x}{min}\frac{1}{2}\parallel g(x_k)+J_k(x-x_k){\parallel }^2.$$

对应方向：

$$d_k=-(J_k^T{J}_k{)}^{-1}{J}_k^{T}g(x_k),$$

前提是 $J_k$ 满列秩。

与 Newton 的关系：

$${\mathrm{\nabla }}^2(\frac{1}{2}\parallel g(x){\parallel }^2)=J(x{)}^{T}J(x)+\sum _i{g}_i(x){\mathrm{\nabla }}^2{g}_i(x).$$

Gauss-Newton 丢掉第二项。若残差 $g(x)$ 很小，这个近似很好。

若 $J_k^T{J}_k$ 奇异或病态，使用 Levenberg-Marquardt：

$$d_k=-(J_k^T{J}_k+{\mu }_{k}I{)}^{-1}{J}_k^{T}g(x_k).$$

10. 作业题型对照

作业	题面	考点
A8.2	预条件梯度法	$P=Q^{-1}$ 给出 Newton-like 一步收敛；为拟牛顿思想铺垫
hw9.5	logistic regression 编程	可以把 damped Newton / Newton-CG 与 BFGS/L-BFGS 思路对比：精确二阶 vs 近似二阶
hw10.1	BFGS 的 $B$-更新 $B^{+}=B-\frac{Bs{s}^{T}B}{s^{T}Bs}+\frac{y{y}^T}{s^{T}y}$	证明对称、secant equation $B^{+}s=y$、半正定/正定；说明 $s^{T}y>0$ 不能去掉
hw10.2	$p_k=-H_k\mathrm{\nabla }f(x_k)$ 与 Wolfe curvature condition	证明下降方向；由 Wolfe 推 $s_k^T{y}_k>0$；构造任意步长导致 $s_k^T{y}_k<0$ 的反例；解释 BFGS 更新失败
hw10.3	手算 L-BFGS two-loop recursion	按“先从新到旧，再从旧到新”的两轮递推算 $H_k{g}_k$；比较 $m=20,n={10}^6$ 时 $2mn$ 存储 vs full BFGS 的 $n^2$
hw10.4	Barzilai-Borwein 两个步长	从 $\underset{t}{min}|s-ty{|}^2$ 和 $\underset{t}{min}|\frac{1}{t}s-y{|}^2$ 推 BB1/BB2；用 Rayleigh quotient 证 $1/M\le t_k\le 1/m$
hw10.5	logistic regression 上实现 BFGS + strong Wolfe	写 $\mathrm{\nabla }F(w)$；用 $H$-形式 BFGS；若 $y_k^T{s}_k\le {10}^{-12}$ 跳过更新；比较三组 LIBSVM 数据收敛

11. 解题招式

招式 1：先写 $s_k,y_k$

任何拟牛顿题先写：

$$s_k=x_{k+1}-x_k,y_k=\mathrm{\nabla }f(x_{k+1})-\mathrm{\nabla }f(x_k).$$

再写 secant equation：

$$B_{k+1}{s}_k=y_k\text{或}{H}_{k+1}{y}_k=s_k.$$

招式 2：正定性只看曲率条件

若题目问 BFGS 更新是否保持正定，回答结构：

1. 假设 $H_k\succ 0$；
2. Wolfe 保证 $s_k^T{y}_k>0$；
3. BFGS 更新由两个 PSD 项组成并满足 secant equation；
4. 因此 $H_{k+1}\succ 0$。

招式 3：比较复杂度

方法	每步主要代价	存储	典型使用
Newton	Hessian + 解线性系统，dense 可到 $O(n^3)$	$O(n^2)$	中小规模、高精度
BFGS	矩阵向量乘/更新 $O(n^2)$	$O(n^2)$	中等规模
L-BFGS	$O(mn)$	$O(mn)$	大规模 smooth 问题
BB	$O(n)$ 级别额外成本	$O(n)$	轻量加速 GD
Gauss-Newton	解 $J^{T}Jd=-J^{T}g$	取决于 $J$	非线性最小二乘

12. 自检清单

• [ ] $s_k,y_k$ 的定义能马上写出来吗？
• [ ] Secant equation 是 $B_{k+1}{s}_k=y_k$ 还是 $B_{k+1}{y}_k=s_k$？能区分 $B$ 和 $H$ 吗？
• [ ] 为什么需要 $s_k^T{y}_k>0$？
• [ ] Wolfe 条件第二条如何推出 $s_k^T{y}_k>0$？
• [ ] BFGS 的 $H$-更新公式能认出来吗？
• [ ] L-BFGS 为什么只需要 $O(mn)$？若存 $m$ 对 $(s_i,y_i)$，总共是多少个实数？
• [ ] BB 两个步长公式能写出一个吗？
• [ ] BB 步长在强凸二次上为什么落在 $[1/M,1/m]$？
• [ ] Gauss-Newton 与 Newton 的 Hessian 差在哪一项？

13. 常见陷阱

1. 把 $B_k$ 和 $H_k$ 搞反：$B_k\approx {\mathrm{\nabla }}^{2}f$，$H_k\approx ({\mathrm{\nabla }}^{2}f{)}^{-1}$。
2. 只用 Armijo 不够：Armijo 保证下降，但不保证 $s_k^T{y}_k>0$，拟牛顿更需要 Wolfe。
3. BFGS 不是“无条件正定”：必须有 $H_k\succ 0$ 和 $s_k^T{y}_k>0$。
4. L-BFGS 不是低秩 Hessian：它是不显式形成 $H_k$，只保存有限历史对。
5. BB 不是线搜索得到的最优步长：它是 secant equation 的标量近似，可能非单调。
6. Gauss-Newton 不是通用 Newton 替代品：它专门利用最小二乘结构，残差小的时候尤其有效。

14. 接下来怎么学

本章学完后，你应该能从“精确二阶”过渡到“近似二阶”。下一章 9_次梯度与次梯度法 会切换到不可微凸优化：没有梯度、没有 Hessian 时，如何仍然写最优性条件并设计算法。