数学优化理论 · 第30课:块坐标下降与复合正则的坐标 Prox

2026-11-18|第5周第2天|18分钟(自测另计)

上一课从单坐标二次上界出发,学习了循环、随机和 GS-L 规则。今天把每次更新一个标量推广成更新一组向量:怎样利用块结构处理 L1、组稀疏与盒约束?什么时候局部块最优能推出整个凸问题全局最优?

一、模型与假设

将变量分成 $m$ 个不相交的块 $x=(x_1,\dots,x_m)$,考虑

\[\boxed{\min_x F(x)=f(x)+H(x),\quad H(x)=\sum_{j=1}^m h_j(x_j).}\]

假设 $f$ 凸且可微,每个 $h_j$ 真、下半连续、凸;对于任意块 $j$、向量 $d$,存在 $L_j>0$ 满足

\[\|\nabla_j f(x+U_jd)-\nabla_j f(x)\|\le L_j\|d\|,\]

其中 $U_jd$ 表示仅在第 $j$ 块添加 $d$。允许 $f$ 跨块耦合,但 $H$ 在本课理论中必须按块可分。之后谈收敛时会额外加入解存在、水平集紧等条件。

对象 定义 作用
$x_j$ 第 $j$ 个标量或向量块 单轮更新单位
$L_j$ 块方向 Smooth 常数 决定局部二次上界
$h_j$ 块正则项或块约束指标函数 利用 Prox 直接处理
$U_j$ 块嵌入算子 其他块保持不变

二、块下降引理:严谨不等式

设 $g_j=\nabla_j f(x)$。沿块方向积分并用 Lipschitz 条件:

\[\begin{aligned} f(x+U_jd)-f(x) &=\int_0^1\langle\nabla_j f(x+tU_jd),d\rangle dt\\ &\le \langle g_j,d\rangle+\int_0^1 tL_j\|d\|^2dt\\ &=\langle g_j,d\rangle+\tfrac{L_j}{2}\|d\|^2. \end{aligned}\]

即

\[\boxed{f(x+U_jd)\le f(x)+\langle g_j,d\rangle+\frac{L_j}{2}\|d\|^2.}\tag{1}\]

注意这个引理仅控制一个块方向,不需要整个 Hessian 的谱范数上界。

三、块近端更新与充分下降

固定其他块,构造

\[q_j(u)=h_j(u)+\langle g_j,u-x_j\rangle+\frac{L_j}{2}\|u-x_j\|^2.\]

记 $p=\arg\min_u q_j(u)$,则

\[\boxed{ p=\operatorname{prox}_{h_j/L_j}\left(x_j-\frac{g_j}{L_j}\right),\quad x^+=x+U_j(p-x_j). }\tag{2}\]

该块子问题的一阶最优性条件为

\[\boxed{0\in g_j+L_j(p-x_j)+\partial h_j(p).}\tag{3}\]

现在证明下降保证。$q_j$ 是 $L_j$-强凸,且 $p$ 为其最优点,因此

\[q_j(p)+\frac{L_j}{2}\|p-x_j\|^2\le q_j(x_j)=h_j(x_j).\]

结合块下降引理:

\[F(x^+)-F(x)\le q_j(p)-h_j(x_j).\]

于是

\[\boxed{F(x)-F(x^+)\ge\frac{L_j}{2}\|p-x_j\|^2.}\tag{4}\]

定义块近端梯度映射 $G_j(x)=L_j(x_j-p)$,则

\[\boxed{F(x)-F(x^+)\ge\frac{\|G_j(x)\|^2}{2L_j}.}\tag{5}\]

这个结论是确定性的单次下降。它不自动赋予任意块选择规则全局线性收敛速率。

四、常见块 Prox:L1、组稀疏与指标函数

当 $h_j(u)=\lambda u $,Prox 是软阈值:
\[\operatorname{prox}_{h_j/L_j}(v)=\operatorname{sign}(v)(|v|-\lambda/L_j)_+.\]

当一个块是向量、$h_j(u)=\lambda|u|_2$,若 $u\ne0$,次梯度最优性给出

\[0=\lambda u/\|u\|_2+L_j(u-v).\]

因此 $u$ 与 $v$ 同方向。结合零点次微分条件,得到组软阈值:

\[\boxed{ \operatorname{prox}_{(\lambda/L_j)\|\cdot\|_2}(v) =\left(1-\frac{\lambda}{L_j\|v\|_2}\right)_+v, }\tag{6}\]

约定 $v=0$ 时输出零。与逐元素 L1 不同,组软阈值会根据整个块的二范数决定是否一起置零。

若 $h_j=\delta_{C_j}$,则 $\operatorname{prox}{h_j/L_j}=\Pi{C_j}$。只有可行域是笛卡尔积 $C=C_1\times\cdots\times C_m$ 时,约束指标函数才可按块分解。

五、循环块坐标下降的收敛条件

令块按 $1,2,\ldots,m$ 循环更新。为建立明确收敛定理,额外假设各 $h_j$ 在全空间有限且连续、初始水平集紧、$F$ 存在最优点且每块精确执行式 (2)。

由充分下降式:

\[\sum_{k=0}^{K-1}\frac{L_{j_k}}2\|x^{k+1}-x^k\|^2 \le F(x^0)-F(x^K)\le F(x^0)-F^*.\]

因为 $L_{\min}=\min_j L_j>0$:

\[\boxed{\sum_{k=0}^\infty\|x^{k+1}-x^k\|^2<\infty,\quad \|x^{k+1}-x^k\|\to0.}\tag{7}\]

紧水平集保证聚点存在。沿每轮起点的一个收敛子列,由于每轮只有有限个更新且每一步移动趋零,该轮所有中间点也趋于同一个聚点 $\bar x$。利用 $\nabla_j f$ 与凸 Prox 的连续性,把每个块的更新式取极限:

\[\bar x_j=\operatorname{prox}_{h_j/L_j} \left(\bar x_j-\nabla_j f(\bar x)/L_j\right).\]

于是

\[0\in\nabla_j f(\bar x)+\partial h_j(\bar x_j),\qquad j=1,\ldots,m.\]

由 $H$ 的块可分性,可将这些条件组合为 $0\in\nabla f(\bar x)+\partial H(\bar x)=\partial F(\bar x)$。由于 $F$ 凸,$\bar x$ 是全局最优点。再利用 $F$ 连续且函数值单调下降,得到

\[\boxed{F(x^k)\to F^*.}\tag{8}\]

这是目标值收敛和聚点最优保证;不能由此直接断言普适的 $O(1/k)$ 或线性速率。这些还需要更强的误差界、强凸或相应的块选择分析。

对纯光滑情形 $h_j=0$,回顾上一课:若以 $p_j=L_j/S$ 独立随机抽块,$S=\sum_jL_j$,目标满足 $\mu$-PL,则

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

由全期望递推得到期望几何收敛。这是光滑目标与指定抽样的结论,不应未经额外证明直接套用到一般非光滑复合问题。

六、完整数值迭代:耦合光滑项 + 可分 L1

考虑

\[\boxed{ F(x,y)=\tfrac12(x-3)^2+\tfrac12(y+1)^2 +\tfrac12(x+y-1)^2+|x|+|y|. }\]

$\nabla f=(2x+y-4,\ x+2y)$,块常数 $L_x=L_y=2$。从 $(0,0)$ 出发,按 $x\to y\to x$ 更新,每次阈值为 $1/2$。

第一次:$g_x=-4$,试探点 $v_x=2$,故 $x_1=S_{0.5}(2)=1.5$。

第二次:$g_y(1.5,0)=1.5$,试探 $v_y=-0.75$,故 $y_2=S_{0.5}(-0.75)=-0.25$。

第三次:$g_x(1.5,-0.25)=-1.25$,试探 $v_x=2.125$,故 $x_3=1.625$。

微步 更新块 $(x,y)$ $F(x,y)$
0 — $(0,0)$ $5.5$
1 $x$ $(1.5,0)$ $3.25$
2 $y$ $(1.5,-0.25)$ $3.1875$
3 $x$ $(1.625,-0.25)$ $3.171875$

最优点可由次梯度条件得到:在 $x>0,y<0$ 的区间解 $2x+y-3=0$、$x+2y-1=0$,得

\[\boxed{(x^*,y^*)=(5/3,-1/3),\qquad F^*=19/6.}\]

这说明逐块优化可以逼近最优点,但示例中的前三步并非有限步求解。

七、失败反例:耦合约束会锁死单坐标

考虑凸且光滑的

\[\boxed{\min_{x+y=1}\tfrac12(x-1)^2+\tfrac12y^2.}\]

从可行初值 $(0,1)$ 出发,若固定 $y=1$,等式迫使 $x=0$;若固定 $x=0$,等式迫使 $y=1$。因此每次只改变一个坐标、并保持等式可行,每一步都无法移动。

但全局最优点是 $(1,0)$,目标值从 1 降到 0。问题出在耦合等式没有独立坐标可行方向,而不是凸性失效。可以合并 $(x,y)$ 为一个联合块,或者通过变量分裂与后续 ADMM/PDHG 等处理。

另一个边界:若永远只更新一部分块,即使强凸目标 $f(x,y)=\tfrac12(x^2+y^2)$ 也可能从 $(0,1)$ 卡住,因为 $y$ 从未更新。块覆盖性与规则设计不可省略。

八、KKT 复习:活跃不保证正乘子

考虑

\[\min_{x\ge0,y\ge0}\tfrac12(x+1)^2+\tfrac12y^2.\]

约束写作 $-x\le0,-y\le0$,最优点 $(0,0)$ 两约束都活跃。拉格朗日函数

\[\mathcal L=\tfrac12(x+1)^2+\tfrac12y^2-\lambda_x x-\lambda_y y.\]

KKT 驻点条件 $x+1-\lambda_x=0$、$y-\lambda_y=0$,给出 $\lambda_x=1,\lambda_y=0$。两个乘子非负,且互补松弛都成立。活跃约束可以对应零乘子。 块指标函数的次梯度就是相应法锥,这与块投影 Prox 完全一致。

九、关系图

flowchart TD
 A["块方向 Smooth:L_j"] --> B["块二次上界"]
 B --> C["块 Prox / 组软阈值"]
 C --> D["充分下降"]
 D --> E["循环 + 紧水平集"]
 E --> F["聚点块固定 + 可分性"]
 F --> G["凸性 ⇒ 全局最优"]
 D --> H["纯光滑 + 随机块 + PL"]
 H --> I["期望几何收敛"]
 C --> J["可分指标函数 ⇒ 块投影"]
 J --> K["法锥 / KKT"]
 C --> L["耦合约束非可分"]
 L --> M["单块可能停滞 ⇒ 联合块或分裂"]

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

首次课堂不公布答案、正确选项或开放题评分要点。独立 JSON 含标准答案,请作答前不要打开,以免泄题。

Lv1|块近端更新的最优性条件|预计2分钟

设 F(x)=f(x)+Σ_j h_j(x_j),其中 f 可微、每个块方向 L_j-Smooth,h_j 真、下半连续、凸,L_j>0。固定其余块,把第 j 块更新为 p=prox_{h_j/L_j}(x_j−∇_j f(x)/L_j)。下列哪项必然成立?

  • A. 由于 f 整体可能耦合,p 一定等于整个 F 的第 j 块全局最优解。
  • B. 必有 0∈∇_j f(x)+L_j(p−x_j)+∂h_j(p);该条件来自近端子问题,而非整个问题的全局 KKT。
  • C. 只要每个块 L_j-Smooth,F 就必定强凸。
  • D. 即使 h 不是块可分函数,也总能把 prox_h 写成各块 prox_{h_j} 的并列组合。

提示:把本轮块二次模型写出来,对它应用 Fermat 次梯度条件;分清块子问题和全局目标。

Lv2|耦合二次函数的两次坐标 Prox|预计4分钟

令 f(x,y)=0.5(x−4)^2+0.5(y+2)^2+0.5(x+y)^2,h(x,y)= x + y 。从 (0,0) 出发,块顺序先 x 后 y,每块采用 L_x=L_y=2 的近端梯度步,更新后立即用于下一块。求两次块更新后的完整目标值 F=f+h;填写数值,保留四位小数。

提示:∂_x f=2x+y−4,∂_y f=x+2y+2;对每次试探点做阈值为 0.5 的软阈值。

Lv3|耦合等式约束使单坐标法停滞|预计5分钟

考虑 min 0.5(x−1)^2+0.5y²,约束 x+y=1,从可行初值 (0,1) 出发。每次固定另一个坐标,对当前单个坐标进行精确可行最小化。哪项正确?

  • A. 更新 x 一次便达到 (1,0),因为目标严格凸。
  • B. 因为约束集合凸,逐坐标可行最小化必然朝最优点移动。
  • C. 每个单坐标可行切片只有当前点,因此算法停在 (0,1),但全局最优点是 (1,0);需要联合块或能维持耦合约束的其他策略。
  • D. 该问题的 KKT 不能成立,因为最优点位于等式约束上。

提示:固定 y=1 时等式给出什么 x?固定 x=0 时 y 又是多少?

Lv4|块下降、循环收敛、组稀疏与 KKT|预计13分钟

设 x=(x_1,…,x_m),F(x)=f(x)+Σ_j h_j(x_j),其中 f 凸且可微、每块沿本块方向有 L_j>0 的 Lipschitz 梯度,h_j 真、下半连续、凸。A(12分):固定其余块,把 x_j 更新为 p=prox_{h_j/L_j}(x_j−∇_j f(x)/L_j)。从块二次上界与近端子问题强凸性证明 F(x)−F(x^+)≥(L_j/2)   p−x_j   ²,并给出块梯度映射。B(12分):另假设每个 h_j 全空间有限且连续、初始水平集紧,循环按固定顺序逐块精确执行 A。解释为何位移平方可求和、每轮更新幅度趋零;证明所有聚点都为全局最优点,目标值趋于 F*;说明为何不能直接用于非可分 h。C(10分):令向量块的 h_j(u)=λ   u   2,推导组软阈值 prox{h_j/L_j}(v);当 v=(6,8)、λ=5、L_j=2 时求一次更新结果。D(6分):求 min_{x≥0,y≥0} 0.5(x+1)^2+0.5y² 的最优点,把约束写成 −x≤0、−y≤0,给出活跃约束的 KKT 乘子,验证互补松弛并说明活跃乘子可以为零。

提示:A 将 u=x_j 代入块近端子问题的强凸性不等式;B 对微步下降量求和,再利用一轮有限个块、Prox 连续性与可分性;C 分 u=0 与 u≠0;D 约束梯度分别是 (−1,0)、(0,−1)。

十一、下一讲

第31课|2026-11-19:ADMM 的增广拉格朗日与三步更新。 将从带耦合等式约束的 $f(x)+g(z)$ 问题出发,推导 $x$ 更新、$z$ 更新与对偶更新,解释惩罚参数、原始/对偶残差与 KKT。

自测按 15/20/25/40 计分。80分及以上正常继续;60—79分补充块 Prox 例子;低于60分重点复习块下降不等式、可分性与 KKT。日期课号不会因成绩改变。