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

简介交替方向乘子法ADMM是一套面向算法初学者的Matlab实现资源讲解如何将复杂的分布式优化问题拆解为可迭代求解的子问题并给出了完整的代码示例涵盖从目标函数建模、约束处理到迭代收敛判断的关键环节。资源共包含2个m文件分别为入口主程序与核心算法脚本压缩包整体仅2KB体积极小、代码精简但结构清晰便于在MATLAB中逐行阅读、调试并观察中间结果。已有1565人学习下载在同类入门代码中关注度不低。通过该资源读者可以了解ADMM的基本迭代格式、参数设定技巧、如何调用quadprog求解二次规划子问题还能对比不同参数下收敛速度的变化并延伸至图像去噪、矩阵分解等经典应用适合正在学习凸优化或想快速上手交替方向乘子法的新手作为课程作业或科研入门的起点。 ADMMAlternating 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^{k1} argmin_x ( f(x) (ρ/2)||Ax Bz^k - c u^k||^2 )第二步固定新得到的 x 和旧的 y关于 z 最小化 L_ρz^{k1} argmin_z ( g(z) (ρ/2)||Ax^{k1} Bz - c u^k||^2 )第三步更新对偶变量 yy^{k1} y^k ρ(Ax^{k1} Bz^{k1} - c)很多资料会把 y 缩放成 u y/ρ写成“缩放形式”那只是变量替换本质和这里写的一样。注意 x 更新用的是 z^k而 z 更新用的是 x^{k1}这种“先用最新值”的交替模式正是“交替方向”这个名称的由来。所以每次迭代的核心逻辑就是先让 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||^2g(z) λ||z||_1A 是原数据矩阵B -Ic 0。把一个带不可导正则项的“硬骨头”拆成了一个二次函数优化问题和软阈值问题。3.2 x-子问题和z-子问题的闭式解拆完之后两个子问题都有解析解这也是这个例子迷人的地方。x 更新忽略常数项需要解min (1/2)||Ax - b||^2 (ρ/2)||x - z^k u^k||^2对 x 求梯度并令其等于零得到x^{k1} (A^T A ρI)^{-1}(A^T b ρ(z^k - u^k))注意这里 A^T A ρI 是正定矩阵所以这个式子一定有解。如果数据维度不是特别大可以直接做 Cholesky 分解或矩阵求逆如果维度很大还可以用共轭梯度法等迭代求解器把整个矩阵算出来没必要。z 更新此时其他项视为常数z 要做的事情是min λ||z||_1 (ρ/2)||x^{k1} - z u^k||^2这个问题的闭式解就是软阈值算子z^{k1} S_{λ/ρ}(x^{k1} u^k)其中 S_κ(v) sign(v) * max(|v| - κ, 0)含义是绝对值大于 κ 的项向零收缩 κ绝对值小于等于 κ 的项直接置零。整个过程就是“把向量每个分量往零方向推一下”实现极其简单。y 更新或 u 更新u^{k1} u^k x^{k1} - z^{k1}。整个迭代过程不需要计算 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, rho1.0, max_iter1000, tol1e-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迭代 {k1} 次收敛原始残差 {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-4tol_dual 1e-4然后循环里判断两个残差都小于阈值就退出。我自己的习惯是打印出每轮残差曲线肉眼看一下下降趋势再结合自动判据双保险。4.2 ρ怎么调自适应策略和实际经验ρ 是 ADMM 里最重要的超参数它控制步长和惩罚强度。ρ 太小约束惩罚太弱原始残差下降很慢甚至不收敛ρ 太大约束满足得很快但对偶变量的更新幅度也随之变大会导致数值震荡甚至发散。我踩过一次大坑当时把一个图像去模糊问题直接套示例代码ρ 默认值设成 0.01结果跑了 500 轮还没收敛损失函数一直在高位震荡。后来把 ρ 调到 1.060 轮就收敛了。那之后我养成了习惯拿到新问题先把 ρ 从 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 轮才做一次自适应更新。符号含义常用取值ρ惩罚参数0.1 ~ 10先扫几轮定数量级ε_abs绝对停机阈值1e-6 ~ 1e-4ε_rel相对停机阈值1e-4 ~ 1e-3α松弛参数可选1.0 ~ 1.85. 常见问题与踩坑实录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 轮一次总耗时直接砍半而收敛精度只损失了一点点。问题现象可能原因排查建议残差不下降子问题求解精度不够提高内循环精度检查是否无闭式解残差震荡ρ 过大或过小重新扫描 ρ或启用自适应策略对偶残差很大ρ 过大调小 ρ增加自适应调整频率原始残差很大ρ 过小调大 ρ或延长迭代次数收敛后结果不理想问题建模或停机阈值设置不当检查约束形式是否匹配标准 ADMM 范式5.4 关于大规模问题的扩展经验ADMM 不是万能药但它在大规模场景下的表现确实值得专门说一句。我在实际项目里处理过特征维度在几十万到百万级别的稀疏优化问题传统内点法根本算不动但用 ADMM 配合稀疏矩阵存储内存占用一下子就降下来了。而且因为每个子问题的规模被拆得很小你甚至可以在单机上用多线程并行处理不同的子问题效果非常明显。不过要注意的是ADMM 的收敛速度在最坏情况下是 O(1/k)这个收敛阶不算快。如果你的问题规模不大、对精度要求又特别高其他二阶算法可能更合适。ADMM 的优势在于“快速得到一个足够好的解”而不是追求极致精度这一点在选型时要想清楚。一些感想在实际使用 ADMM 之前我一度觉得这只是一个“听起来很高级但好像用不上”的优化理论。直到自己动手拆了几个问题之后才真正体会它为什么受欢迎它不要求你有特别高深的优化理论功底只要你把目标函数拆成两块再把约束写清楚剩下的工作就是反复求解两个“看起来眼熟”的简单问题。对工程师来说这种“把复杂变简单”的能力比任何花哨的数学技巧都更有价值。如果你手头正好有一个难啃的约束优化问题试试 ADMM可能这就是最后一根撬动它的杠杆。本文还有配套的精品资源点击获取