首页天道酬勤乘子交替方向法(交替方向隐格式)

乘子交替方向法(交替方向隐格式)

admin 12-04 02:29 295次浏览

编者按:本文介绍了ADMM最基本情况的推导。通过本文,您将了解ADMM算法的基本思想、收敛性分析的基本原理及其理论局限性。

作者:秦含章

编辑:秦含章

本文的内容主要来源于著名的讲义:

通过乘子的交替方向方法的分布式优化和统计学习[J]。机器学习的基础和趋势,2011,3(1): 1-122。

在开始课文之前多说几句。史蒂芬博伊德作为一名优化学家,除了自己的大量研究之外,他一生中最突出的贡献就是广泛而严谨地将优化理论引入工程领域。其中,ADMM就是一个非常重要的例子。事实上,这种方法已经被理论优化界研究了几十年(sxdds教师语言),但只是在最近几年,如Boyd,包括Stanford的叶先生等人,才“重新探索”了这方面的研究,引起了广泛的关注。

1. ADMM算法的基本形式

2. ADMM的收敛性证明思路

3. 三个不等式的证明(第一次阅读可跳过)

所以我们看到我们其实已经掌握了证明的主要思想,具体的证明其实技术上并不难,顶多代数有点绕。这也是ADMM算法分析的一般特征。我们仍然是最基本的情况,复杂情况的分析要复杂得多(主要是因为迭代过程中的各种“交替”).

4.写在最后

注意,我只给出了ADMM算法收敛到最优可行解(原变量不一定是最优的)和最优目标函数值的证明。我在这里根本没有讨论收敛速度。收敛速度在许多其他优化算法中相对容易分析,如一阶二阶算法、内点法等。然而,在ADMM的分析中,收敛速度分析确实是这一领域的一大难点。事实上,在实践中,如果你写代码运行ADMM,你会发现它不像那些梯度下降,lydh方法,而且很容易快速收敛到更高的误差精度。ADMM的实际收敛速度往往比那些算法慢得多。ADMM的主要应用主要是在解空间很大的时候(比如A和B在存储空间都是GB矩阵)。这时候很多传统的方法都不太好用,块解是强制性的,解的绝对精度往往没有那么高。当然,然后你必须祈祷原始空间上argmin迭代的形式相对简单。

你可以在这个微信官方账号的后台回复关键词:回复“ADMM”获取此参考的pdf版本。如果你觉得有用,请不要吝啬你的评论和赞美!~

欢迎投稿:

电子邮件:hr@paperweekly.site

请在附件中单独发送所有带图片的文章。

请留下您的即时联系方式(微信或手机),以便我们在编辑发布时与作者沟通。

这篇文章最初由作者“战术家”发表。如需转载,请在微信官方账号后台获取转载说明。

iOS如何实现抖音点赞功能DeepRust匹配:有更好的方法吗?C++构造析构赋值运算函数怎么应用雷士灯具管理系统
numpy是啥(numpy int) python安装numpy 教程(numpy数组倒序)
相关内容