第 21 课|第三周复盘:GD、AGD、PL 与线搜索的统一收敛框架

日期:2026-11-09|第 3 周第 7 天(复盘)|讲授约 18 分钟,自测另计。

本节不是新增大型理论,而是把第 15—20 课的定理假设、可证结论与反例放在一张图里。重点是:“下降”“接近驻点”“接近最优值”“变量接近最优点”并非同一个断言。

一、一个统一问题与三类误差指标

考虑无约束问题 $\min_{x\in\mathbb R^n}f(x)$,记 $g_k=\nabla f(x_k)$。按需要分别假设:

  • Smooth:$|\nabla f(x)-\nabla f(y)|\le L|x-y|$,$L>0$;
  • 凸性:$f(y)\ge f(x)+\nabla f(x)^T(y-x)$;
  • 强凸性:上式右端增加 $\frac\mu2|y-x|^2$,$\mu>0$;
  • PL 条件:$\frac12|\nabla f(x)|^2\ge\mu(f(x)-f^)$,其中 $f^$ 已达到。

要分别识别:$|\nabla f(x_k)|^2$(驻点性)、$f(x_k)-f^$(最优值误差)、$|x_k-x^|^2$(到指定最优点的距离)。一般非凸函数可以存在非最优驻点;最优解不唯一时,函数值接近最优不代表接近某个预先指定的最优点。

假设 方法 可证明的结论 不能偷换成什么
凸且 L-Smooth(最优解存在) GD,步长 1/L 最后一步函数值误差 $O(1/K)$ 不直接保证任意非凸函数全局最优
L-Smooth、下有界 GD,步长 1/L 最佳梯度范数平方 $O(1/K)$ 驻点未必全局最优
L-Smooth + μ-PL GD,步长 1/L 函数值误差 $O((1-\mu/L)^K)$ 不要求强凸或最优解唯一
凸且 L-Smooth(最优解存在) 合规参数的 Nesterov AGD 最后一步函数值误差 $O(1/K^2)$ 不保证逐步目标值单调
L-Smooth + 负梯度 + 下有界 Armijo 回溯 GD 有限终止;梯度范数趋零 不能宣称非凸全局最优
下降方向 + Wolfe + 正定初始 BFGS 矩阵 BFGS 更新 $s_k^Ty_k>0$ 且保持正定 需要更多假设证明算法收敛

二、统一起点:下降引理(证明)

设 $d=y-x$。由微积分基本定理与梯度 Lipschitz 条件, \(\begin{aligned} f(y)-f(x)&=\int_0^1\nabla f(x+td)^Td\,dt\\ &=\nabla f(x)^Td+ \int_0^1[\nabla f(x+td)-\nabla f(x)]^Td\,dt\\ &\le \nabla f(x)^Td+ \int_0^1Lt\|d\|^2\,dt\\ &=\nabla f(x)^Td+\frac L2\|d\|^2. \end{aligned}\)

取 $y=x-\frac1L\nabla f(x)$,得到 GD 的充分下降: \(\boxed{f(x_{k+1})\le f(x_k)-\frac1{2L}\|g_k\|^2.}\tag{1}\) 这个不等式只要求 Smooth,不要求凸性。

如果函数还有下界 $f_{\inf}>-\infty$,将 (1) 对 $k=0,\ldots,K-1$ 求和: \(\frac1{2L}\sum_{k=0}^{K-1}\|g_k\|^2 \le f(x_0)-f(x_K)\le f(x_0)-f_{\inf}.\) 于是 \(\boxed{\min_{0\le k<K}\|g_k\|^2\le \frac{2L(f(x_0)-f_{\inf})}{K}.}\tag{2}\) 这是最佳梯度平方界,而非非凸全局最优值界。 进一步,若算法无限执行,非负级数 $\sum_k|g_k|^2$ 有界,故 $|g_k|\to0$;它仍不排除停在非最优驻点。

三、再加凸性:如何严格得到 $O(1/K)$?

假设 $f$ 凸、$L$-Smooth,且存在最优点 $x^$。凸性给出 \(f(x_k)-f^*\le g_k^T(x_k-x^*).\) 与下降引理合并: \(f(x_{k+1})-f^*\le g_k^T(x_k-x^*)-\frac1{2L}\|g_k\|^2.\) 而平方距离恒等式为 \(\|x_{k+1}-x^*\|^2=\|x_k-x^*\|^2-\frac2L g_k^T(x_k-x^*)+\frac1{L^2}\|g_k\|^2.\) 故 \(\boxed{ f(x_{k+1})-f^* \le\frac L2\big(\|x_k-x^*\|^2-\|x_{k+1}-x^*\|^2\big). }\tag{3}\) 求和,并用 GD 的函数值单调性可知,每个 $f(x_{k+1})-f^\ge f(x_K)-f^*$,因此 \(\boxed{f(x_K)-f^*\le\frac{L\|x_0-x^*\|^2}{2K}.}\tag{4}\) 这是最后一步的函数值误差保证。推导中新增的决定性条件是凸性,而非 Smooth 本身。

四、再加 PL:为什么不必强凸也有几何收敛?

如果另外有 $\mu$-PL: \(\frac12\|g_k\|^2\ge\mu(f(x_k)-f^*),\) 则将它代入 (1): \(\begin{aligned} f(x_{k+1})-f^*&\le f(x_k)-f^*-\frac1{2L}\|g_k\|^2\\ &\le(1-\mu/L)(f(x_k)-f^*). \end{aligned}\) 递推即得 \(\boxed{f(x_K)-f^*\le(1-\mu/L)^K(f(x_0)-f^*).}\tag{5}\) 该证明没有使用凸性。强凸足以推出 PL,但不是必要条件。

典型反例:$F(u,v,w)=\frac12(u^2+4v^2)$。其 Hessian 为 $\operatorname{diag}(1,4,0)$,有零特征值,故不强凸;最优点集合 ${(0,0,w):w\in\mathbb R}$ 也不唯一。但是 \(\frac12\|\nabla F\|^2=\frac12(u^2+16v^2)\ge F-F^*,\) 故它满足 $1$-PL 且 $4$-Smooth,GD 仍有函数值几何收敛。

五、AGD 在哪里获得额外一个 $1/K$?

第 16 课的凸 Nesterov 三序列算法令 \(A_0=0,\quad y_0=z_0=x_0,\quad A_{k+1}=A_k+a,\quad La^2=A_{k+1},\) \(u=\frac{A_ky_k+az_k}{A_{k+1}},\quad g=\nabla f(u),\quad y_{k+1}=u-g/L,\quad z_{k+1}=z_k-ag.\) 在凸且 Smooth 的假设下,构造势函数 \(E_k=A_k(f(y_k)-f^*)+\tfrac12\|z_k-x^*\|^2.\) 用 Smooth 下降引理、分别针对 $y_k,x^$ 的凸性下界、以及 $z$ 的平方距离展开,可整理为 \(\begin{aligned} E_{k+1}-E_k &\le g^T[A_k(u-y_k)+a(u-z_k)]\\ &\quad+\tfrac12(a^2-A_{k+1}/L)\|g\|^2=0. \end{aligned}\) 其中第一项因 $A_{k+1}u=A_ky_k+az_k$ 消失,第二项因 $La^2=A_{k+1}$ 消失。因此 $E_k\le E_0=|x_0-x^|^2/2$。再由权重递推得到 $A_K\ge(K+1)^2/(4L)$($K\ge1$),故 \(\boxed{f(y_K)-f^*\le \frac{2L\|x_0-x^*\|^2}{(K+1)^2}.}\tag{6}\) 这说明 $O(1/K^2)$ 依赖特定的外推—权重—势函数结构,而不是“任意 Momentum 都加速”。势函数不增也不意味着每步 $f(y_k)$ 必然不增。

六、未知 $L$ 时:Armijo、Wolfe 分别控制什么?

令 $p_k$ 为严格下降方向,$g_k^Tp_k<0$,更新 $x_{k+1}=x_k+\alpha_kp_k$。

Armijo(充分下降): \(f(x_k+\alpha p_k)\le f(x_k)+c_1\alpha g_k^Tp_k,\quad 0<c_1<1.\) 对 $p_k=-g_k$,下降引理保证 $\alpha\le2(1-c_1)/L$ 一定通过;回溯系数 $\beta\in(0,1)$、每轮固定初始试探步长 $\bar\alpha>0$ 时, \(\boxed{\alpha_k\ge\min\{\bar\alpha,\,2\beta(1-c_1)/L\}>0.}\tag{7}\) 这说明回溯有限终止,并给出可用于非凸驻点收敛分析的统一步长下界。

弱 Wolfe(曲率条件) 再要求: \(\nabla f(x_k+\alpha p_k)^Tp_k\ge c_2g_k^Tp_k,\quad c_1<c_2<1.\) 设 $s_k=\alpha p_k$、$r_k=g_{k+1}-g_k$(这里用 $r$ 表示梯度差,避免与 Nesterov 序列 $y$ 混淆),则 \(\begin{aligned} s_k^Tr_k &=\alpha(g_{k+1}-g_k)^Tp_k\\ &\ge \alpha(c_2-1)g_k^Tp_k\\ &=\alpha(1-c_2)(-g_k^Tp_k)>0. \end{aligned}\tag{8}\) 这正是 BFGS 更新保持正定性的关键曲率条件。但只要矩阵正定还不足以保证 BFGS 全局收敛:Zoutendijk 型结果首先限制 $\sum_k\cos^2\theta_k|g_k|^2$,要进一步推导 $|g_k|\to0$,还需如统一方向角度下界等条件。

Strong Wolfe 用 $ \nabla f(x_k+\alpha p_k)^Tp_k \le c_2 g_k^Tp_k $ 进一步限制过冲。普通 Armijo 只会缩步;Wolfe 曲率不满足时,候选步长可能恰好太小,需要扩展区间再 Zoom,不能简单只缩不增。

七、两轮数值复盘:固定 GD 与 Armijo

取 \(f(u,v)=\tfrac12(u^2+4v^2),\quad \nabla f=(u,4v),\quad (u_0,v_0)=(2,1).\) Hessian $\operatorname{diag}(1,4)$,故 $\mu=1,L=4$,$f_0=4$。

固定 GD,步长 $1/L=1/4$: \((u_1,v_1)=(1.5,0),\ f_1=1.125;\qquad (u_2,v_2)=(1.125,0),\ f_2=0.6328125.\)

Armijo: 取 $c_1=1/4,\beta=1/2$,每轮从 $\bar\alpha=1$ 开始。起始梯度 $(2,4)$,梯度范数平方为 $20$;第一轮检查 $f(x_0-\alpha g_0)\le4-5\alpha$:

试探步长 候选点 候选函数值 右端阈值 判断
$1$ $(0,-3)$ $18$ $-1$ 拒绝
$1/2$ $(1,-1)$ $2.5$ $1.5$ 拒绝
$1/4$ $(1.5,0)$ $1.125$ $2.75$ 接受

第二轮从 $(1.5,0)$ 再试 $\alpha=1$,直接到 $(0,0)$,$f=0\le1.125-\frac14(1)(1.5)^2=0.5625$,接受。

这个例子中自适应步长在第二轮更快,但不能据此断言 Armijo 对所有问题都比固定步长或 AGD 快。它多次评估函数,而迭代复杂度不等同于运行时间。

八、失败反例与边界最优复习

失败 1:非凸驻点不是全局最优。 $f(t)=1-\cos t$ 全局 $1$-Smooth、下有界,但 $f’(\pi)=0$ 且 $f(\pi)=2>f(0)=0$。所以 (2) 的梯度范数界不能误读成非凸全局最优保证。

失败 2:步长过大会发散。 对 $f(t)=\frac12t^2$,固定 $\alpha=3$ 得 $t_{k+1}=-2t_k$,函数值每步变成四倍;强凸与 Smooth 也无法拯救非法步长。

失败 3:Armijo 不保证 BFGS 正曲率。 对 $f(t)=(t^2-1)^2$,从 $0.1$ 走到 $0.2$ 可使目标从 $0.9801$ 降至 $0.9216$ 并通过 $c_1=0.1$ 的 Armijo,但 $s=0.1$、梯度差 $-0.372$,故 $s^Ty=-0.0372<0$。

KKT 知识回扣: 无约束最优点满足 $\nabla f(x^)=0$;有约束时边界最优可以有非零原始梯度。例如 $\min_{x\le1}\frac12(x-2)^2$ 的 $x^=1$,约束活跃且 $\lambda^=1$,驻点 $-1+1=0$,互补松弛 $\lambda^(x^-1)=0$。另外,活跃不意味着乘子必正:$\min_{x\le0}\frac12x^2$ 在 $x^=0$ 约束活跃,却有合法最优乘子 $\lambda^*=0$。

九、判断流程图

flowchart TD
    A["目标函数满足 L-Smooth 吗?"] --> B["GD 合法步长:下降引理"]
    B --> C["仅下有界:梯度平方的 O(1/K) 界"]
    B --> D["加凸性且最优点存在"]
    D --> E["GD 最后一步函数值 O(1/K)"]
    D --> F["合规 Nesterov 势函数"]
    F --> G["AGD 最后一步函数值 O(1/K²)"]
    B --> H["加 PL 条件(可非凸)"]
    H --> I["GD 函数值几何收敛"]
    B --> J["L 未知:Armijo 回溯"]
    J --> K["充分下降与正步长下界"]
    K --> L["如需 BFGS 曲率:Wolfe"]
    L --> M["sᵀy 大于零,但仍需其他收敛假设"]

十、今日四级自测(100 分)

首次发送不附标准答案,不公布正确选项、数值答案及开放题评分要点。不要提前查看独立测验 JSON,以免泄题。 前三题客观评分,第四题按证明步骤评分。自测成绩不会改变日期与课号。

Lv1|条件与收敛保证辨析|15 分|预计 2 分钟|单选

对无约束可微优化,下列哪项一定正确?

A. 只要函数是全局 $L$-Smooth,梯度下降便保证收敛到全局最优值。

B. 若函数满足 $L$-Smooth 与正的 PL 条件,采用步长 $1/L$ 的 GD 可使函数值误差几何收敛;不必额外假设凸性或唯一最优点。

C. 某条不等式约束在最优点活跃,KKT 乘子就必须严格为正。

D. 只要使用 Nesterov 加速,目标函数值就必定每步单调下降。

提示:分别检查 Smooth、PL、KKT 互补松弛和 AGD 势函数控制的是哪一种量。

Lv2|Armijo 回溯的首次接受步长|20 分|预计 3 分钟|数值

给定 $f(t)=\tfrac12(t-4)^2$,在 $t_0=0$ 沿负梯度方向进行 Armijo 回溯。取 $c=0.25$、初始试探步长 $\alpha_0=3$、缩步因子 $\beta=0.5$,按 $3,1.5,0.75,\ldots$ 依次检查。求首次接受的步长 $\alpha$(保留三位小数,仅填写数值)。

提示:计算 $f(0)$、$g=f’(0)$,依次检查 $f(0-\alpha g)\le f(0)-c\alpha g^2$;等号也算通过。

Lv3|Wolfe、Strong Wolfe 的区间判别|25 分|预计 5 分钟|单选

对 $f(t)=\tfrac12t^2$,从 $t_0=2$ 取方向 $p=-2$,定义 $\phi(\alpha)=f(2-2\alpha)$。设 $c_1=0.1,c_2=0.4$,比较候选步长 $\alpha=0.25,0.75,1.6$。哪一项正确?

A. $\alpha=0.25$ 同时满足 Armijo 与弱 Wolfe。

B. $\alpha=0.75$ 满足 Strong Wolfe;$\alpha=1.6$ 满足弱 Wolfe 但不满足 Strong Wolfe。

C. $\alpha=1.6$ 因为过冲,所以连 Armijo 也不满足。

D. $\alpha=0.75$ 满足 Armijo,但由于方向导数仍为负,故不满足弱 Wolfe。

提示:先求 $\phi(\alpha)=2(1-\alpha)^2$ 和 $\phi’(\alpha)=-4+4\alpha$,把三个条件化为各自的步长区间。

Lv4|四项统一证明:GD、PL、Wolfe 与 KKT|40 分|预计 12 分钟|开放证明

完成以下四个彼此相关但假设不同的任务,必须明确各自结论所需的条件。

A(12 分)凸 GD: 设 $f:\mathbb R^n\to\mathbb R$ 凸且 $L$-Smooth,最优点 $x^*$ 存在。对 $x_{k+1}=x_k-\nabla f(x_k)/L$,从下降引理、凸函数一阶不等式与平方距离恒等式推导 \(f(x_K)-f^*\le\frac{L\|x_0-x^*\|^2}{2K},\quad K\ge1.\)

B(10 分)PL 与非强凸: 在 $L$-Smooth、$\mu$-PL($0<\mu\le L$)下,推导 GD 的函数值几何收敛。再用 $F(u,v,w)=\tfrac12(u^2+4v^2)$ 说明 PL 不意味着强凸或最优点唯一。

C(10 分)Wolfe 与反例: 对严格下降方向 $p$、正步长 $\alpha$ 和 $0<c_1<c_2<1$,证明弱 Wolfe 曲率条件推出 $s^Ty>0$($s=\alpha p,y=\nabla f(x+\alpha p)-\nabla f(x)$)。再举一个 Armijo 成立但 $s^Ty<0$ 的具体例子,说明只有充分下降为何不够。

D(8 分)KKT 回顾: 求解 $\min_{x\le1}\tfrac12(x-2)^2$,给出最优点、活跃约束、乘子、驻点与互补松弛。再举一个约束活跃却乘子为零的凸问题。解释为何约束最优点不必满足 $\nabla f=0$。

提示:A 将函数值差写成相邻平方距离之差后求和;B 用 PL 控制梯度平方;C 由新旧方向导数之差推出正曲率,可参照双井函数;D 在边界点用乘子平衡非零梯度。

十一、下一讲与学习安排

第 22 课|2026 年 11 月 10 日|第 4 周第 1 天:投影与近端算子的最优性条件。

从下周起,将无约束梯度迭代推广到带集合约束与非光滑正则项的场景,推导 $\operatorname{prox}_{\eta h}$、投影算子与法锥关系,并以投影梯度和软阈值为起点。第 28 课(2026-11-16)安排四周阶段测验。

自测总分 $15+20+25+40=100$:80 分及以上正常继续;60—79 分补充针对性例题;低于 60 分优先复习下降引理、PL 假设、Wolfe 曲率与 KKT 互补松弛。回答后逐题评分反馈,但不因成绩改变课程日期与编号。

本课一句话: 任何收敛速度都要和它的「函数假设—算法参数—误差指标」一起记忆;真正可靠的是写出完整不等式链,而不是只背 $O(1/K)$ 或“线性收敛”。