简介交替方向乘子法ADMM是一种结合对偶上升与乘子法优势的优化算法在压缩感知、低秩矩阵恢复、机器学习等领域应用广泛。代码专为初次接触ADMM的新手编写两个m文件分工明确一个集中展示带等式或不等式约束的二次规划问题建模与参数设置另一个实现ADMM的核心迭代逻辑包括变量分裂、x和z交替更新、对偶变量拉格朗日乘子调整以及收敛判据方便读者对照公式逐行理解。整个压缩包仅含2个文件、大小2KB轻量紧凑没有任何冗余内容在MATLAB中可直接运行、修改或调试尤其适合边读边动手验证。目前已有1565人学习/下载这种由主程序和核心函数构成的代码结构能让初学者快速定位模型建立与算法更新的关键部分动手验证ADMM的收敛过程。 ADMM 这个缩写我在不同项目里跟它打过好几年交道了。先说结论如果你遇到一个优化问题目标函数能拆成两块或者变量规模大到单机内存吃紧那交替方向乘子法ADMM基本是性价比最高的那类解法。它不像内点法那样依赖二阶信息也不需要像梯度下降那样小心翼翼地调学习率靠的是一套拆开求解、再通过乘子协调的思路把大问题化整为零。这篇文章我把自己的实现经验、踩坑记录和调参心得都整理出来给打算上手 ADMM 的朋友做个参考。我最早接触 ADMM 是在做稀疏建模相关的工作当时要解带 L1 正则的回归问题数据量大、特征维度高普通梯度法收敛慢直接求闭式解又不可能。后来换成 ADMM配合软阈值算子迭代速度明显上一个台阶。这篇文章会用最直白的方式把原理讲清楚然后拿一个 Lasso 实例从头到尾跑一遍包括代码、参数怎么调、残差怎么判断最后聊聊我在实际工程里踩过的几个典型坑。1. ADMM 到底在做什么1.1 从拆问题这件事说起很多工程问题最后都能写成这种形式最小化两个函数之和中间夹着一个线性等式约束。写成数学表达就是[ \min f(x) g(z) \quad \text{s.t.} \quad Ax Bz c ]f 和 g 是两个不同的惩罚项x 和 z 是我们想求的变量。举个例子Lasso 回归的目标函数是平方损失加上 L1 正则如果把它写成上述形式可以令 f(x) 负责平方损失g(z) 负责 L1 正则再用一个等式约束把 x 和 z 拉到相等。这类问题麻烦在哪儿呢如果直接用梯度下降L1 项在零点不可导收敛会很别扭如果全部写成一个大约束优化问题维度上去以后内点法又承受不住。ADMM 的核心策略是把 x 和 z 当作两个独立变量先分别针对其中一个做最小化然后通过拉格朗日乘子把两者的差异拉回来。一句话概括就是交替求解、乘子协调。打个比方两个人合作搬一张大桌子一个人负责托左边一个人负责托右边各自按照自己的节奏调整姿势但中间必须要有一个通信机制让他们保持步伐一致。ADMM 里的乘子就是那个通信机制每轮迭代完都检查一下 x 和 z 差了多少然后把这个差值反馈到下一轮更新里。1.2 为什么不是纯拉格朗日法你可能会问拉格朗日乘子法不是早就有了吗为什么非要 ADMM这个问题我当初也困惑过。传统的对偶上升法要求原问题有很强的凸性和光滑性否则对偶上升过程非常不稳定。增广拉格朗日法也叫乘子法加了一个二次惩罚项稳定性好很多但它要求在每一轮迭代里同时精确求解 x 和 z 的联合最小化。问题是这个联合最小化往往没有闭式解内部还得套一层数值优化计算开销很大。ADMM 的高明之处在于它不强迫每轮精确求解联合问题而是把联合问题拆成 x 子问题和 z 子问题各自单独求最小值。这样做的代价是收敛需要的迭代次数变多了但每一轮的计算量大幅下降尤其当 x 子问题和 z 子问题都有闭式解时整体效率非常可观。2. 数学原理与关键参数2.1 标准形式的三个迭代步骤先给出标准形式的增广拉格朗日函数[ L_\rho(x,z,y)f(x)g(z)y^T(AxBz-c)\frac{\rho}{2}|AxBz-c|_2^2 ]这里 y 是拉格朗日乘子ρ 是惩罚参数。ADMM 的迭代分三步走x 更新固定 z 和 y最小化 L_ρ 关于 x 的部分z 更新固定 x 和 y最小化 L_ρ 关于 z 的部分y 更新沿约束残差方向上升y y ρ(Ax Bz - c)前两步是拆最后一步是合。每轮迭代完后Ax Bz - c 这个残差会不断变小y 则累积了历史信息用来推动约束满足。理解这个结构很重要因为后面判断收敛、调参、改分布式版本都要回到这三步来看。2.2 缩放形式为什么更常用理论推导里用的是上面这种非缩放形式但工程实现里我基本都用缩放形式scaled form。思路很简单令 u y/ρ代入拉格朗日函数并配方可以消掉线性项得到[ L_\rho(x,z,u)f(x)g(z)\frac{\rho}{2}|AxBz-cu|_2^2 - \frac{\rho}{2}|u|_2^2 ]迭代时 u 的更新退化成 u u (Ax Bz - c)。不要小看这个变换它至少带来两个好处一是代码里少维护一个乘子向量二是缩放形式下残差的量纲跟原始约束一致调试起来直觉上更舒服。2.3 惩罚参数 ρ 的双重身份ρ 是我最想强调的参数。它表面上是二次惩罚项的权重实际上还充当了乘子更新的步长。ρ 偏大约束满足得更快但 x 和 z 的迭代容易因为步子迈太大而产生振荡ρ 偏小约束慢慢靠拢整体收敛速度会被拖慢。实际调参时我没有死磕理论最优值而是先固定 ρ 1跑一轮看残差曲线再根据残差变化趋势按 2 倍或 0.5 倍调整。这里有一个实用的小技巧把原始残差和对偶残差的比值控制在 1 到 10 之间小于 1 说明约束已经紧到可能过头了可以适当加大 ρ大于 10 说明约束还没跟上需要减小 ρ。3. 从零实现一个 Lasso 求解器3.1 问题转换与闭式解推导Lasso 问题的标准形式是[ \min \frac{1}{2}|A x - b|_2^2 \lambda |x|_1 ]把它改写成 ADMM 形式可以令 f(x) (1/2)||Ax - b||_2^2g(z) λ||z||_1约束取 x - z 0。注意这里 A 和 B 一个是单位阵、一个是负单位阵约束非常简洁。x 子问题因为只有二次项直接求导置零就能得到闭式解[ x (A^T A \rho I)^{-1}(A^T b \rho(z - u)) ]z 子问题对应 L1 范数的近端算子也就是软阈值运算[ z S_{\lambda/\rho}(x u), \quad S_\kappa(a) \mathrm{sign}(a)\max(|a| - \kappa, 0) ]软阈值操作理解起来很形象把每个分量往零的方向压一个 κ 的距离不够压的直接变成 0。这也是 L1 正则能产生稀疏解的根本原因。整个算法里最贵的部分就是 x 子问题里那个矩阵求逆好在 A^T A ρI 是固定不变的可以预先做一次 Cholesky 分解后面每轮只做回代速度会快很多。3.2 Python 代码与迭代流程下面是我常用的一个最小实现逻辑清晰适合拿去改造成自己的模块import numpy as np def soft_threshold(a, kappa): return np.sign(a) * np.maximum(np.abs(a) - kappa, 0.0) def admm_lasso(A, b, lam, rho1.0, max_iter1000, tol1e-6): m, n A.shape # 预分解减少每轮开销 ATA A.T A 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 更新解 (A^T A rho I) x A^T b rho(z - u) rhs A.T b rho * (z - u) x np.linalg.solve(L.T, np.linalg.solve(L, rhs)) # 两次三角回代 # z 更新软阈值 z_old z.copy() z soft_threshold(x u, lam / rho) # u 更新残差累积 u u x - z # 收敛判断原始残差和对偶残差 r_pri np.linalg.norm(x - z) s_dual np.linalg.norm(-rho * (z - z_old)) if r_pri tol and s_dual tol: print(fconverged at iter {k}) break return x这段代码跑起来非常直观。生成一份仿真数据让真实 x 只有少量非零元素加一点噪声然后观察残差曲线你会发现原始残差在前几十轮迅速下降后面进入一个缓慢逼近的阶段。这正好说明 ADMM 的收敛特点前期拆解的效果立竿见影后期主要靠乘子一点一点把约束磨平。3.3 收敛判据与停止条件工程上不能光靠设置 max_iter 来停止那样要么浪费算力要么结果不达标。我通常同时盯两个指标原始残差和对偶残差。原始残差就是 ||Ax Bz - c||反映了约束满足程度对偶残差跟相邻两轮 z 的变化量有关反映了对偶变量是否还在大幅移动。停止条件可以写成[ |r^k|2 \le \epsilon{\mathrm{abs}} \epsilon_{\mathrm{rel}} \max(|x^k|_2, |z^k|_2) ]以及类似的对偶残差条件。实际使用中ε_rel 取 1e-3 到 1e-4 是比较合理的范围。有一点要注意如果你在跑大规模问题计算范数本身也可能有通信开销这种时候可以把范数改成平方和或者用近似估计提前在每一轮里累积局部值。4. 常见问题与实战排查记录4.1 ρ 越调越乱试试残差平衡法我最早用 ADMM 时最头疼的就是 ρ。固定太小约束迟迟不满足固定太大x 和 z 又振荡。后来我读到 Boyd 那篇综述里提到的残差平衡策略实测非常有效每一轮迭代完成后比较原始残差和对偶残差如果原始残差大于对偶残差很多就把 ρ 调大一点反过来就调小一点。这个策略不需要额外的梯度信息实现成本极低。我习惯按 2 的倍数调整避免频繁变动导致迭代不稳定。在分布式场景下动态调 ρ 还有个好处它等效于动态改变乘子更新的步长相当于给算法增加了一个自适应的能力对数据分布不均的情况特别友好。4.2 非凸问题到底能不能用 ADMM理论上 ADMM 的收敛性证明多基于凸假设但现实中很多人拿它解非凸问题比如低秩矩阵分解、深度网络稀疏化。我自己试过在非凸场景下用 ADMM效果时好时坏。好的情况下收敛非常快坏的情况下卡在某个鞍点上出不来残差不降。这时候我的建议是不要依赖单一随机初始化用多个不同起点跑几轮选择最终目标函数值最小的那个结果。ADMM 在非凸问题里没有全局收敛保证但配合 warm start 和合适的正则化项依然能拿到一个工程可用的解。另外提醒一句非凸场景下的乘子更新要特别小心。有时乘子的范数会异常放大导致后续迭代数值溢出。可以在每轮更新后检查一下 y 或 u 的范数超过设定阈值就回退到上一轮或者压缩乘子的更新步长。4.3 分布式部署时怎么设计通信ADMM 天然适合分布式因为它把原问题拆成了各自独立的子问题。比如在参数服务器架构里x 子问题可以在 worker 节点本地算z 子问题和乘子更新在服务器端完成每轮只需要把 x 的汇总结果传上去、把 z 和 u 广播回来。通信量非常小瓶颈往往在本地子问题的求解速度上。我踩过的一个坑是同步策略。如果某些节点计算慢整体就会被拖累。后来在实践里改为异步更新也就是每轮允许节点在本地迭代多次再汇报一次结果服务器端做一次近似更新。这个做法不是标准 ADMM收敛性没有严格保证但在工程上经常能显著提升吞吐量。如果你的场景对收敛性有硬要求还是建议做同步版本但给每个节点分配均衡的计算量。4.4 跟其他常见算法怎么选型很多人会问ADMM、近端梯度法、原始对偶法到底选哪个我的经验是分场景来看。近端梯度法实现最简单适合单机小规模、f 光滑且梯度便宜的情况收敛速度依赖 Lipschitz 常数的估计。原始对偶法比如 Chambolle-Pock在处理鞍点问题时很有优势但需要调两个步长参数。ADMM 的优势在可分离结构明显、或者需要分布式部署时最突出缺点是参数 ρ 需要一些调参经验而且每轮迭代的开销不一定比梯度法便宜。下面的表是我在项目里常用的选型参考场景推荐方法理由单机小样本、f 光滑近端梯度法实现成本低调参简单大规模 L1/L2 正则ADMM子问题有闭式解收敛稳定分布式数据并行ADMM通信量小天然解耦非光滑且强对偶场景原始对偶法理论性质好不容易振荡4.5 初始化与预处理的两个小技巧最后分享两个我实际项目里很受用的小技巧。第一初始化尽量不要用零向量尤其是在高维稀疏场景。一个简单的 warm start 是用近端梯度法先跑几十轮把得到的解作为 ADMM 的初始点这样经常能把迭代次数砍掉一半以上。第二对 A 做列归一化。ADMM 的收敛速度对 A 的条件数比较敏感归一化之后 ρ 的取值会更稳定不太容易出现换一份数据就要重新调一遍 ρ的情况。我曾在同一套代码里只加了归一化就把收敛所需的迭代数降了大约 40%。说到底ADMM 是个很耐用的工具箱但想让它在实战里跑得又快又稳还是离不开对问题结构的理解和对残差曲线的耐心观察。参数调来调去最终靠的都是经验积累希望这篇文章能帮你少走一些弯路。本文还有配套的精品资源点击获取