本页目录

凸优化 III · 增广拉格朗日与 ADMM

对标：Boyd et al. Distributed Optimization via ADMM（专著级综述）｜前置：cvx-01/02、本科优化 III 大规模问题的解法哲学：拆——把纠缠的目标拆成各自好解的块，用对偶变量协调。本页从对偶上升法的缺陷出发，经增广拉格朗日的修复，抵达 ADMM：统计学习与分布式计算的主力求解器。

1. 对偶上升法及其脆弱

约束问题 \(\min f(x)\ \text{s.t.}\ Ax = b\)，对偶函数 \(q(y) = \min_x L(x, y)\)。对偶上升：交替"给定 \(y\) 解 \(x\)""对 \(y\) 做梯度上升"（\(\nabla q(y) = Ax^* - b\)——对偶梯度恰是约束残差【一行：Danskin 定理/包络定理】）：

\[ x_{k+1} = \arg\min_x L(x, y_k), \qquad y_{k+1} = y_k + \alpha_k(Ax_{k+1} - b) \]

脆弱点：内层 \(\arg\min\) 要求 \(f\) 严格凸且良态——\(f\) 仿射方向平坦时 \(x\)-步无界（LP 就崩）；收敛还挑步长。但它有一个宝贵基因：\(f\) 可分时 \(x\)-步逐块并行（分布式的种子）。

2. 增广拉格朗日（Method of Multipliers）

修复：给拉格朗日加二次罚项——

\[ L_\rho(x, y) = f(x) + y^\top(Ax - b) + \frac{\rho}{2}\|Ax - b\|^2 \]

\(x\)-步对 \(L_\rho\) 求解（罚项补足强凸性——平坦方向被 \(\rho\) 项撑起），\(y\)-步固定步长 \(\rho\)：

\[ y_{k+1} = y_k + \rho\,(Ax_{k+1} - b) \]

为什么步长恰取 \(\rho\)【证明】：\(x_{k+1}\) 满足 \(0 = \nabla f + A^\top y_k + \rho A^\top(Ax_{k+1} - b) = \nabla f + A^\top y_{k+1}\)——每步迭代后原始最优性条件自动精确成立，只欠约束可行性；算法 = "保持对偶可行、逐步逼近原始可行"。\(\blacksquare\) 代价：罚项 \(\|Ax - b\|^2\) 把各块 \(x\) 耦合了——可分性（对偶上升的宝贵基因）被杀死。鱼与熊掌，于是——

3. ADMM：既要稳健又要可拆

问题形态（与 cvx-01 Fenchel 同型）：\(\min f(x) + g(z)\ \text{s.t.}\ Ax + Bz = c\)。

ADMM（交替方向乘子法）：对增广拉格朗日不联合求解而交替：

\[ \begin{aligned} x_{k+1} &= \arg\min_x L_\rho(x, z_k, y_k) \\ z_{k+1} &= \arg\min_z L_\rho(x_{k+1}, z, y_k) \\ y_{k+1} &= y_k + \rho(Ax_{k+1} + Bz_{k+1} - c) \end{aligned} \]

——Gauss–Seidel 式的"轮流坐庄"（数值 II 迭代法的既视感）：每块面对的都是"自己 + 二次项"的好问题（常有闭式：prox！cvx-02 的算子库整个接入——\(g\) 是 L1 时 \(z\)-步 = 软阈值）。

定理（收敛性）【骨架】 \(f, g\) 闭凸、强对偶成立，则 ADMM 满足：残差 \(Ax_k + Bz_k - c \to 0\)、目标值 → 最优、\(y_k \to\) 对偶最优。思路：Lyapunov 函数 \(V_k = \frac1\rho\|y_k - y^*\|^2 + \rho\|B(z_k - z^*)\|^2\) 单调不增且每步下降量控制残差（三条最优性不等式相加配平——Boyd 附录的六页代数，结构清晰簿记较重，骨架级掌握恰当）。\(\blacksquare\) （速率：一般凸 \(O(1/k)\)（遍历意义）【引用】；不保证快，胜在稳（几乎不挑参数）+ 拆（步步可分布式）。）

读法：ADMM = 增广拉格朗日的稳健 + 对偶上升的可拆——两代方法的合题。\(\rho\) 的角色：大 \(\rho\) 压约束残差快、小 \(\rho\) 压目标快（自适应 \(\rho\) 的工程惯例【引用】）。

4. 应用形态学（一个模板生成一族求解器）

问题	拆法 \(f + g\)	\(z\)-步的 prox
Lasso	最小二乘 + \(\lambda\lVert z\rVert_1\)（\(x = z\)）	软阈值
鲁棒 PCA	核范数 + L1（\(L + S = M\)）	奇异值软阈值 + 软阈值
一致性优化（分布式）	\(\sum_i f_i(x_i)\) + 一致约束 \(x_i = z\)	均值（\(z\)-步 = 各节点平均）
图像去噪 TV	保真项 + 全变差	逐边收缩

一致性形态是分布式机器学习的原型：各节点本地解自己的 \(f_i\)（数据不出门），只交换 \(x_i\) 与乘子——联邦学习的优化骨架；🔗 你的 Medusa 若做多机 A/B 参数聚合，这就是教科书方案。

5. 练习与要点

例 1（ADMM 手推 Lasso） 写出三步的显式公式：\(x\)-步 = 解 \((A^\top A + \rho I)x = A^\top b + \rho(z - u)\)（岭回归型——正则化的另一次上岗）、\(z\)-步 = 软阈值、\(u\)-步 = 残差累加（scaled form）。三行即一个可实现的 Lasso 求解器——亲手写进 30 行 numpy 是本页的最佳作业。

例 2（为什么不三块交替） 三块及以上的朴素 ADMM 可以发散（Chen–He–Ye–Yuan 反例【引用】）——"两块的和谐不自动推广"：把问题重组成两块（变量堆叠）是标准规避法。定理边界即工程红线。

例 3（对偶上升崩溃的实感） \(f(x) = c^\top x\)（线性）+ 等式约束：\(x\)-步 \(\arg\min\) 无界 ⇒ 对偶上升死；同题加 \(\frac\rho2\|Ax-b\|^2\) 立刻良定——增广项"扶起平坦方向"的最小演示。\(\blacksquare\)

下一页：二阶世界的高峰——内点法与半定规划：多项式时间凸优化的理论与 SDP 的应用版图，凸优化四页收官。