论文标题
乘数交替方向方法的确切最坏情况的收敛速率
The exact worst-case convergence rate of the alternating direction method of multipliers
论文作者
论文摘要
最近，半决赛编程性能估计已被用作一阶方法的最坏情况性能分析的强大工具。在本文中，我们通过使用绩效估计来得出新的非共性收敛速率（ADMM）。我们举例说明了给定边界的精确性。我们还研究了ADMM的线性和R线性收敛。我们确定，当且仅当双重目标满足强大凸性的情况下，ADMM享有全球线性收敛速率。此外，我们给出了线性收敛速率因子的明确公式。此外，我们研究了在两个新场景下ADMM的R线性收敛。
Recently, semidefinite programming performance estimation has been employed as a strong tool for the worst-case performance analysis of first order methods. In this paper, we derive new non-ergodic convergence rates for the alternating direction method of multipliers (ADMM) by using performance estimation. We give some examples which show the exactness of the given bounds. We also study the linear and R-linear convergence of ADMM. We establish that ADMM enjoys a global linear convergence rate if and only if the dual objective satisfies the Polyak-Lojasiewicz (PL)inequality in the presence of strong convexity. In addition, we give an explicit formula for the linear convergence rate factor. Moreover, we study the R-linear convergence of ADMM under two new scenarios.
