对应 note_6_gd.pdf。本章从理论转向数值算法，核心是收敛性证明——这套证明套路一旦掌握，就能解几乎所有 GD/Newton 类的题。

0. 一句话理解这一章

梯度下降 = 在每一步用线性近似 + 二次惩罚来"小心翼翼地往下走"；牛顿法 = 用二次近似精确跳到极小。算法的优劣由 (i) Lipschitz 常数 L、(ii) 强凸常数 μ、(iii) 条件数 $\kappa =L/\mu$ 决定。

1. 知识地图

            梯度下降 (GD)
            ──────────────────────────────
            x_{k+1} = x_k − t_k ∇f(x_k)
                          │
                等价：min  f(x_k) + ∇f(x_k)^T(x − x_k) + 1/(2t)‖x−x_k‖²
                          │
            步长选择：
              - 常数 t < 2/L
              - 精确线搜索（zig-zag）
              - Armijo 回溯（最实用）
                          │
            收敛分析的两块基石：
              ① Lipschitz 梯度  →  二次上界 (Lemma 1.2)
              ② 充分下降引理 (Lemma 1.3)
                          │
            收敛率：
              - 一般非凸：min_i ‖∇f‖² 收敛 (Theorem 1.6)
              - 凸 + L-smooth：O(1/k) (Theorem 1.7)
              - μ-强凸 + L-smooth：(1 − μ/L)^k 线性 (Theorem 1.12)
                
                

            牛顿法 (Newton)
            ──────────────────────────────
            x_{k+1} = x_k − [∇²f(x_k)]^{-1} ∇f(x_k)
                          │
                等价：用二次模型最小化
                          │
            局部二次收敛 (Theorem 2.1)：
              ‖x_{k+1} − x*‖ ≤ (L/2m)‖x_k − x*‖²
              
              

            其它二阶方法
            ──────────────────────────────
            damped Newton（带 Armijo）
            quasi-Newton（DFP, BFGS）—— 用 secant 方程拟合 Hessian
            trust region / cubic regularization
            Gauss-Newton / Levenberg-Marquardt（最小二乘专用）
            BB 方法（轻量级 GD with 自适应步长）

2. 梯度下降法

2.1 基本迭代

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

理解视角（邻近视角 / proximal view）：

$$x_{k+1}=\arg \underset{x}{min}f(x_k)+\mathrm{\nabla }f(x_k{)}^T(x-x_k)+\frac{1}{2t_k}\parallel x-x_k{\parallel }^2.$$

"线性近似 + 二次惩罚" → "majorization minimization"——这正是为什么步长太大会发散，太小会很慢。

2.2 步长策略（要会区分）

策略	公式	优缺点
常数步长	$t_k=\alpha$	简单，但需要知道 $L$；要 $\alpha <2/L$
精确线搜索	$t_k=\arg \underset{s\ge 0}{min}f(x_k+s{p}_k)$	表面贪心，但易"zig-zag"
Armijo 回溯（最实用）	见下	不需要 $L$，鲁棒

Armijo 回溯：选 $\alpha \in (0,1/2)$、$\beta \in (0,1)$、$t_0$（常 1）。从 $t=t_0$ 开始，只要 $f(x_k+t{p}_k)>f(x_k)+\alpha t\mathrm{\nabla }f(x_k{)}^T{p}_k$ 就把 $t$ 缩为 $\beta t$。

几何理解：右边是"目标函数沿 $p_k$ 方向倾斜了 $\alpha$ 倍下降量的直线"——只要 $f$ 落在这条线下方就接受。

为什么 Armijo 一定终止：由一阶 Taylor，$f(x+tp)=f(x)+t\mathrm{\nabla }{f}^{T}p+o(t)<f(x)+\alpha t\mathrm{\nabla }{f}^{T}p$ 对于足够小 $t$ 成立。

2.3 终止判据

$\parallel \mathrm{\nabla }f(x_k)\parallel \le ϵ$、$|f(x_{k+1})-f(x_k)|\le ϵ$、$\parallel x_{k+1}-x_k\parallel \le ϵ$（实际要除以"max(1, ...)" 防止数值问题）。

2.4 GD 的"慢"——"zig-zag" 与条件数

例 (2)：$f(x)=\frac{1}{2}(x_{(1)}^2+\gamma x_{(2)}^2)$，从 $x_0=(\gamma ,1)$ 出发，精确线搜索给：

$$\frac{\parallel x_k-x^{\ast }\parallel }{\parallel x_0-x^{\ast }\parallel }={\left(\frac{\gamma -1}{\gamma +1}\right)}^k.$$

当 $\gamma =10000$ 时，这个比值 $\approx 0.9998$——几千次迭代才能下降一点。

"zig-zag" ：精确线搜索下 $(x_{k+2}-x_{k+1}{)}^T(x_{k+1}-x_k)=0$（连续两步互相垂直）。条件数 $L/\mu$ 越大，GD 越慢。

3. 收敛分析的"两个基石"

基石 1：Lipschitz 梯度 → 二次上界（Lemma 1.2）⭐⭐⭐

若 $\mathrm{\nabla }f$ 是 L-Lipschitz，则

$$f(y)\le f(x)+\mathrm{\nabla }f(x{)}^T(y-x)+\frac{L}{2}\parallel y-x{\parallel }^2,\mathrm{\forall }x,y.$$

证明思路：把 $f(y)-f(x)$ 写成 ${\int }_0^1\mathrm{\nabla }f(x+t(y-x){)}^T(y-x)dt$，减掉 $\mathrm{\nabla }f(x{)}^T(y-x)$ 后用 Cauchy-Schwarz + Lipschitz。

这是后面所有收敛证明的起点。

基石 2：充分下降引理（Lemma 1.3）⭐⭐⭐

若 $\mathrm{\nabla }f$ 是 L-Lipschitz，则

$$f(x)-f(x-t\mathrm{\nabla }f(x))\ge t(1-\frac{Lt}{2})\parallel \mathrm{\nabla }f(x){\parallel }^2.$$

推导：在 Lemma 1.2 中令 $y=x-t\mathrm{\nabla }f(x)$。

当 $t<2/L$ 时右边正——保证下降。当 $t=1/L$ 时右边 $=\frac{1}{2L}\parallel \mathrm{\nabla }f{\parallel }^2$——最常用的"最佳"常数。

4. 收敛性结果（必须会推导）

整套证明的"作业模式"：从 Lemma 1.3 出发 → 与凸/强凸不等式叠加 → 累加（telescoping）→ 得到收敛率。

4.1 一般情形（Theorem 1.5–1.6）

只需 $L$-smooth + $0<t<2/L$：

• $f(x_k)$ 单调不增；
• $\underset{i\le k}{min}\parallel \mathrm{\nabla }f(x_i)\parallel \le \sqrt{\frac{f(x_0)-f^{\ast }}{(k+1)M}}$，$M=t(1-Lt/2)$。
• 即 $\parallel \mathrm{\nabla }f\parallel$ 收敛速度是 $O(1/\sqrt{k})$。对非凸问题这通常已经是最好结果。

4.2 凸 + L-smooth（Theorem 1.7）⭐

$0<t\le 1/L$：

$$f(x_k)-f(x^{\ast })\le \frac{1}{2kt}\parallel x_0-x^{\ast }{\parallel }^2.$$

即 $O(1/k)$。要达 $ϵ$ 精度需 $O(1/ϵ)$ 次。

证明套路（记住这个结构！）：

1. 用 Lemma 1.3 + $t\le 1/L$：$f(x^{+})\le f(x)-\frac{t}{2}\parallel \mathrm{\nabla }f(x){\parallel }^2$。
2. 用凸性 $f(x)\le f(x^{\ast })+\mathrm{\nabla }f(x{)}^T(x-x^{\ast })$ 替 $f(x)$，得：$$f(x^{+})\le f(x^{\ast })+\mathrm{\nabla }f(x{)}^T(x-x^{\ast })-\frac{t}{2}\parallel \mathrm{\nabla }f(x){\parallel }^2.$$
3. 配方：右边 = $f(x^{\ast })+\frac{1}{2t}(\parallel x-x^{\ast }{\parallel }^2-\parallel x^{+}-x^{\ast }{\parallel }^2)$。
4. 累加 $i=1,\dots ,k$：左边 $\sum f(x_i)-f^{\ast }$，右边 telescoping → $\frac{1}{2t}\parallel x_0-x^{\ast }{\parallel }^2$。
5. 用 $f(x_k)\le \frac{1}{k}\sum f(x_i)$（单调性）得最终结果。

这套配方 + telescoping 是本章证明题的核心模板。

4.3 强凸 + L-smooth（Theorem 1.12）⭐

$t=1/L$ 时：

$$f(x_k)-f^{\ast }\le (1-\mu /L{)}^k(f(x_0)-f^{\ast }).$$

线性收敛！达 $ϵ$ 需 $O(\frac{L}{\mu }\log \frac{1}{ϵ})$ 次。

证明：

1. Lemma 1.3 + $t=1/L$：$f(x^{+})-f^{\ast }\le f(x)-f^{\ast }-\frac{1}{2L}\parallel \mathrm{\nabla }f{\parallel }^2$。
2. 强凸的二次下界：$f^{\ast }\ge f(x)-\frac{1}{2\mu }\parallel \mathrm{\nabla }f{\parallel }^2$，移项：$f(x)-f^{\ast }\le \frac{1}{2\mu }\parallel \mathrm{\nabla }f{\parallel }^2$。
3. 代回得 $f(x^{+})-f^{\ast }\le (1-\mu /L)(f(x)-f^{\ast })$。

4.4 关键概念：条件数 $\kappa =L/\mu$

$\kappa$ 决定 GD 的速度：$\kappa$ 越小越好；$\kappa \to 1$ 时一步收敛；$\kappa \to \mathrm{\infty }$ 时极慢。

5. 牛顿法

5.1 标准牛顿法

$$x_{k+1}=x_k-[{\mathrm{\nabla }}^{2}f(x_k){]}^{-1}\mathrm{\nabla }f(x_k).$$

等价视角：在 $x_k$ 处用二次模型 $m_k(p)=f(x_k)+\mathrm{\nabla }{f}^{T}p+\frac{1}{2}{p}^T{\mathrm{\nabla }}^{2}fp$ 最小化 $p$。

5.2 局部二次收敛（Theorem 2.1）⭐⭐

设 $f$ μ-强凸 + ${\mathrm{\nabla }}^{2}f$ L-Lipschitz。则

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

若 $\parallel x_0-x^{\ast }\parallel \le \mu /L$，则 $\parallel x_k-x^{\ast }\parallel \le \frac{2\mu }{L}(1/2{)}^{2^k}$（二次收敛——精度每步翻倍指数级）。

证明思路：

1. $x_{k+1}-x^{\ast }=({\mathrm{\nabla }}^{2}f(x_k){)}^{-1}(\mathrm{\nabla }f(x^{\ast })-\mathrm{\nabla }f(x_k))$ (用 $\mathrm{\nabla }f(x^{\ast })=0$ 代入迭代式)。
2. 用积分中值 $\mathrm{\nabla }f(x^{\ast })-\mathrm{\nabla }f(x_k)={\int }_0^1{\mathrm{\nabla }}^{2}f(x_k+t(x^{\ast }-x_k))(x^{\ast }-x_k)dt$，移项后能写成 Hessian 差 ${\int }_0^1[{\mathrm{\nabla }}^{2}f(x_k+t(x^{\ast }-x_k))-{\mathrm{\nabla }}^{2}f(x_k)]dt$ 乘 $(x^{\ast }-x_k)$。
3. 用 Hessian 的 Lipschitz $\parallel {\mathrm{\nabla }}^{2}f(\cdot )-{\mathrm{\nabla }}^{2}f(x_k)\parallel \le Lt\parallel x^{\ast }-x_k\parallel$，再用 $\parallel ({\mathrm{\nabla }}^{2}f{)}^{-1}\parallel \le 1/\mu$，积出 $\frac{L}{2\mu }\parallel x^{\ast }-x_k{\parallel }^2$。

5.3 阻尼牛顿法（damped Newton, Algorithm 3）

加 Armijo 线搜索，保证全局收敛：

• 计算 Newton 方向 $d_k=-{\mathrm{\nabla }}^2{f}^{-1}\mathrm{\nabla }f$。
• 用 Armijo 选 $t_k$。
• $x_{k+1}=x_k+t_k{d}_k$。

为什么纯 Newton 可能不收敛：远离 $x^{\ast }$ 时 Hessian 可能不正定/二次模型偏差大；damped 版加线搜索作为安全网。

5.4 Newton 法的优劣

优	劣
局部二次收敛（极快）	每步 $O(n^3)$ 求线性系统
仿射不变（不依赖 conditioning）⭐	需要 Hessian $\Rightarrow O(n^2)$ 存储
	远离 $x^{\ast }$ 时不一定下降

仿射不变性：对 $\tilde{f}(y)=f(Ay)$，从 $y_0=A^{-1}{x}_0$ 出发的牛顿迭代 = $A^{-1}$ 乘原迭代。所以条件数对 Newton 没影响——这点比 GD 强很多。

6. 其他二阶方法（仅作了解，考试通常只要识别概念）

6.1 拟牛顿（Quasi-Newton）

用 $B_k\approx {\mathrm{\nabla }}^{2}f(x_k)$ 或 $H_k\approx {\mathrm{\nabla }}^2{f}^{-1}$。

Secant 方程：$B_{k+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)$

经典更新：

• DFP：先更新 $B_k$。
• BFGS（最常用）：直接更新 $H_k=B_k^{-1}$：$$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=1/y_k^T{s}_k.$$

6.2 Trust Region 信赖域 + Cubic Regularization

不是"沿方向走多远"，而是"在半径 ${\mathrm{\Delta }}_k$ 的小球内最小化二次模型"。每步根据"实际下降 vs 模型预测下降"的比 ${\rho }_k$ 调整 ${\mathrm{\Delta }}_k$。

Cubic 正则化：在二次模型上加 $\frac{\rho }{6}\parallel x-x_k{\parallel }^3$ 惩罚，全局收敛率 $O({ϵ}^{-3/2})$（非凸最优）。

6.3 Gauss-Newton 与 Levenberg-Marquardt

针对最小二乘 $\frac{1}{2}\parallel g(x){\parallel }^2$，用线性化 $g(x_k)+J_g(x_k)(x-x_k)$ 近似。

• $x_{k+1}=x_k-(J_k^T{J}_k{)}^{-1}{J}_k^{T}g(x_k)$（GN）。
• $x_{k+1}=x_k-(J_k^T{J}_k+{\mu }_{k}I{)}^{-1}{J}_k^{T}g(x_k)$（LM，对秩亏处理）。

6.4 Barzilai-Borwein (BB)

GD 的步长用 $t_k=\frac{s_{k-1}^T{y}_{k-1}}{y_{k-1}^T{y}_{k-1}}$ 或 $\frac{s_{k-1}^T{s}_{k-1}}{s_{k-1}^T{y}_{k-1}}$。 不是单调的——常配 nonmonotone 线搜索。实际中收敛常常很快，但理论保证弱。

7. 作业题型对照（A8 + hw07.4）

作业	题面	考点
A8.1 / hw07.4	Backtracking 步长下界 + 回溯次数	用强凸的二次上界 $f(x+t\mathrm{\Delta }x)\le f(x)+t\mathrm{\nabla }{f}^T\mathrm{\Delta }x+\frac{M}{2}{t}^2|\mathrm{\Delta }x{|}^2$ → 推 Armijo 条件何时一定成立 → 得 $t\le \frac{-\mathrm{\nabla }{f}^T\mathrm{\Delta }x}{M|\mathrm{\Delta }x{|}^2}$ 时 ok → $t\ge \beta min\{1,\dots \}$ → 回溯次数对数级
A8.2(a)	预条件 GD：$x_{k+1}=x_k-tP\mathrm{\nabla }f$，证 $e_{k+1}=(I-tPQ)e_k$	用 $\mathrm{\nabla }f(x)=Qx-c$，$\mathrm{\nabla }f(x^{\ast })=0$ → $\mathrm{\nabla }f(x_k)=Q(x_k-x^{\ast })=Q{e}_k$；代入迭代式
A8.2(b)	怎么选 $P,t$ 让 1 步到最优	要 $I-tPQ=0$ → 选 $P=Q^{-1},t=1$（这就是 Newton 法）
A8.3(a)	$Lt\in (0,1]$ 下"双倍充分下降" $f(x_n)-f(x_{n+1})\ge \frac{t}{2}|\mathrm{\nabla }f(x_n){|}^2+\frac{t}{2}|\mathrm{\nabla }f(x_{n+1}){|}^2$	关键：在两个端点都用 Lemma 1.3 / Lemma 1.2，再用凸性"梯度单调"或者 A8.4 的"反向不等式"
A8.3(b)	$Lt\in (0,2]$ 下 $|\mathrm{\nabla }f(x_{n+1})|\le |\mathrm{\nabla }f(x_n)|$	用 $|\mathrm{\nabla }f(x^{+}){|}^2-|\mathrm{\nabla }f(x){|}^2$ 的展开 + Lipschitz 梯度
A8.4	$g_x(y)=f(y)-\mathrm{\nabla }f(x{)}^{T}y$	(a) $\mathrm{\nabla }{g}_x(x)=\mathrm{\nabla }f(x)-\mathrm{\nabla }f(x)=0$ + $g_x$ 凸 → $x$ 是 $g_x$ 的极小；(b) $g_x$ 也是 L-smooth + 凸 → 用 Lemma 1.3 + 步长 $1/L$：$g_x(y-\frac{1}{L}\mathrm{\nabla }{g}_x(y))\le g_x(y)-\frac{1}{2L}|\mathrm{\nabla }{g}_x(y){|}^2$，再用 (a) 的 $g_x(x)\le g_x(\cdot )$；(c) 把 (b) 的不等式展开成 $f$ 的形式
A8.5	$t=\phi /L$ 步长，$f(x_k)-f^{\ast }\le \frac{1}{\phi k}\cdot \frac{L}{2}|x_0-x^{\ast }{|}^2$	用题给恒等式 $\frac{L}{2}|x_n-x^{\ast }{|}^2-\frac{L}{2}|x_{n+1}-x^{\ast }{|}^2=\frac{L}{2}|x_n-x_{n+1}{|}^2+L⟨x_n-x_{n+1},x_{n+1}-x^{\ast }⟩$ + 凸性 + Lipschitz；本质是 Theorem 1.7 证明的精细版

复习要点：A8 的所有题都是"GD 的收敛性证明"的变种，核心套路是 §4.2 的"配方 + telescoping"。A8.4 的 $g_x$ 函数是个非常巧妙的"对偶化"工具——通过减去线性项把 $x$ 变成新函数的极小点。

---

8. 解题"招式手册"

招式 1：收敛性证明的"四步走"⭐

(1) 用 Lemma 1.2 (二次上界) 写出 $f(x^{+})\le f(x)+\mathrm{\nabla }{f}^T(x^{+}-x)+\frac{L}{2}\parallel x^{+}-x{\parallel }^2$； (2) 代入 $x^{+}=x-t\mathrm{\nabla }f$，把 $\mathrm{\nabla }{f}^T$ 项与平方项合并； (3) 用凸性（$f(x)\le f(x^{\ast })+\mathrm{\nabla }{f}^T(x-x^{\ast })$）或强凸（$f^{\ast }\ge f(x)-\frac{1}{2\mu }\parallel \mathrm{\nabla }f{\parallel }^2$）把 $f(x)$ 和 $f^{\ast }$ 联系起来； (4) 配方为 $\parallel x-x^{\ast }{\parallel }^2-\parallel x^{+}-x^{\ast }{\parallel }^2$ 形式，telescoping 累加 $k$ 步。

招式 2：Armijo 步长下界证明套路

回溯条件不满足意味着 $f(x+\beta t\mathrm{\Delta }x)>f(x)+\alpha \beta t\mathrm{\nabla }{f}^T\mathrm{\Delta }x$；用二次上界 $\le f(x)+\beta t\mathrm{\nabla }{f}^T\mathrm{\Delta }x+\frac{M}{2}{\beta }^2{t}^2\parallel \mathrm{\Delta }x{\parallel }^2$；两者放在一起得 $t$ 的下界。hw07.4 与 A8.1 标准套路。

招式 3：用辅助函数 $g_x(y)$ 构造"反向"不等式

$g_x(y)=f(y)-\mathrm{\nabla }f(x{)}^{T}y$ 这个技巧把 $f$ 在 $x$ 处的"切线信息"剥离掉。它的极小点是 $x$（A8.4 第 (a) 部分）；它仍然 L-smooth + 凸；对 $g_x$ 应用 Lemma 1.3 给出反向不等式：

$$f(x)+\mathrm{\nabla }f(x{)}^T(y-x)+\frac{1}{2L}\parallel \mathrm{\nabla }f(x)-\mathrm{\nabla }f(y){\parallel }^2\le f(y).$$

这是 GD 收敛性证明里最常用的"硬核工具"。要会推导。

招式 4：识别"等价问题 = 1 步收敛"

$f(x)=\frac{1}{2}{x}^{T}Qx-c^{T}x$（凸二次）+ $P=Q^{-1},t=1$ → 1 步到 $x^{\ast }$。这就是 Newton 法的本质。出现"如何选预条件矩阵"基本是这个答案。

招式 5：用积分中值代替 Hessian 差

Newton 法的二次收敛证明里出现"$\mathrm{\nabla }f(x^{\ast })-\mathrm{\nabla }f(x_k)$"——用 ${\int }_0^1{\mathrm{\nabla }}^{2}f(x_k+t(x^{\ast }-x_k))(x^{\ast }-x_k)dt$ 替代，再加减 ${\mathrm{\nabla }}^{2}f(x_k)$。

---

9. 自检清单

• [ ] GD 的等价"邻近视角"：$\arg minf(x_k)+\mathrm{\nabla }{f}^T(x-x_k)+\frac{1}{2t}\parallel x-x_k{\parallel }^2$？
• [ ] Armijo 回溯的具体形式（$\alpha ,\beta ,t_0$）？
• [ ] Lemma 1.2 / Lemma 1.3 的命题与证明？
• [ ] 凸 + L-smooth：$O(1/k)$ 收敛——证明能复现吗？
• [ ] 强凸 + L-smooth：$(1-\mu /L{)}^k$ 线性——证明能复现吗？
• [ ] 条件数 $\kappa =L/\mu$ 的含义？为什么 GD 慢、Newton 不慢？
• [ ] Newton 法的二次收敛 + 仿射不变？
• [ ] BFGS 的 secant 方程？
• [ ] Gauss-Newton 与 Newton 的差别？

10. 常见陷阱

1. L 的两种含义：本章 $L$ 通常指梯度的 Lipschitz 常数（$\mathrm{\nabla }f$ 是 L-Lipschitz）。但讲义里常把 $L$ 当成 Hessian 的 Lipschitz 常数（Newton 法 Theorem 2.1）。做题前先看 L 修饰的是 $\mathrm{\nabla }f$ 还是 ${\mathrm{\nabla }}^{2}f$。
2. 强凸 ≠ 严格凸 ≠ 凸：$f(x)=x^4$ 严格凸但不是强凸。
3. GD 的常数步长上界：$t<2/L$（保证下降）；$t\le 1/L$（凸情形 $O(1/k)$ 证明用）；$t=1/L$（强凸情形 $(1-\mu /L)$ 用）。题目里的 "Lt∈(0,1]" 与 "Lt∈(0,2]" 是两种典型设定（A8.3）。
4. "凸性给的不等式" vs "强凸给的不等式"：
   • 凸：$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$（线性下界）；
   • L-smooth：$f(y)\le f(x)+\mathrm{\nabla }f(x{)}^T(y-x)+\frac{L}{2}\parallel y-x{\parallel }^2$（二次上界）；
   • μ-强凸：$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)+\frac{\mu }{2}\parallel y-x{\parallel }^2$（二次下界）。 做题时不要混用，每个不等式有自己的"假设"。
5. 互补松弛 / KKT 与 Newton 法没什么关系——这章是无约束的。
6. Newton 法的二次收敛要 $\parallel x_0-x^{\ast }\parallel \le m/L$：远的话不一定收敛。这就是为什么实际中要用 damped Newton。

---

11. 完整学完六章后应当做到

1. 判凸 + 建模：拿到一个问题，能在 5 分钟内决定它是不是凸的、属于哪个标准形（LP/QP/SOCP/SDP），并写出标准形。
2. 写 KKT + 写对偶：拿到任何凸问题，能徒手写 KKT、写 Lagrangian、写对偶问题；能用对偶反解原最优。
3. 算法收敛性：能从 Lipschitz/凸/强凸假设出发，复现 $O(1/k)$ 与 $(1-\mu /L{)}^k$ 两条收敛率证明的全部步骤；能改造证明做 A8 这类变种题。
4. 不被"陷阱"骗：知道 Slater 在哪一步用、CLP 强对偶为什么需要严格可行、Newton 在哪种情形会失效、SDR 什么时候紧。

12. 最后的复习路线（期中）

建议按这个顺序刷一遍所有作业：

1. A1, A2, A3 → 检测 Ch2 凸性判定与 Ch3 建模（用时 1 天）。
2. A6.1 → 检测 Ch4 KKT（半天）。
3. A5, A6.2-4, hw07.5 → 检测 Ch5 对偶（1.5 天）。
4. A8, hw07.4 → 检测 Ch6 GD 收敛性证明（1 天）。
5. hw07.1-3 → 综合 Ch3 SOCP/SDP 建模（半天）。

总用时 ≈ 4-5 天。做完每道题后，如果不能在 5 分钟内说清"这题考了什么知识点 + 什么招式"，就回头重看对应学习指导。

---

至此 Lecture 6 的一阶算法主线已经覆盖。Newton 法在本章只是作为二阶方法入口；更完整的阻尼 Newton、inexact Newton 和 self-concordant 分析见 7_牛顿法，拟牛顿和 L-BFGS 见 8_拟牛顿法。