Optimally linearizing the alternating direction method of multipliers for convex programming
Optimally linearizing the alternating direction method of multipliers for convex programming
复制标题
凸规划乘法器交替方向法的最优线性化
DOI：
10.1007/s10589-019-00152-3
复制
发表时间：
2020
影响因子：
2.2
通讯作者：
Yuan Xiaoming
中科院分区：
文献类型：
--
作者：
He Bingsheng;Ma Feng;Yuan Xiaoming
交替方向乘法器（ADMM）被广泛应用于各种领域，其针对不同应用场景的不同变体也在文献中得到了深入研究。其中，线性ADMM由于其效率高、易于实现而受到广泛关注。为了从理论上保证线性化ADMM的收敛性，线性化子问题的步长或线性化参数的倒数应该足够小。另一方面，小的步长在数值上减慢收敛。因此，它是有趣的探索的最佳（最大）值的步长，保证收敛的线性ADMM。这种分析在文献中是缺乏的。在本文中，我们提供了一个严格的数学分析，找到这个最佳步长的线性ADMM，并相应地建立了最佳版本的线性ADMM的凸规划的背景下。证明了线性化ADMM最优解的全局收敛性和最坏情况下的收敛速度。
The alternating direction method of multipliers (ADMM) is being widely used in a variety of areas; its different variants tailored for different application scenarios have also been deeply researched in the literature. Among them, the linearized ADMM has received particularly wide attention in many areas because of its efficiency and easy implementation. To theoretically guarantee convergence of the linearized ADMM, the step size for the linearized subproblems, or the reciprocal of the linearization parameter, should be sufficiently small. On the other hand, small step sizes decelerate the convergence numerically. Hence, it is interesting to probe the optimal (largest) value of the step size that guarantees convergence of the linearized ADMM. This analysis is lacked in the literature. In this paper, we provide a rigorous mathematical analysis for finding this optimal step size of the linearized ADMM and accordingly set up the optimal version of the linearized ADMM in the convex programming context. The global convergence and worst-case convergence rate measured by the iteration complexity of the optimal version of linearized ADMM are proved as well.