数学优化理论 · 第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。