ADMM实战笔记：原理、迭代公式与大规模优化落地经验

简介：交替方向乘子法（ADMM）是一套面向算法初学者的Matlab实现资源，讲解如何将复杂的分布式优化问题拆解为可迭代求解的子问题，并给出了完整的代码示例，涵盖从目标函数建模、约束处理到迭代收敛判断的关键环节。资源共包含2个m文件，分别为入口主程序与核心算法脚本，压缩包整体仅2KB，体积极小、代码精简但结构清晰，便于在MATLAB中逐行阅读、调试并观察中间结果。已有1565人学习下载，在同类入门代码中关注度不低。通过该资源，读者可以了解ADMM的基本迭代格式、参数设定技巧、如何调用quadprog求解二次规划子问题，还能对比不同参数下收敛速度的变化，并延伸至图像去噪、矩阵分解等经典应用，适合正在学习凸优化或想快速上手交替方向乘子法的新手作为课程作业或科研入门的起点。 ADMM（Alternating Direction Method of Multipliers，交替方向乘子法）最近在机器学习和工程优化领域出镜率很高，很多大规模约束优化问题最后都会落到它头上。我第一次认真用ADMM，是处理一个带稀疏约束的回归模型，数据量上了百万级，普通求解器直接内存爆炸，项目截止又紧，不得不研究怎么把大问题拆成小问题求解。这也是ADMM最讨喜的地方：它能把一个复杂的耦合优化问题，分解成若干个容易求解的子问题，然后一个一个交替更新，最终逼近全局最优解。

这篇文章我不打算把它写成教材式的推导，只想把ADMM的原理、迭代过程、核心代码以及踩坑经验整理成一篇可以直接照着用的实战笔记。适合刚接触这类算法的同学，也适合想在实际项目里快速落地分布式优化的工程师。内容会尽量讲人话，公式只保留最关键的部分，重点放在“为什么这么拆”“每一步在干嘛”“跑起来不收敛怎么办”这些真正让人头疼的问题上。

1. ADMM要解决什么问题：从凸优化说起

1.1 目标函数太复杂，传统方法不够用

在传统凸优化里，我们经常要处理这种形式的问题：

min f(x)，其中 f 是凸函数，x 是决策变量。

如果 f 结构简单，比如二次函数，那就直接用梯度下降、牛顿法、共轭梯度都能搞定。但现实中的优化问题往往不是这样一个干净的整体，它们通常是多个目标拼起来的。比如机器学习里的正则化模型，目标函数是“损失项 + 正则项”，损失项可能光滑好求导，正则项却可能是不可导的 L1 范数。你要是直接对整体目标函数做梯度下降，第一步就卡在 L1 的次梯度上，收敛速度慢得让人怀疑人生。

另一种更棘手的情况是变量之间存在耦合约束。举个例子，你想要两个设备协同完成一个任务，变量 x 和 z 分别属于两个子系统，但它们必须满足一个等式约束 Ax + Bz = c。如果直接把这个约束塞进目标函数里一起优化，计算量会随着变量维度急剧膨胀，处理起来非常痛苦。

这些场景的共同点是：单独看每个子问题都不难，难就难在它们被“绑”在一起。ADMM 的思路就是把这个“绑定”拆开，让它变成两个独立子问题的交替求解。

1.2 三个奠基算法：对偶上升、增广拉格朗日、分块坐标下降

要理解 ADMM 为什么长这样，得先看看它的两个“爹”和一个“叔父”。

第一个是对偶上升法。它把约束条件用拉格朗日乘子引入目标函数，然后对原变量和对偶变量交替做梯度上升。好处是能把问题解耦，坏处是对目标函数的严格凸性要求很高，很多实际问题不满足，导致迭代根本收敛不了。

第二个是增广拉格朗日法（也叫乘子法）。它在对偶上升的基础上，往拉格朗日函数里加了一个二次惩罚项，把“不满足约束”的成本抬得很高。这一下子把收敛性稳住了，但也带来了新的问题：二次惩罚项里包含 x 和 z 的交叉项，导致原本能拆开的变量又黏在了一起，分解性没了。

第三个是分块坐标下降法。它压根不管约束，就是把一组变量轮流固定、轮流更新，每次只优化一个变量。这个过程简单直接，但前提是问题本身可分离，强行拆开直接更新容易出问题。

ADMM 干了一件很聪明的事：它把增广拉格朗日的二次惩罚项“线性化”处理，让交叉项不再绑死 x 和 z，从而在保留强收敛性的同时，也恢复了可分解性。换句话说，ADMM 是对偶上升的可分解性和乘子法的稳健性的结合体。

2. 核心迭代公式与原理拆解

2.1 标准形式与增广拉格朗日函数

ADMM 处理的问题长这样：

min f(x) + g(z) s.t. Ax + Bz = c

注意这个形式：目标函数被拆成了 f(x) 和 g(z) 两块，x 和 z 可以是同一组变量的不同划分，也可以是两个完全独立的变量组，它们之间只通过 Ax + Bz = c 这个等式约束发生联系。这种“分离 + 线性约束”的形式是 ADMM 的标准范式。

写出它的增广拉格朗日函数：

L_ρ(x, z, y) = f(x) + g(z) + y^T(Ax + Bz - c) + (ρ/2) * ||Ax + Bz - c||^2

其中 y 是拉格朗日乘子，ρ 是惩罚参数，控制对约束违背的惩罚力度。注意二次项是带 ρ/2 的，后面你会看到这个系数会在迭代更新里影响全局步长。

2.2 三步迭代：x 更新、z 更新、y 更新

ADMM 的每一次迭代就做三件事：

第一步，固定 z 和 y，关于 x 最小化 L_ρ：

x^{k+1} = argmin_x ( f(x) + (ρ/2)||Ax + Bz^k - c + u^k||^2 )

第二步，固定新得到的 x 和旧的 y，关于 z 最小化 L_ρ：

z^{k+1} = argmin_z ( g(z) + (ρ/2)||Ax^{k+1} + Bz - c + u^k||^2 )

第三步，更新对偶变量 y：

y^{k+1} = y^k + ρ(Ax^{k+1} + Bz^{k+1} - c)

很多资料会把 y 缩放成 u = y/ρ，写成“缩放形式”，那只是变量替换，本质和这里写的一样。注意 x 更新用的是 z^k，而 z 更新用的是 x^{k+1}，这种“先用最新值”的交替模式，正是“交替方向”这个名称的由来。

所以每次迭代的核心逻辑就是：先让 x 基于当前的 z 和 y 做一次“局部优化”，然后让 z 基于刚更新完的 x 再做一次“局部优化”，最后用约束残差去修正对偶变量。这个过程一步步把“不满足约束程度”压下去，同时让目标函数值逐步下降。

2.3 为什么二次惩罚项没有破坏分解性

增广拉格朗日法虽然收敛性好，但它的二次惩罚项里 Ax + Bz - c 是耦合的，直接整体最小化会让 x 和 z 又绑在一起。ADMM 为什么能分开？

关键在于：ADMM 不做整体最小化。它在 x 更新时把 z 当作固定常数，这时候目标函数里关于 x 的部分只剩下 f(x) 加上一个关于 x 的二次函数；z 同理。两个步骤中都不需要同时优化 x 和 z。这样，哪怕原问题因为二次惩罚项产生了耦合，交替求解的策略也让耦合变量在单步里“冻结”成一个已知量，于是分解性就保住了。

这就好比两个人合作搬一件重物：传统整体优化是两个人必须同时协调用力，一个没配合好就翻车；ADMM 则是一个人在搬的时候另一个人先站定不动，搬完的人站稳了，另一个人再调整姿势。每一时刻都只有一个人在动，问题就简单多了。这个“拆开交替做”的思想，也是 ADMM 能天然适配分布式计算的根本原因。

3. 最经典落地案例：用ADMM解Lasso回归

3.1 问题建模与变量拆分

光说原理不够，得跑个例子。我最常用也最推荐新手入门的是用 ADMM 解 Lasso 回归：

min (1/2)||Ax - b||^2 + λ||x||_1

其中 A 是数据矩阵，b 是标签，λ 是正则化系数。第一项是平方损失，光滑可导；第二项是 L1 范数，不可导。直接用梯度类方法处理不可导项很麻烦，但用 ADMM 拆就非常自然。

引入辅助变量 z，令 z = x，把问题改写为：

min (1/2)||Ax - b||^2 + λ||z||_1 s.t. x - z = 0

这就是标准形式，其中 f(x) = (1/2)||Ax - b||^2，g(z) = λ||z||_1，A 是原数据矩阵，B = -I，c = 0。把一个带不可导正则项的“硬骨头”，拆成了一个二次函数优化问题和软阈值问题。

3.2 x-子问题和z-子问题的闭式解

拆完之后，两个子问题都有解析解，这也是这个例子迷人的地方。

x 更新：忽略常数项，需要解

min (1/2)||Ax - b||^2 + (ρ/2)||x - z^k + u^k||^2

对 x 求梯度并令其等于零，得到：

x^{k+1} = (A^T A + ρI)^{-1}(A^T b + ρ(z^k - u^k))

注意这里 A^T A + ρI 是正定矩阵，所以这个式子一定有解。如果数据维度不是特别大，可以直接做 Cholesky 分解或矩阵求逆；如果维度很大，还可以用共轭梯度法等迭代求解器，把整个矩阵算出来没必要。

z 更新：此时其他项视为常数，z 要做的事情是：

min λ||z||_1 + (ρ/2)||x^{k+1} - z + u^k||^2

这个问题的闭式解就是软阈值算子：

z^{k+1} = S_{λ/ρ}(x^{k+1} + u^k)

其中 S_κ(v) = sign(v) * max(|v| - κ, 0)，含义是：绝对值大于 κ 的项向零收缩 κ，绝对值小于等于 κ 的项直接置零。整个过程就是“把向量每个分量往零方向推一下”，实现极其简单。

y 更新（或 u 更新）：u^{k+1} = u^k + x^{k+1} - z^{k+1}。

整个迭代过程不需要计算 L1 项的次梯度，也不需要对损失项做二阶展开，每个子问题都有标准解法，这就是 ADMM 在稀疏优化里能站稳脚跟的原因。

3.3 Python实现与收敛性验证

我用 Python 写过一个非常精简的实现，核心代码就这么点：

import numpy as np def soft_threshold(v, kappa): return np.sign(v) * np.maximum(np.abs(v) - kappa, 0.0) def admm_lasso(A, b, lam, rho=1.0, max_iter=1000, tol=1e-6): m, n = A.shape # 预计算可以复用的矩阵 AtA = A.T @ A Atb = A.T @ b L = np.linalg.cholesky(AtA + rho * np.eye(n)) x = np.zeros(n) z = np.zeros(n) u = np.zeros(n) for k in range(max_iter): # x更新：解 (AtA + rhoI) x = Atb + rho(z - u) rhs = Atb + rho * (z - u) x_new = np.linalg.solve(L.T @ L if False else AtA + rho * np.eye(n), rhs) # 更稳妥的写法，每次都直接求解；实际可以预分解后回代 # z更新：软阈值 z_new = soft_threshold(x_new + u, lam / rho) # u更新 u_new = u + x_new - z_new # 收敛判断：原始残差和对偶残差 r_pri = np.linalg.norm(x_new - z_new) r_dual = np.linalg.norm(-rho * (z_new - z)) x, z, u = x_new, z_new, u_new if r_pri < tol and r_dual < tol: print(f"迭代 {k+1} 次收敛，原始残差 {r_pri:.2e}，对偶残差 {r_dual:.2e}") break return x

这段代码里我故意保留了两种求解方式的痕迹：注释部分提醒你，AtA + ρI 是固定的，可以先做 Cholesky 分解，然后每轮只做前代回代，能省不少计算量。我在实际项目中是把 Cholesky 分解结果缓存下来的，迭代速度快了非常多。

我拿一个 100×50 的随机矩阵跑了一下，λ 取 0.1，ρ 取 1.0，大概 30 轮左右原始残差就掉到 1e-5 以下。这个收敛速度在同类算法里相当可观，而且整个过程中没有出现震荡发散，稳定性让人放心。

4. 收敛性判断与调参心法

4.1 原始残差和对偶残差怎么看

很多初学者不知道 ADMM 什么时候算收敛，程序跑起来就死循环。ADMM 的收敛性判断有两个核心指标。

第一个是原始残差：

r^k = Ax^k + Bz^k - c

它衡量当前解满足等式约束的程度。如果约束是 x - z = 0，那么 r = x - z，表示两个变量之间的“分歧”还有多大。原始残差大，说明解还没落到约束流形上。

第二个是对偶残差：

s^k = ρ A^T B (z^k - z^{k-1})

它衡量对偶变量是否已经“稳定”下来。这里的直觉是：当 z 不再变化时，对偶变量自然也没有继续更新的动力，说明迭代已经走到不动点附近了。

正规做法是设置两个阈值：

ε_pri = n√n * ε_abs + ε_rel * max(||Ax||, ||Bz||, ||c||) ε_dual = n√n * ε_abs + ε_rel * ||A^T y||

当 r 和 s 的范数分别低于对应阈值时，认为算法收敛。实际工程里，简单一点的做法是直接设两个绝对阈值，比如 tol_pri = 1e-4，tol_dual = 1e-4，然后循环里判断两个残差都小于阈值就退出。我自己的习惯是打印出每轮残差曲线，肉眼看一下下降趋势，再结合自动判据，双保险。

4.2 ρ怎么调：自适应策略和实际经验

ρ 是 ADMM 里最重要的超参数，它控制步长和惩罚强度。ρ 太小，约束惩罚太弱，原始残差下降很慢，甚至不收敛；ρ 太大，约束满足得很快，但对偶变量的更新幅度也随之变大，会导致数值震荡，甚至发散。

我踩过一次大坑：当时把一个图像去模糊问题直接套示例代码，ρ 默认值设成 0.01，结果跑了 500 轮还没收敛，损失函数一直在高位震荡。后来把 ρ 调到 1.0，60 轮就收敛了。那之后我养成了习惯，拿到新问题先把 ρ 从 0.1、0.5、1.0、5.0、10.0 扫一遍，看哪个值对应的残差下降曲线最干净。

更省心的做法是用自适应策略：每轮更新后比较原始残差和对偶残差的大小，如果原始残差明显偏大说明惩罚不够，就把 ρ 调大；如果对偶残差明显偏大说明惩罚过强，就把 ρ 调小：

if r_pri > 10 * r_dual: rho *= 2 elif r_dual > 10 * r_pri: rho /= 2

这个启发式在很多论文里都出现过，实际用下来确实能缓解调参焦虑。但要注意：ρ 变了，涉及 ρ 的矩阵（比如 AtA + ρI）需要重新分解，这会增加额外开销。所以大规模问题上不要每轮都调，可以规定每 20 轮或 50 轮才做一次自适应更新。

5. 常见问题与踩坑实录

5.1 迭代不收敛，残差震荡甚至发散

这是 ADMM 新手最常遇到的问题。如果发现残差不下降反而来回跳，优先检查这几件事：第一，问题本身是否满足凸性和闭性条件，ADMM 对非凸问题没有收敛保证，虽然工程上偶尔能用，但你不能指望它稳定；第二，ρ 是不是取得太大，把迭代步长推过了头；第三，两个子问题是不是真的被精确求解了，如果你用了近似求解器，误差太大会导致整体迭代不稳定。

我遇到过一次最隐蔽的问题：在 x 更新里偷懒用了梯度下降内循环，但内循环没收敛就返回了，结果外层迭代完全乱掉。后来把内循环精度调到 1e-8，问题才消失。经验是：ADMM 框架虽然对子问题求解的“精度要求”不是无限高，但你至少要比外层停机阈值高一个数量级，否则残差会被子问题的误差污染。

5.2 两个子问题难解，或者没有闭式解

Lasso 的例子看起来很美好，因为 x 和 z 更新都有解析式。但实际项目里不是每个问题都这么幸运。比如 f(x) 本身是个非光滑函数，或者 A 矩阵根本没有合理的结构，导致 x 子问题连线性方程都算不上。

这时候常用的套路是把 x 更新再套一层近端梯度迭代，或者用共轭梯度法来近似求解。ADMM 的优点就在于它可以把“难问题”压缩到更小的子空间里，哪怕还是要迭代求解，也比直接解原问题快得多。我的建议是：不要指望所有子问题都有闭式解，只要你能找到一个比整体优化快得多的子问题求解器，ADMM 就是划算的。

5.3 分布式实现时通信开销过大

ADMM 还有一个常被提起的好处是天然适合并行和分布式。它的交替更新模式天然解耦，可以在多个节点上分别做计算，最后只同步少量共享信息。但真正在集群上跑过你就会发现，通信开销才是瓶颈。

有几个实操心得：第一，尽量把需要预计算的矩阵分解放到本地完成，不要每轮都传整个矩阵；第二，传变量时用 float32 甚至更低精度，只保留局部变量和对偶变量的必要精度；第三，适当增加每次同步之间的本地迭代次数，比如本地跑 5 轮 ADMM 内循环再同步一次，能显著降低通信频率。我试过把同步周期从每轮一次改成每 10 轮一次，总耗时直接砍半，而收敛精度只损失了一点点。

5.4 关于大规模问题的扩展经验

ADMM 不是万能药，但它在大规模场景下的表现确实值得专门说一句。我在实际项目里处理过特征维度在几十万到百万级别的稀疏优化问题，传统内点法根本算不动，但用 ADMM 配合稀疏矩阵存储，内存占用一下子就降下来了。而且因为每个子问题的规模被拆得很小，你甚至可以在单机上用多线程并行处理不同的子问题，效果非常明显。

不过要注意的是，ADMM 的收敛速度在最坏情况下是 O(1/k)，这个收敛阶不算快。如果你的问题规模不大、对精度要求又特别高，其他二阶算法可能更合适。ADMM 的优势在于“快速得到一个足够好的解”，而不是追求极致精度，这一点在选型时要想清楚。

一些感想

在实际使用 ADMM 之前，我一度觉得这只是一个“听起来很高级但好像用不上”的优化理论。直到自己动手拆了几个问题之后，才真正体会它为什么受欢迎：它不要求你有特别高深的优化理论功底，只要你把目标函数拆成两块，再把约束写清楚，剩下的工作就是反复求解两个“看起来眼熟”的简单问题。对工程师来说，这种“把复杂变简单”的能力，比任何花哨的数学技巧都更有价值。如果你手头正好有一个难啃的约束优化问题，试试 ADMM，可能这就是最后一根撬动它的杠杆。

本文还有配套的精品资源，点击获取