数学优化理论 · 第29课

坐标下降:循环、随机与 Gauss–Southwell 规则

2026年11月17日|第5周第1天|讲授约18分钟(自测另计)

前四周主要研究一次同时更新全部变量的 GD、FISTA 与算子分裂。本周进入坐标下降、ADMM 与 PDHG:变量有很多,但每次只改一个坐标,为什么仍可能高效收敛? 重点不能只看“每次便宜”,还要看下降量、选坐标的额外成本,以及收敛保证究竟衡量多少次坐标更新。

一、模型、假设与三个坐标选择策略

先考虑无约束的可微函数 f:ℝⁿ→ℝ,存在全局最优点 x*。记 e_i 为第 i 个标准基向量,g_i(x)=∂_i f(x)。

坐标方向 Smooth: 对每个 i,有 L_i>0,使任意 x、t 满足

\[|\partial_i f(x+t e_i)-\partial_i f(x)|\le L_i|t|.\]

这只要求沿单个坐标的偏导 Lipschitz;与整个梯度满足全局 L-Smooth 是不同的假设。

一次坐标更新: \(x^{k+1}=x^k-\frac{\partial_{i_k}f(x^k)}{L_{i_k}}e_{i_k}.\)

三种选择:

  • Cyclic(循环):按照 1,2,…,n,1,2,… 的顺序轮流更新。
  • Randomized(随机):每步抽取坐标,例如均匀抽样或按照 L_i 的重要性抽样。
  • Gauss–Southwell(GS):选择 g_i 最大的坐标;GS-Lipschitz(GS-L) 选择 g_i²/L_i 最大的坐标。

两者不能混为一谈。GS-L 最大化的是下面要证明的可保证的一步下降量,不是必然最大化真实函数下降量。

二、核心引理:单坐标二次上界

定义 φ(t)=f(x+t e_i)。坐标光滑假设意味着

\[|\phi'(t)-\phi'(0)|\le L_i|t|.\]

由积分表示(t<0 时也可沿反向区间证明):

\[\begin{aligned} \phi(t)-\phi(0) &=\int_0^t\phi'(s)\,ds\\ &\le t\phi'(0)+\frac{L_i}{2}t^2. \end{aligned}\]

所以

\[\boxed{f(x+t e_i)\le f(x)+t g_i(x)+\frac{L_i}{2}t^2.}\tag{1}\]

二次上界对 t 的最小点为 t*=−g_i/L_i。代回:

\[\boxed{f(x)-f(x+t^*e_i)\ge\frac{g_i(x)^2}{2L_i}.}\tag{2}\]

注意:式(1)、(2)不需要凸性。 但要得到全局函数值收敛,还需要额外的结构假设。

由式(2)直接获得规则:

\[\boxed{i_{\mathrm{GS-L}}\in\arg\max_i\frac{g_i(x)^2}{L_i}.}\tag{3}\]

如果 L_i 均相等,GS 与 GS-L 才具有相同的最大化指标。

为什么只比较 |g_i| 可能不合适?

如果梯度分量为 (3,2.8),坐标常数为 (9,1),则:

  • 更新坐标 1 保证的下降量:9/(2×9)=0.5。
  • 更新坐标 2 保证的下降量:7.84/(2×1)=3.92。

所以普通 GS 选择 1,但 GS-L 选择 2。数值 3.92 是下降下界,不等于所有目标函数的真实下降量。

三、随机坐标下降的条件期望

令 S=∑_{i=1}^n L_i,按

\[\boxed{p_i=\Pr(i_k=i)=\frac{L_i}{S}}\tag{4}\]

独立抽取坐标。由式(2),给定 x^k 后:

\[\begin{aligned} \mathbb E[f(x^{k+1})\mid x^k] &\le f(x^k)-\frac12\sum_i p_i\frac{g_i(x^k)^2}{L_i}\\ &=f(x^k)-\frac{\|\nabla f(x^k)\|^2}{2S}. \end{aligned}\]

因此

\[\boxed{\mathbb E[f(x^{k+1})\mid x^k]\le f(x^k)-\frac{\|\nabla f(x^k)\|^2}{2S}.}\tag{5}\]

如果改成均匀抽样 p_i=1/n,则

\[\mathbb E[f(x^{k+1})\mid x^k] \le f(x^k)-\frac1{2n}\sum_i\frac{g_i(x^k)^2}{L_i} \le f(x^k)-\frac{\|\nabla f(x^k)\|^2}{2nL_{\max}}.\]

这是保守但简单的界。重要性抽样并不在每个问题上都比均匀抽样更快,因为真实更新成本、L_i 分布与维护梯度的代价可能不同。

四、严格收敛定理:强凸条件下的随机线性收敛

进一步假设 f 是 μ-强凸(μ>0)的可微函数。强凸一阶下界:

\[f(x^*)\ge f(x)+\nabla f(x)^T(x^*-x)+\frac\mu2\|x^*-x\|^2.\]

对最后两项配方,并利用平方项非负:

\[\boxed{\|\nabla f(x)\|^2\ge2\mu[f(x)-f^*].}\tag{6}\]

这也是此前学习的 PL 梯度主导不等式。

将式(6)代入式(5):

\[\begin{aligned} \mathbb E[f(x^{k+1})-f^*\mid x^k] &\le (1-\mu/S)[f(x^k)-f^*]. \end{aligned}\]

令 Δ_k=f(x^k)-f*,使用全期望公式(tower property):

\[\mathbb E\Delta_{k+1}\le(1-\mu/S)\mathbb E\Delta_k.\]

归纳得到:

\[\boxed{\mathbb E[f(x^K)-f^*]\le\left(1-\frac\mu S\right)^K[f(x^0)-f^*].}\tag{7}\]

这里的 K 是单坐标更新次数,不是完整扫描全体 n 个坐标的轮数。期望取自各轮随机坐标选择。

这项证明实际上只用到式(6)的 PL 关系;因此如果函数虽非强凸但满足同一全局 PL 不等式,式(7)仍然成立。线性收敛结论不能推广到任意非凸函数。

五、GS-L 为什么也有单步线性收敛保证?

使用式(2)、(3):

\[f(x)-f(x^+)\ge\frac12\max_i\frac{g_i(x)^2}{L_i}.\]

令 S=∑L_i。由于最大值不小于加权平均:

\[\max_i\frac{g_i^2}{L_i} \ge\sum_i\frac{L_i}{S}\frac{g_i^2}{L_i} =\frac{\|g\|^2}{S}.\]

所以:

\[f(x^+)\le f(x)-\frac{\|\nabla f(x)\|^2}{2S}.\]

再用强凸推出的 PL 关系:

\[\boxed{ f(x^{k+1})-f^* \le(1-\mu/S)[f(x^k)-f^*]. }\tag{8}\]

注意 GS-L 是确定性的一步保证,随机方法是条件期望保证。相同上界不意味着两者真实耗时相同:GS-L 可能需要检查全部梯度分量,随机选择往往可以只计算一个局部坐标。

循环选坐标在额外条件下同样可以证明收敛,但不能把式(8)直接逐坐标套用到循环规则:这一轮指定的坐标梯度可能恰好为零,虽然其他坐标的梯度不为零。

六、耦合二次函数的完整迭代

考虑:

\[\boxed{f(x_1,x_2)=2x_1^2+x_1x_2+x_2^2-5x_1-3x_2.}\]

梯度:

\[\nabla f= \begin{bmatrix} 4x_1+x_2-5\\ x_1+2x_2-3 \end{bmatrix}.\]

Hessian:

\[H=\begin{bmatrix}4&1\\1&2\end{bmatrix}\]

的特征值为 3±√2,均为正,因此函数强凸;可取 L₁=4、L₂=2,μ=3−√2。解 Hx=(5,3) 得 x=(1,1),f=−4。

从 x⁰=(0,0) 出发,循环顺序为坐标 1 再坐标 2。

第一步:g₁=−5,于是 x₁=0−(−5)/4=1.25。此时 f(1.25,0)=−3.125。

第二步:在更新后的点,g₂=1.25−3=−1.75;x₂=0−(−1.75)/2=0.875。此时

\[\boxed{f(1.25,0.875)=-3.890625.}\]

第三步:新点 g₁=4(1.25)+0.875−5=0.875,再更新 x₁=1.25−0.875/4=1.03125,目标值进一步减少 0.875²/(2×4)=0.095703125。

更新次数 选择坐标 更新后 x₁ 更新后 x₂ f(x)
0 — 0 0 0
1 1 1.25 0 −3.125
2 2 1.25 0.875 −3.890625
3 1 1.03125 0.875 −3.986328125
最优 — 1 1 −4

在这个二次函数上,式(2)每次取等号,因为坐标二次模型与真实坐标截面恰好相同;一般非二次函数只有保证下降量的下界。

七、失败反例:坐标极小未必全局最优

考虑一个强凸但非光滑、非可分的目标:

\[F(x,y)=|x-y|+\frac{x^2+y^2}{2}+\frac{x+y}{2}.\]

在 (0,0) 固定 y=0,单独优化 x:

\[F(x,0)=|x|+\frac{x^2}2+\frac x2.\]

此一维函数在 x=0 最小。固定 x=0、单独优化 y 也一样。因此 (0,0) 是逐坐标精确最小化的不动点。

但沿着方向 x=y=−t:

\[F(-t,-t)=t^2-t.\]

取 t=1/2 得:

\[F(-1/2,-1/2)=-1/4< F(0,0)=0.\]
所以坐标极小点并非全局最优。原因不是缺少强凸性,而是不可分的非光滑项 x−y 使两条坐标轴上的局部最优条件无法推出整体次梯度包含零。上一节关于光滑 f 的梯度坐标条件不能直接用于此例。

另一个失败是非法步长:即使 f(x)=x²/2,若坐标步长取 3(而 L=1),则 x_{k+1}=−2x_k,迭代发散。

八、与 KKT 和坐标 Prox 的联系

对于可分正则化

\[\boxed{F(x)=f(x)+\sum_i h_i(x_i),}\]

可以对坐标 i 使用近端更新:

\[\boxed{ x_i^+=\operatorname{prox}_{h_i/L_i} \left(x_i-\frac{\partial_i f(x)}{L_i}\right), }\]

其他坐标保持不变。对于 L1 正则化,逐坐标 Prox 是软阈值。这里非光滑部分可分是关键结构。

若还有耦合约束,例如 x₁+x₂=1,固定另一个坐标而单独更新一个坐标可能根本无法移动,此时需要块坐标更新、投影或后续学习的 ADMM/PDHG 等方法。

再回顾 KKT。考虑约束 x≥0,统一写成 −x≤0:

  • 对 min (x+1)²/2,最优点 x=0,约束活跃,驻点 1−λ=0,故 λ=1。
  • 对 min x²/2,最优点 x=0,约束同样活跃,但驻点 0−λ=0,故 λ=0。

两者均满足 λ≥0、−x≤0、λ(−x)=0。所以活跃约束不必对应严格正乘子。

九、数学关系图与算法比较

flowchart TD
    A["坐标方向 Lipschitz:L_i"] --> B["单坐标二次上界"]
    B --> C["保证下降 g_i²/(2L_i)"]
    C --> D["循环选择"]
    C --> E["随机选择 p_i=L_i/ΣL_i"]
    C --> F["GS-L 选择最大 g_i²/L_i"]
    E --> G["条件期望下降"]
    F --> H["确定性下降"]
    G --> I["强凸 / PL ⇒ 期望线性收敛"]
    H --> J["强凸 / PL ⇒ 确定性线性收敛"]
    B --> K["可分 h_i ⇒ 坐标 Prox"]
    K --> L["耦合约束 ⇒ 需块方法或分裂"]
规则 选坐标方式 保证的性质 代价提醒    
循环 固定顺序 每个合法坐标步不增加目标 单步未必有全梯度收缩界    
随机 例如 p_i=L_i/S 条件期望下降与线性收敛界 单步便宜,但路径随机    
GS 最大 g_i   在 L_i 相同时对应最大保证下降 常需搜索梯度分量
GS-L 最大 g_i²/L_i 最大化本课的单步下降保证 选择成本可能较高    

十、下一讲

第30课(2026-11-18):块坐标下降与复合正则化的坐标近端更新。将从软阈值、块 Lipschitz 常数与可分结构出发,研究为什么某些非光滑正则可以逐块优化,而耦合约束和非可分正则需要更谨慎的处理。

阅读延伸:Y. Nesterov, Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems, SIAM Journal on Optimization, 2012(https://doi.org/10.1137/100802001);J. Nutini 等, Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection, 2015(https://arxiv.org/abs/1506.00552)。

自测说明:第一次发课不附答案。前三题客观评分,最后一题按证明要点评分。总分 80+ 正常推进、60–79 补充针对性例子、低于60优先复习薄弱知识;不改变日期课号。标准答案仅存于独立 JSON。

十一、今日四级自测(100分;首次不公布答案)

请先独立作答,不要打开独立测验 JSON,其中含有标准答案。

Lv1|坐标光滑性与关键概念|15分|预计2分钟

设可微函数 f 的第 i 个坐标满足沿坐标方向的梯度 Lipschitz 条件,常数 L_i>0。下面哪一项必然正确?

  • A. 只要每个坐标分别光滑,f 就必定是强凸函数。
  • B. 对任何实数 t,均有 f(x+t e_i)≤f(x)+t∂_i f(x)+(L_i/2)t²。
  • C. Gauss–Southwell–Lipschitz 规则总是选择 ∂_i f(x) 最大的坐标,完全不看 L_i。
  • D. 对任意非光滑且非可分的凸函数,坐标逐一精确最小化后的坐标最优点一定是全局最优点。

提示:只沿第 i 个方向应用一维下降引理;区分坐标光滑、强凸及坐标选择规则。

Lv2|耦合二次函数的两次循环更新|20分|预计4分钟

令 f(x₁,x₂)=2x₁²+2x₁x₂+3x₂²−5x₁−7x₂,坐标 Lipschitz 常数 L₁=4、L₂=6。从 x⁰=(0,0) 出发,先更新坐标 1,再更新坐标 2,每次采用 x_i←x_i−∂_i f(x)/L_i(更新后立即用于下一个坐标)。求两次更新后 f(x²) 的数值,保留四位小数。

提示:先求两项偏导;先更新 x₁,再以最新的 x₁ 求第二个坐标的偏导数。

Lv3|Gauss–Southwell 与归一化选择规则比较|25分|预计5分钟

在某个点,梯度为 (∂₁f,∂₂f)=(4,3),坐标光滑常数 (L₁,L₂)=(16,2)。采用单坐标步长 1/L_i 时,第 i 坐标可保证的函数下降量至少为 (∂_i f)²/(2L_i)。普通 GS 选择 ∂_i f 最大的坐标,GS-Lipschitz (GS-L) 选择 (∂_i f)²/L_i 最大的坐标。以下哪项正确?
  • A. GS 与 GS-L 都选择坐标 1,因为第一个梯度分量更大。
  • B. GS 选择坐标 2,GS-L 选择坐标 1;两者保证下降量相同。
  • C. GS 选择坐标 1,GS-L 选择坐标 2;对应的理论保证下降量分别为 0.5 和 2.25。
  • D. GS-L 选择坐标 2,但理论保证下降量只能是 3,不能用平方梯度计算。

提示:先比较两个梯度分量绝对值,再分别计算 g_i²/(2L_i)。

Lv4|坐标下降收敛证明、非可分反例与 KKT|40分|预计14分钟

完成四部分,并写清所有假设。

A(12分):若 f 可微、每个坐标有正的 L_i-Lipschitz 偏导,证明沿坐标 i 使用 t=−∂_i f(x)/L_i 后,f(x)−f(x+t e_i)≥(∂_i f(x))²/(2L_i)。说明 GS-L 选择为何最大化这个保证下降量。

B(12分):进一步假设 f 为 μ-强凸函数(μ>0),最优点存在。令 S=∑_i L_i。采用独立随机坐标选择 P(i_k=i)=L_i/S,证明 E[f(x^{k+1})−f* x^k]≤(1−μ/S)(f(x^k)−f),再证明 E[f(x^K)−f]≤(1−μ/S)^K(f(x⁰)−f*)。指出期望是针对什么随机性。
C(10分):考虑 F(x,y)=2 x−y +(x²+y²)/2+3(x+y)/4。证明 (0,0) 固定另一个坐标逐一精确最小化时都不改变,但它不是全局最优点(给出一个更好的点)。解释为何这不与 A/B 矛盾。

D(6分):分别对 min_{x≤2}(x−4)²/2 和 min_{x≥1}(x−1)²/2 求解最优点、活跃约束、非负 KKT 乘子,并验证驻点和互补松弛;解释活跃约束为何不一定对应严格正乘子。

提示:A 对一维二次上界配方;B 对 i 的抽样取条件期望,并用强凸推出 PL 不等式;C 用单坐标次微分判别并尝试沿 x=y<0 移动;D 把约束统一写成 g(x)≤0。