第 17 课|强凸加速、条件数与重启:动量为何会振荡?
2026 年 11 月 5 日|第 3 周·第 3 天|讲授约 18 分钟(自测另计)
上节课我们证明:凸且 (L)-Smooth 的无约束问题,Nesterov 三序列 AGD 可使最后一步函数值误差达到 (O(1/k^2))。今天更进一步:当目标还具有 (\mu)-强凸性时,能否像普通梯度下降一样得到几何收敛,但摆脱缓慢的条件数依赖?
今天的逻辑是:明确假设 → 构造强凸加速迭代 → 严格证明势函数收缩 → 计算二维例子 → 解释目标值振荡 → 证明一种真正有保证的重启办法。
一、问题、假设与条件数
研究无约束最小化 (\min_{x\in\mathbb R^n} f(x))。假设 (f) 可微、(\mu)-强凸、(L)-Smooth,(0<\mu\le L),即对所有 (x,y): [ f(y)\ge f(x)+\nabla f(x)^T(y-x)+\frac\mu2|y-x|^2, ] [ f(y)\le f(x)+\nabla f(x)^T(y-x)+\frac L2|y-x|^2. ] 在这些假设下存在唯一最优点 (x^),满足 (\nabla f(x^)=0)。记初始误差 (\Delta_0=f(x_0)-f^*),条件数 [ \boxed{\kappa=L/\mu\ge1}. ]
当 (\kappa) 很大,曲率最大的方向和最小的方向相差悬殊;为了避免在高曲率方向震荡,GD 需要较小步长,却因此在低曲率方向移动缓慢。以对角二次函数 (f(u,v)=\tfrac12(u^2+\kappa v^2)) 为例,步长 (1/L=1/\kappa) 的 GD 满足 (u_{k+1}=(1-1/\kappa)u_k)、(v_{k+1}=0),其中 (u) 是最慢方向。
| 算法与设定 | 函数值误差的可证明上界 | 条件数相关迭代复杂度 |
|---|---|---|
| GD,步长 (1/L) | (\Delta_k\le(1-1/\kappa)^k\Delta_0) | (O(\kappa\log(\Delta_0/\varepsilon))) |
| 今日强凸 AGD | (\Delta_k\le 2(1-1/\sqrt\kappa)^k\Delta_0) | (O(\sqrt\kappa\log(\Delta_0/\varepsilon))) |
| 上节课凸 AGD,无需 (\mu) | (\Delta_k\le2L|x_0-x^*|^2/(k+1)^2) | 一般凸:(O(1/\sqrt\varepsilon))(常数略) |
这些都是最坏情况迭代界,不是声称在每个具体问题、每个中间迭代上 AGD 都比 GD 更快。对一般凸函数还不能直接使用强凸几何收敛率。
二、强凸 Nesterov 三序列方法
设
[
\boxed{\rho=\sqrt{\mu/L}=1/\sqrt\kappa\in(0,1]}.
]
初始化 (x_0=z_0)。第 (k) 轮定义
[
\boxed{
\begin{aligned}
y_k&=\frac{x_k+\rho z_k}{1+\rho} &&\text{外推 / 耦合点},
g_k&=\nabla f(y_k) &&\text{只计算一次梯度},
x_{k+1}&=y_k-\frac1L g_k &&\text{梯度下降步},
z_{k+1}&=(1-\rho)z_k+\rho y_k-\frac{\rho}{\mu}g_k &&\text{辅助点更新}.
\end{aligned}}
\tag{1}
]
这是一种针对已知 (\mu,L) 的强凸 Nesterov / 线性耦合实现;并非随意在 GD 上叠加一个常数动量。若 (\mu,L) 只是合法的保守界,算法依然可用,但收敛界可能偏松。
今天的收敛定理:定义 [ \boxed{V_k=f(x_k)-f^+\frac\mu2|z_k-x^|^2.} \tag{2} ] 那么 [ \boxed{V_{k+1}\le(1-\rho)V_k.} \tag{3} ] 注意 (V_k) 是“函数值误差 + 辅助变量距离”,不是只有函数值的 (\Delta_k)。这正是加速法可以在个别步目标值上升、却仍保持整体收敛保证的原因。
三、严格推导势函数的几何收缩
为了让不等式容易检查,在某一步简写 (x=x_k,z=z_k,y=y_k,g=g_k),再令 [ \bar z=(1-\rho)z+\rho y,\quad x^+=x_{k+1},\quad z^+=z_{k+1}. ]
第一步:两次应用强凸性。 在 (y) 处分别比较 (x) 与 (x^):
[
f(x)\ge f(y)+g^T(x-y)+\frac\mu2|x-y|^2,
]
[
f(x^)\ge f(y)+g^T(x^-y)+\frac\mu2|x^-y|^2.
]
分别乘 (1-\rho,\rho) 再相加,整理得
[
\begin{aligned}
f(y)-f^-(1-\rho)[f(x)-f^]
&\le g^T[y-(1-\rho)x-\rho x^]
&\quad-\frac\mu2\left[(1-\rho)|x-y|^2+\rho|x^-y|^2\right].
\end{aligned}
\tag{4}
]
第二步:下降引理。 因 (x^+=y-g/L), [ \boxed{f(x^+)\le f(y)-\frac1{2L}|g|^2.} \tag{5} ]
第三步:辅助变量的平方距离。 由 (z^+=\bar z-(\rho/\mu)g),结合凸组合恒等式
[
|\bar z-x^|^2
=(1-\rho)|z-x^|^2+\rho|y-x^|^2
-\rho(1-\rho)|z-y|^2,
]
得到
[
\begin{aligned}
\frac\mu2\left[|z^+-x^|^2-(1-\rho)|z-x^|^2\right]
&=\frac{\mu\rho}{2}|y-x^|^2
&\quad-\frac{\mu\rho(1-\rho)}2|z-y|^2
&\quad-\rho g^T(\bar z-x^*)+\frac{\rho^2}{2\mu}|g|^2.
\end{aligned}
\tag{6}
]
第四步:合并并检查每一项。 把式 (4)、(5)、(6) 相加,计算 (V_{k+1}-(1-\rho)V_k)。其中:
[
\boxed{\frac{\rho^2}{\mu}=\frac1L}
]
让梯度平方项严格抵消;而
[
\begin{aligned}
&y-(1-\rho)x-\rho x^-\rho(\bar z-x^)
&=(1-\rho)\big[(1+\rho)y-x-\rho z\big]=0,
\end{aligned}
]
因为外推定义给出 ((1+\rho)y=x+\rho z),所以梯度内积项也抵消。
于是只留下非正余项: [ \boxed{ V_{k+1}-(1-\rho)V_k \le-\frac{\mu(1-\rho)}2 \big(|x-y|^2+\rho|z-y|^2\big)\le0. } \tag{7} ] 这完整证明了式 (3)。两个精心设计的恒等式,而不是“动量直觉”,保证了加速。
四、从势函数到复杂度:为什么是平方根条件数?
由递推, [ V_k\le(1-\rho)^kV_0. ] 由于 (z_0=x_0),并且强凸性与 (\nabla f(x^)=0) 给出 [ f(x_0)-f^\ge\frac\mu2|x_0-x^|^2, ] 因此 (V_0\le2\Delta_0)。又因为 (f(x_k)-f^\le V_k),所以 [ \boxed{ f(x_k)-f^*\le2(1-\sqrt{\mu/L})^k\Delta_0. } \tag{8} ]
利用 ((1-\rho)^k\le e^{-\rho k}),若 (\Delta_0>0),为了使函数值误差不超过 (\varepsilon>0),充分条件是 [ k\ge \frac1\rho\log\frac{2\Delta_0}{\varepsilon} =\sqrt{\frac L\mu}\log\frac{2\Delta_0}{\varepsilon}, ] 在 (\mu=L) 时可直接从 (\rho=1) 看出第一步到达最优。由此得到 [ \boxed{\text{AGD: }O(\sqrt\kappa\log(1/\varepsilon)),\qquad \text{GD: }O(\kappa\log(1/\varepsilon))} ] (这里省略初始误差常数)。例如 (\kappa=100) 时,GD 的标准收缩因子上界为 (0.99),今日 AGD 势函数的收缩因子是 (0.9);两者的收缩对象和前置常数不同,不能仅看单步系数就声称精确的实际加速倍数。
五、数值迭代:同一个二维问题比较 GD 与 AGD
考虑 [ f(u,v)=\frac12(u^2+9v^2),\qquad \nabla f(u,v)=(u,9v),\qquad \nabla^2 f=\operatorname{diag}(1,9). ] 因此 (\mu=1,L=9,\rho=1/3,\kappa=9);最优点 ((0,0)),最优值 0。初始化 (x_0=z_0=(3,1))。
第 1 步。 外推点 (y_0=(3,1)),梯度 (g_0=(3,9)),所以 [ x_1=(3,1)-\tfrac19(3,9)=(8/3,0), ] [ z_1=(3,1)-\tfrac13(3,9)=(2,-2). ]
第 2 步。 注意梯度应在 (y_1) 计算,而非 (x_1): [ y_1=\frac{(8/3,0)+(1/3)(2,-2)}{4/3} =(5/2,-1/2). ] 于是 (g_1=(5/2,-9/2)), [ x_2=y_1-\tfrac19g_1=(20/9,0). ]
| (k) | 强凸 AGD 的 (x_k) | AGD 目标值 | GD 同轮目标值(步长 (1/9)) |
|---|---|---|---|
| 0 | ((3,1)) | (9) | (9) |
| 1 | ((8/3,0)) | (32/9\approx3.5556) | (32/9\approx3.5556) |
| 2 | ((20/9,0)) | (200/81\approx2.4691) | (2048/729\approx2.8093) |
此例第二轮 AGD 优于 GD;但两轮实验只能说明这个实例,不能代替第四节的最坏情况收敛证明。
六、为什么 AGD 可能出现目标值振荡?
一个容易犯的错误是:从 (V_{k+1}\le(1-\rho)V_k) 推出 (f(x_{k+1})\le f(x_k))。这两个不等式不是一回事。
给出一个完全满足本课假设的反例:(f(t)=t^2),取合法但不紧的界 (\mu=1,L=4)(实际 Hessian 恒为 2),因此 (\rho=1/2)。令 (x_0=z_0=1),按式 (1) 迭代,可得到
| 迭代 | (x_k) | 函数值 (f(x_k)) |
|---|---|---|
| 0 | (1) | (1) |
| 1 | (1/2) | (1/4) |
| 2 | (1/6) | (1/36) |
| 3 | (1/36) | (1/1296) |
| 4 | (-1/108) | (1/11664\approx0.00008573) |
| 5 | (-7/648) | (49/419904\approx0.00011669) |
从第 4 到第 5 步,目标值确实上升,但势函数仍有式 (3) 的几何收缩保证,因为辅助变量距离项也在变化。目标值非单调不等于算法发散,单调性与全局收敛率也不是同一性质。
另一个失败点是参数不合法:如果 (\mu) 或 (L) 不是有效的全局曲率界,本课证明不成立。随机挑选动量系数、使用大于稳定范围的步长,也不能直接继承这些收敛结论。
七、重启(Restart):一个可证明版本与一个启发式版本
加速方法可能沿外推方向“冲过头”。实践中常使用重启:运行若干步后保留当前输出,重置历史辅助状态,从该点重新开始。
需要严格区分两类策略。
有理论保证的固定周期重启。 用上一课仅要求凸与 Smooth 的 AGD,从一个起点 (s) 运行 (T\ge1) 步,满足 [ f(y_T)-f^\le\frac{2L|s-x^|^2}{(T+1)^2}. ] 由强凸性: [ |s-x^|^2\le\frac2\mu(f(s)-f^). ] 合并得到 [ \boxed{ f(y_T)-f^\le\frac{4\kappa}{(T+1)^2}(f(s)-f^). } \tag{9} ] 只要选择 [ \boxed{T+1\ge\sqrt{8\kappa}} ] 便保证每一完整重启周期结束时误差至多减半。重复 (m) 轮就有 [ \Delta_m\le2^{-m}\Delta_0,\qquad \text{总梯度计算次数 }=O(\sqrt\kappa\log(\Delta_0/\varepsilon)). ] 这个证明需要已知合法的 (\mu,L)、精确梯度、每轮正确重置并运行足够步数;不保证周期中每一步函数值都下降。
经验性自适应重启。 例如观察函数值上升就重启、或者利用相邻位移与梯度的内积判断动量方向不合适。这类规则在实际中可能有效,但如果没有额外分析,不能把固定周期的理论减半界套用到任意自适应触发规则。今天不宣称这类经验规则自动享有 (O(\sqrt\kappa\log(1/\varepsilon))) 的保证。
八、与前两周 KKT 的联系
今天全部证明针对无约束、可微、强凸且 Smooth 的问题。带约束时最优点通常不满足 (\nabla f(x^*)=0),而是满足法锥形式或 KKT 条件;不能不加修改就套用式 (1) 的无约束收敛证明。后续投影梯度、Prox 和原始—对偶方法会相应改变更新式与势函数。
特别回顾互补松弛:活跃约束 (g_i(x^)=0) 并不要求 (\lambda_i^>0);只有严格不活跃 (g_i(x^)<0) 才强制 (\lambda_i^=0)。算法收敛保证与 KKT 乘子的存在或唯一性,也必须分别证明。
九、关系图与本课结论
flowchart TD
A["μ-强凸 + L-Smooth + 无约束"] --> B["κ = L / μ"]
B --> C["GD: 1 - 1/κ"]
B --> D["强凸 AGD: ρ = 1/√κ"]
D --> E["势函数 V = 目标误差 + 辅助距离"]
E --> F["严格证明 V(k+1) ≤ (1-ρ)V(k)"]
F --> G["O(√κ log(1/ε)) 梯度次数"]
D --> H["输出目标值可能非单调"]
A --> I["凸 AGD + 固定周期重启"]
I --> J["T+1 ≥ √(8κ) 保证每周期误差减半"]
K["经验性自适应重启"] -. "没有自动的同款保证" .-> J
今天最重要的三个公式:(\rho=\sqrt{\mu/L})、(V_{k+1}\le(1-\rho)V_k)、以及 (T+1\ge\sqrt{8\kappa}) 对固定周期重启的减半保证。
十、四级自测(100 分)
首次课堂只显示题目和提示,不显示标准答案、正确选项与开放题评分细则。请先独立作答,不要提前打开独立答案 JSON。
Lv1|强凸加速的条件与保证|15 分|预计 2 分钟
设函数可微、μ-强凸且 L-Smooth(0<μ≤L),并且使用本课给出的参数正确的强凸三序列 AGD。下列哪项一定正确?
A. 由于函数强凸,任何正步长和任何动量系数都能保证全局收敛。
B. 算法的势函数具有几何收缩界,但输出函数值不一定每步单调下降。
C. 只要使用动量,任何非凸函数都能获得全局最优值的 O(1/k²) 保证。
D. 强凸 AGD 的收敛结论必然意味着原始约束问题的 KKT 乘子唯一。
提示:请区分势函数收缩、目标值逐步单调、以及无约束和约束问题的假设。
Lv2|强凸三序列 AGD 的两步计算|20 分|预计 4 分钟
考虑 (f(u,v)=\tfrac12(u^2+16v^2)),取 (\mu=1,\ L=16,\ \rho=\sqrt{\mu/L}=1/4),初值 (x_0=z_0=(4,1))。使用本课三序列算法:(y_k=(x_k+\rho z_k)/(1+\rho))、(g_k=\nabla f(y_k))、(x_{k+1}=y_k-g_k/L)、(z_{k+1}=(1-\rho)z_k+\rho y_k-(\rho/\mu)g_k)。求第二步结束后的函数值 (f(x_2)),保留三位小数。
提示:第一步需同时更新 x_1 和 z_1;第二步计算的梯度位置是 y_1,不是 x_1。
Lv3|条件数、固定周期重启与严格界|25 分|预计 5 分钟
设 (f) 为 (\mu)-强凸且 (L)-Smooth 的无约束函数,条件数 (\kappa=L/\mu=25)。已知上一课凸 AGD 从初值 (x) 运行 (T\ge1) 步的输出满足 (f(y_T)-f^\le 2L|x-x^|^2/(T+1)^2)。每次将 (y_T) 作为新初值、重置辅助状态。下面哪项一定有严格保证?
A. 每 10 步重启一次,一定让每轮末端函数值误差至少减半。
B. 每 14 步重启一次,在给定假设下,每轮末端函数值误差至多为前一轮的一半。
C. 只要满足强凸,AGD 每一步的目标值必然单调降低,所以重启无关紧要。
D. 上述重启减半保证对任意 L-Smooth 非凸问题同样成立。
| *提示:强凸给出 μ | x-x* | ²/2≤f(x)-f;将它代入上一课的 AGD 界,再核对 T。 |
Lv4|强凸加速势函数、复杂度和非单调反例|40 分|预计 12 分钟
对无约束问题 (\min_x f(x)),设 (f) 可微、(\mu)-强凸、(L)-Smooth,(0<\mu\le L),最优点为 (x^)。令 (\rho=\sqrt{\mu/L}),初值 (z_0=x_0),迭代: [ y_k=\frac{x_k+\rho z_k}{1+\rho},\quad g_k=\nabla f(y_k),\quad x_{k+1}=y_k-\frac1L g_k,\quad z_{k+1}=(1-\rho)z_k+\rho y_k-\frac{\rho}{\mu}g_k. ] A(16 分): 定义 (V_k=f(x_k)-f^+\frac{\mu}{2}|z_k-x^|^2)。同时对 (x_k,x^) 应用强凸一阶下界,对 (x_{k+1}) 使用下降引理,并展开 (z_{k+1}) 的平方距离,证明 (V_{k+1}\le(1-\rho)V_k)。明确写出两处抵消的恒等式。 B(8 分): 利用 (z_0=x_0) 和强凸性导出函数值误差上界,比较 GD 与强凸 AGD 在条件数 (\kappa=L/\mu) 下达到精度 (\varepsilon) 的迭代复杂度。 C(8 分): 如果只运行上一课的凸 AGD 并周期性重启,利用其 (O(1/T^2)) 界与强凸性,求一个显式的重启周期 (T),使每轮末端误差至多减半(答案可用 (\kappa) 表示)。 D(8 分): 对新函数 (f(t)=(t-1)^2),取合法但不紧的常数 (\mu=1,L=4)、初值 (x_0=z_0=2),按本题强凸 AGD 计算 (x_4,x_5),判断目标值是否每步单调,并解释这为何不违背 A 的势函数收缩。
提示:A:令 ̄z=(1-ρ)z_k+ρ y_k,使用平方范数的凸组合恒等式;利用 ρ²/μ=1/L 与 (1+ρ)y_k=x_k+ρ z_k。
十一、下一讲与评分规则
第 18 课|2026 年 11 月 6 日:线搜索、Backtracking 与未知 Smooth 常数下的步长选择。 将推导 Armijo 类充分下降条件及其适用前提,解释为何无需预先知道精确 (L) 也能选择可靠步长,并比较固定步长、线搜索和加速法的代价与收敛结论。
四题分值为 15 + 20 + 25 + 40 = 100。作答后逐题批改,80 分及以上正常继续;60–79 分补相关例题;低于 60 分优先复习强凸、Smooth、势函数与 KKT 基础。测评结果不改变按日期计算的课程编号。