The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
复制标题
ADMM对于多块凸最小化问题的直接扩展并不一定收敛
DOI：
10.1007/s10107-014-0826-5
复制
发表时间：
2016-01-01
影响因子：
2.7
通讯作者：
Yuan, Xiaoming
中科院分区：
文献类型：
--
作者：
Chen, Caihua;He, Bingsheng;Yuan, Xiaoming
乘子交替方向法（ADMM）现已广泛应用于许多领域，并且在两个变量块交替更新时证明了其收敛性。将 ADMM 直接扩展到多块凸最小化问题的情况是非常理想且具有实际价值的，其中其目标函数是两个以上可分离凸函数的总和。然而，这种扩展的收敛性长期以来一直缺失——文献中既没有肯定的收敛性证明，也没有显示其发散性的例子。在本文中，我们对这个长期悬而未决的问题给出了否定的答案：ADMM 的直接扩展不一定收敛。我们给出了保证ADMM直接推广收敛的充分条件，并举例说明了其发散性。
The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend the ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of more than two separable convex functions. However, the convergence of this extension has been missing for a long time-neither an affirmative convergence proof nor an example showing its divergence is known in the literature. In this paper we give a negative answer to this long-standing open question: The direct extension of ADMM is not necessarily convergent. We present a sufficient condition to ensure the convergence of the direct extension of ADMM, and give an example to show its divergence.