编者按：本文介绍ADMM最基本情形的推导。通过这篇文章，你将了解ADMM算法的基本思路，收敛性分析的基本原理，和它理论上的一些局限性。

文章作者：覃含章

责任编辑：覃含章

本文的内容主要来自著名的讲义：

Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. 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版本，如果觉得有用， 请勿吝啬你的留言和赞哦！~

欢迎投稿：

投稿邮箱：hr@paperweekly.site

• 所有文章配图，请单独在附件中发送

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

文章由作者『运筹OR帷幄』原创发布，如需转载请在公众号后台获取转载须知