CONVERGENCE ANALYSIS OF ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR A FAMILY OF NONCONVEX PROBLEMS
CONVERGENCE ANALYSIS OF ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR A FAMILY OF NONCONVEX PROBLEMS
复制标题
DOI：
10.1137/140990309
复制
发表时间：
2016-01-01
影响因子：
3.1
通讯作者：
Razaviyayn, Meisam
中科院分区：
文献类型：
--
作者：
Hong, Mingyi;Luo, Zhi-Quan;Razaviyayn, Meisam
在许多工程领域，乘数的交替方向方法（ADMM）被广泛用于求解大规模约束优化问题，即凸或非convex。但是，当目标函数是非convex时，人们普遍缺乏对算法的理论理解。在本文中，我们分析了ADMM的融合，以解决某些非概念共识并共享问题。我们表明，如果选择增强的拉格朗日式的罚款参数，则经典的ADMM会收敛于固定解决方案集。对于共享问题，我们表明，无论可变块的数量如何，ADMM都是收敛的。我们的分析没有对算法生成的迭代物施加任何假设，并且广泛适用于许多涉及近端更新规则和各种灵活块选择规则的ADMM变体。
The alternating direction method of multipliers (ADMM) is widely used to solve large-scale linearly constrained optimization problems, convex or nonconvex, in many engineering fields. However there is a general lack of theoretical understanding of the algorithm when the objective function is nonconvex. In this paper we analyze the convergence of the ADMM for solving certain nonconvex consensus and sharing problems. We show that the classical ADMM converges to the set of stationary solutions, provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. For the sharing problems, we show that the ADMM is convergent regardless of the number of variable blocks. Our analysis does not impose any assumptions on the iterates generated by the algorithm and is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.