【优化】交替方向乘子法（ADMM）的基本原理
编者按：本文介绍ADMM最基本情形的推导。通过这篇文章，你将了解ADMM算法的基本思路，收敛性分析的基本原理，和它理论上的一些局限性。文章作者： @覃含章
责任编辑： @覃含章
文章发表于微信公众号【运筹OR帷幄】：【优化】交替方向乘子法（ADMM）的基本原理
欢迎原链接转发，转载请私信 @留德华叫兽 获取信息，盗版必究。
敬请关注和扩散本专栏及同名公众号，会邀请全球知名学者发布运筹学、人工智能中优化理论等相关干货、知乎Live及行业动态：『运筹OR帷幄』大数据人工智能时代的运筹学
本文的内容主要来自著名的讲义：Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 2011, 3(1): 1-122.
正文开始前多说几句。Stephen Boyd作为一名优化科学家，除了自己的很多研究，这辈子最杰出的贡献就是广泛地将优化理论严谨地介绍给了工程界。其中，ADMM就是一个很重要的例子。这个方法其实理论优化界早就研究了几十年（何炳生老师语），但是也只是到了最近几年，如Boyd包括Stanford的Yinyu Ye老师等人，才对这方面的研究进行了“再挖掘”，引起了大家的广泛注意。
1. ADMM算法的基本形式
2. ADMM的收敛性证明思路
3. 三个不等式的证明（第一次阅读可跳过）
所以我们看到其实掌握了证明的主要思路，具体证明其实没什么技术难度，顶多就是algebra稍微有点绕。这也是ADMM算法分析的一般特点，我们这还是最基本的情况，复杂情况的分析就是绕得多了（主要是因为迭代的时候各种“交替”）...
4. 写在最后
注意我这边只给出了关于ADMM算法收敛到最优可行解（原变量还不一定最优）和最优目标函数值的证明。这里我完全没有讨论收敛速率的问题。收敛速率，在很多其它优化算法里面都是比较容易分析的，像一阶二阶算法，内点法等等。但在ADMM的分析里面，收敛速率分析确实是这块领域的一大难点。事实上，实际当中你如果写代码跑ADMM会发现它不像那些梯度下降，牛顿法，很容易快速收敛到一个较高的误差精度，ADMM实际的收敛速度往往比那些算法慢得多。。ADMM的主要应用，主要是在解空间规模非常大的情况下（比如A，B都是存储空间上GB的矩阵），这个时候很多传统的方法不好用，强制需要分块求解，而且对解的绝对精度往往要求也没那么高。当然，然后你还得祈祷在primal space上argmin那个迭代的形式比较简单。。
可以在 本公众号后台 回复关键词：回复”ADMM“获得本文参考文献的pdf版本，如果觉得有用， 请勿吝啬你的留言和赞哦！~
欢迎投稿：
投稿邮箱：operations_r@163.com
所有文章配图，请单独在附件中发送
请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通
文章由作者『运筹OR帷幄』原创发布，如需转载请在公众号后台获取转载须知<hr/>扫二维码关注『运筹OR帷幄』公众号：
点击查看『运筹OR帷幄』志愿者招募介绍及加入方式：
最近在处理一个非凸的工程优化问题，用到了admm，觉得前期惩罚因子小一些，后期大一些，更容易找到比较好的解。相反的话，觉得会很难收敛。 一个note：在下列文章中，作者指出了其实这里给出的Boyd等人的分析实际上还隐含了一些更强的condition才能成立。。。
A note on the convergence of ADMM for linearly constrained convex optimization problems， Computational Optimization and Applications, March 2017, Volume 66, Issue 2, pp 327–343 您好，我想请问一下，迭代计算的时候，拉格朗日乘子和admm步长应该初始化为多少？ 调参是门手艺。。 @覃含章 太对了 终止条件那里看的不是很懂，是什么？ 欢迎加群 @运筹OR帷幄 交流~ 你好，最后那里惩罚因子应该不是递减的吧，是递增的吧 @覃含章
页:
[1]
2