对应 note_7_newton.pdf。这一章把第六章中的 Newton 概念展开成完整算法：Newton 方向、Newton decrement、阻尼 Newton、inexact Newton，以及 self-concordant 函数下的复杂度分析。

0. 一句话理解这一章

Newton 法 = 每一步最小化二阶 Taylor 模型；阻尼 Newton 用线搜索保证全局下降；靠近最优解后自动接受 $t=1$，进入二次收敛。Newton decrement 是这章的核心量。

1. 知识地图

            二阶模型
            m_k(p)=f(x_k)+∇f(x_k)^T p+1/2 p^T∇²f(x_k)p
                          │
                          ▼
            Newton 方向 d_k = -[∇²f(x_k)]^{-1}∇f(x_k)
                          │
                          ├── descent direction：∇f^T d_k < 0
                          ├── affine invariant：坐标变换不影响本质迭代
                          └── Newton decrement：λ(x)^2 = -∇f(x)^T d(x)
                          │
                          ▼
            阻尼 Newton
              先试 t=1，不满足 Armijo 就回溯
                          │
                          ▼
            两阶段收敛
              Phase 1：每步至少下降 γ
              Phase 2：t=1，二次收敛
                          │
                          ▼
            扩展
              inexact Newton / Newton-CG
              self-concordant 分析

2. Newton 方向与 decrement

2.1 从二阶模型推出 Newton 步

在 $x_k$ 处用二阶 Taylor 模型：

$$m_k(p)=f(x_k)+\mathrm{\nabla }f(x_k{)}^{T}p+\frac{1}{2}{p}^T{\mathrm{\nabla }}^{2}f(x_k)p.$$

若 ${\mathrm{\nabla }}^{2}f(x_k)\succ 0$，一阶最优性条件给出：

$${\mathrm{\nabla }}^{2}f(x_k)p+\mathrm{\nabla }f(x_k)=0,d_k=p=-[{\mathrm{\nabla }}^{2}f(x_k){]}^{-1}\mathrm{\nabla }f(x_k).$$

实际计算时不要显式求逆，而是解线性方程：

$${\mathrm{\nabla }}^{2}f(x_k)d_k=-\mathrm{\nabla }f(x_k).$$

这也是 hw9 的核心：写 Newton system、说明 Hessian 正定、用 Cholesky/CG 求方向。

2.2 Newton 方向为什么下降

若 $\mathrm{\nabla }f(x_k)\ne 0$ 且 ${\mathrm{\nabla }}^{2}f(x_k)\succ 0$，则

$$\mathrm{\nabla }f(x_k{)}^T{d}_k=-\mathrm{\nabla }f(x_k{)}^T[{\mathrm{\nabla }}^{2}f(x_k){]}^{-1}\mathrm{\nabla }f(x_k)<0.$$

所以 Newton 方向是下降方向，可以配 Armijo 回溯。

2.3 Newton decrement

定义：

$$\lambda (x)={(\mathrm{\nabla }f(x{)}^T[{\mathrm{\nabla }}^{2}f(x){]}^{-1}\mathrm{\nabla }f(x))}^{1/2}.$$

等价形式：

$$\lambda (x{)}^2=-\mathrm{\nabla }f(x{)}^{T}d(x),\lambda (x{)}^2=d(x{)}^T{\mathrm{\nabla }}^{2}f(x)d(x).$$

二阶模型下：

$$f(x)-\underset{y}{inf}\hat{f}(y)=\frac{1}{2}\lambda (x{)}^2.$$

因此 $\lambda (x{)}^2/2$ 可以看成“用二阶模型估计的剩余 optimality gap”，也是 Newton 法常用停止准则：

$$\frac{\lambda (x_k{)}^2}{2}\le ϵ.$$

3. 阻尼 Newton 法

算法框架：

1. 解 ${\mathrm{\nabla }}^{2}f(x_k)d_k=-\mathrm{\nabla }f(x_k)$。
2. 从 $t=1$ 开始做 Armijo 回溯，直到$$f(x_k+t{d}_k)\le f(x_k)+\alpha t\mathrm{\nabla }f(x_k{)}^T{d}_k.$$
3. 更新 $x_{k+1}=x_k+t_k{d}_k$。
4. 用 ${\lambda }^2/2\le ϵ$ 或 $\parallel \mathrm{\nabla }f\parallel \le ϵ$ 停止。

和纯 Newton 的区别：

方法	步长	适用状态
纯 Newton	固定 $t=1$	已经靠近最优解，Hessian 正定且模型可信
阻尼 Newton	Armijo 回溯选 $t$	全局更稳，远离最优点也能下降
modified Newton	解 $({\mathrm{\nabla }}^{2}f+\mu I)d=-\mathrm{\nabla }f$	Hessian 可能不定或病态
inexact Newton	线性系统只近似求解	大规模问题，常配 CG

4. 收敛分析：两阶段图景

讲义假设：

$$mI⪯{\mathrm{\nabla }}^{2}f(x)⪯MI,\parallel {\mathrm{\nabla }}^{2}f(x)-{\mathrm{\nabla }}^{2}f(y)\parallel \le L\parallel x-y\parallel .$$

4.1 Phase 1：阻尼阶段

当 $\parallel \mathrm{\nabla }f(x_k)\parallel \ge \eta$ 时，线搜索保证每步至少有固定下降：

$$f(x_{k+1})-f(x_k)\le -\gamma .$$

含义：还没靠近最优点时，算法不一定快，但一定在稳定下降；因为目标值不能无限下降，所以这种“慢阶段”的迭代次数有限。

4.2 Phase 2：二次收敛阶段

当 $\parallel \mathrm{\nabla }f(x_k)\parallel <\eta$ 后，回溯会接受 $t=1$，并且

$$\parallel \mathrm{\nabla }f(x_{k+1})\parallel \le \frac{L}{2m^2}\parallel \mathrm{\nabla }f(x_k){\parallel }^2.$$

这就是二次收敛：误差大致平方级下降。等价地，在距离形式中常见结论是

$$\parallel x_{k+1}-x^{\ast }\parallel \le \frac{L}{2m}\parallel x_k-x^{\ast }{\parallel }^2.$$

复习时不要只背“Newton 很快”，要能说清楚：快发生在靠近解且 $t=1$ 被接受以后。

5. Affine invariance

若做变量变换 $x=Ty$，定义 $\overline{f}(y)=f(Ty)$，则

$$\mathrm{\nabla }\overline{f}(y)=T^T\mathrm{\nabla }f(x),{\mathrm{\nabla }}^2\overline{f}(y)=T^T{\mathrm{\nabla }}^{2}f(x)T.$$

对应的 Newton 方向满足

$$d_{\overline{f}}(y)=T^{-1}{d}_f(x).$$

所以如果 $x_0=T{y}_0$，两边迭代始终满足 $x_k=T{y}_k$。这说明 Newton 法本质上不受线性坐标变换影响；相比之下，梯度下降会明显受条件数影响。

6. Inexact Newton / Newton-CG

精确 Newton 要解

$${\mathrm{\nabla }}^{2}f(x_k)p_k=-\mathrm{\nabla }f(x_k).$$

大规模时可以允许残差

$$r_k={\mathrm{\nabla }}^{2}f(x_k)p_k+\mathrm{\nabla }f(x_k)\ne 0,\parallel r_k\parallel \le {\eta }_k\parallel \mathrm{\nabla }f(x_k)\parallel .$$

讲义结论：

${\eta }_k$ 选择	收敛含义
${\eta }_k\le t<1$	局部线性收敛
${\eta }_k\to 0$	超线性收敛
${\eta }_k=O(|\mathrm{\nabla }f(x_k)|)$ 且 Hessian Lipschitz	二次收敛

实践理解：

• ${\eta }_k=0.5$：方向比较粗，便宜，但靠近解时通常只能保证线性级别。
• ${\eta }_k=min\{0.5,\parallel \mathrm{\nabla }f(x_k)\parallel \}$：远处粗算、近处精算，更符合 Newton-CG 的常用策略。

7. Modified Newton

当 ${\mathrm{\nabla }}^{2}f(x_k)$ 可能不定或病态时，用

$$({\mathrm{\nabla }}^{2}f(x_k)+{\mu }_{k}I)d_k=-\mathrm{\nabla }f(x_k).$$

只要

$${\mathrm{\nabla }}^{2}f(x_k)+{\mu }_{k}I\succ 0,$$

就有

$$\mathrm{\nabla }f(x_k{)}^T{d}_k=-\mathrm{\nabla }f(x_k{)}^T({\mathrm{\nabla }}^{2}f(x_k)+{\mu }_{k}I{)}^{-1}\mathrm{\nabla }f(x_k)<0.$$

所以 $d_k$ 是下降方向。hw9 第 4 题基本就在考这个判断。

8. Self-concordant 函数

8.1 定义与例子

一元凸函数 $f$ self-concordant 若

$$|f^{‴}(x)|\le 2(f^{″}(x){)}^{3/2}.$$

多元情形要求任意直线限制 $g(t)=f(x+tv)$ 都 self-concordant。

典型例子：

• 线性函数、二次函数；
• $-\log x$；
• $-\sum _i\log (b_i-a_i^{T}x)$；
• $-\log detX$；
• SOC barrier $-\log (y^2-x^{T}x)$。

8.2 为什么重要

Self-concordant 分析的优点：

• 不需要知道 $m,M,L$ 这些全局常数；
• 对仿射变换不敏感；
• 是内点法 barrier 分析的核心工具。

讲义中的关键结论：

若 $\lambda (x)<1$ 且 $x^{+}=x-[{\mathrm{\nabla }}^{2}f(x){]}^{-1}\mathrm{\nabla }f(x)$，则

$$\lambda (x^{+})\le \frac{\lambda (x{)}^2}{(1-\lambda (x){)}^2}.$$

当 $\lambda (x_k)\le \eta \le 1/4$ 时，线搜索接受 $t=1$，并且

$$2\lambda (x_{k+1})\le (2\lambda (x_k){)}^2.$$

这就是用 Newton decrement 表达的二次收敛。

9. 作业题型对照

作业	题面	考点
A8.1 / hw07.4	回溯线搜索步长下界	用二次上界推 Armijo 一定成立的步长范围；这是阻尼 Newton 的线搜索基础
A8.2	预条件梯度法一轮到达最优	选 $P=Q^{-1},t=1$；本质上就是二次函数上的 Newton 法
hw9.1	$\sum _i\sqrt{1+(a_i^{T}x-b_i{)}^2}+\rho |x{|}^2/2$	证明凸性；写 $\mathrm{\nabla }f,{\mathrm{\nabla }}^{2}f$；写 Newton system 和 decrement
hw9.2	log-sum-exp + 正则项	写梯度/Hessian；描述阻尼 Newton + backtracking；停止准则用 ${\lambda }^2/2$
hw9.3	链式 logistic 结构 Hessian 三对角	识别 Hessian sparsity；用三对角线性系统 $O(n)$ 求 Newton 方向
hw9.4	modified / inexact Newton	$\mu I$ 保证正定；残差条件 $|r_k|\le {\eta }_k|\mathrm{\nabla }f|$；解释 ${\eta }_k$ 对局部收敛率的影响
hw9.5	logistic regression 编程	实现 damped Newton 和 inexact Newton-CG；比较目标值和梯度范数收敛曲线

10. 解题招式

招式 1：遇到 Newton 题先写三件事

$$H_k={\mathrm{\nabla }}^{2}f(x_k),g_k=\mathrm{\nabla }f(x_k),H_k{d}_k=-g_k.$$

然后再写

$${\lambda }_k^2=-g_k^T{d}_k.$$

这几乎覆盖所有 Newton 基础题。

招式 2：证明 Hessian 正定

常见套路：

• 目标函数是“凸项 + $\rho \parallel x{\parallel }^2/2$”且 $\rho >0$，所以 Hessian $⪰\rho I$；
• Hessian 形如 $A^{T}DA+\rho I$，其中 $D⪰0$，故 $\succ 0$；
• modified Newton 中直接选 $\mu >-{\lambda }_{min}({\mathrm{\nabla }}^{2}f)$。

招式 3：不要写 $H^{-1}$，写“解线性系统”

理论公式可写 $d=-H^{-1}g$，但算法实现和作业说明应写：

• dense 小规模：Cholesky；
• sparse / structured：利用结构，如三对角 $O(n)$；
• 大规模：CG 求 $Hd=-g$，只需要 Hessian-vector product。

招式 4：线搜索证明从二次上界开始

若 $H⪯MI$，则

$$f(x+td)\le f(x)+t\mathrm{\nabla }f(x{)}^{T}d+\frac{M}{2}{t}^2\parallel d{\parallel }^2.$$

把右边和 Armijo 条件比较，就能推出步长下界。

11. 自检清单

• [ ] 能从二阶模型推出 Newton system 吗？
• [ ] 能解释为什么 Newton 方向是下降方向吗？
• [ ] 能写出 $\lambda (x{)}^2=-\mathrm{\nabla }f(x{)}^{T}d(x)$ 吗？
• [ ] 能说明为什么停止准则常用 ${\lambda }^2/2\le ϵ$ 吗？
• [ ] 阻尼 Newton 的 Armijo 条件会写吗？
• [ ] 两阶段收敛：Phase 1 固定下降、Phase 2 二次收敛，能说清楚吗？
• [ ] Inexact Newton 的残差条件和 ${\eta }_k$ 对收敛率的影响能解释吗？
• [ ] Hessian 稀疏/三对角时，知道不要用 dense Cholesky 吗？
• [ ] self-concordant 的典型例子能列出 3 个吗？

12. 常见陷阱

1. 显式求逆是坏写法：代码和算法描述都应写“解线性系统”，不是 inv(H)*g。
2. Newton 快不是全局快：远离最优解时需要阻尼；二次收敛只在局部阶段出现。
3. Hessian 不正定时 Newton 方向可能不是下降方向：这时要 modified Newton、trust region 或回退到梯度方向。
4. ${\lambda }^2/2$ 是模型 gap，不是永远等于真实 gap：self-concordant 或局部分析下才有更强解释。
5. Inexact Newton 残差越小越好但越贵：远处粗算、近处精算是实际算法的关键。
6. 结构化 Hessian 不要当 dense 矩阵处理：三对角、低秩加对角、稀疏结构都应该影响复杂度分析。

13. 接下来怎么学

学完本章后，直接做 hw9 第 1-5 题，尤其第 5 题。然后进入 8_拟牛顿法，学习如何在不显式计算 Hessian 的情况下保留 Newton 的加速效果。