【优化】交替方向乘子法（ADMM）的基本原理

unityloverz · 发表于 2021-11-23 11:21

编者按：本文介绍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[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版本，如果觉得有用，请勿吝啬你的留言和赞哦！~
欢迎投稿：
投稿邮箱：operations_r@163.com
所有文章配图，请单独在附件中发送
请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

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

<hr/>扫二维码关注『运筹OR帷幄』公众号：

点击查看『运筹OR帷幄』志愿者招募介绍及加入方式：

redhat9i · 发表于 2021-11-23 11:29

最近在处理一个非凸的工程优化问题，用到了admm，觉得前期惩罚因子小一些，后期大一些，更容易找到比较好的解。相反的话，觉得会很难收敛。

RedZero9 · 发表于 2021-11-23 11:37

一个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

闲鱼技术01 · 发表于 2021-11-23 11:44

您好，我想请问一下，迭代计算的时候，拉格朗日乘子和admm步长应该初始化为多少？

jquave · 发表于 2021-11-23 11:53

调参是门手艺。。 @覃含章

xiangtingsl · 发表于 2021-11-23 12:01

太对了

XGundam05 · 发表于 2021-11-23 12:04

终止条件那里看的不是很懂，是什么？

KaaPexei · 发表于 2021-11-23 12:10

欢迎加群 @运筹OR帷幄交流~

kyuskoj · 发表于 2021-11-23 12:20

你好，最后那里惩罚因子应该不是递减的吧，是递增的吧

xiaozongpeng · 发表于 2021-11-23 12:25

@覃含章

		自动登录	找回密码
密码			立即注册

【优化】交替方向乘子法（ADMM）的基本原理

本帖子中包含更多资源