Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods.
The convergence rate bound provided in @cite_14 coincides with the bound provided in Corollary . The rate bound in @cite_14 holds for ADMM applied to Euclidean quadratic problems with linear inequality constraints. We generalize these results, using a different machinery, to arbitrary real Hilbert spaces (also infinite dimensional), to both Douglas-Rachford splitting and ADMM, to general smooth and strongly convex functions @math , and, perhaps most importantly, to any proper, closed, and convex function @math .
@cite_14
2037603831
The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm parameters that minimize the convergence factor of the ADMM iterates in the context of l 2 -regularized minimization and constrained quadratic programming. Numerical examples show that our parameter selection rules significantly outperform existing alternatives in the literature.