第 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 基础。测评结果不改变按日期计算的课程编号。