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.
In @cite_25 , the authors show that if the @math parameter is small enough and if @math is a quadratic function, then Douglas-Rachford splitting is equivalent to a gradient method applied to a smooth convex function named the Douglas-Rachford envelope. Convergence rate estimates then follow from the gradient method rate estimates. Also, accelerated variants of Douglas-Rachford splitting are proposed, based on fast gradient methods. In Figure , we compare to the rate bound of the fast Douglas-Rachford splitting in [Theorem 6] Panos_acc_DR_2014 when applied to the dual. This rate bound is better than the rate bound for standard Douglas-Rachford splitting in [Theorem 4] Panos_acc_DR_2014 . We note that Corollary gives better rate bounds.
@cite_25
2951090613
We propose a new approach for analyzing convergence of the Douglas-Rachford splitting method for solving convex composite optimization problems. The approach is based on a continuously differentiable function, the Douglas-Rachford Envelope (DRE), whose stationary points correspond to the solutions of the original (possibly nonsmooth) problem. By proving the equivalence between the Douglas-Rachford splitting method and a scaled gradient method applied to the DRE, results from smooth unconstrained optimization are employed to analyze convergence properties of DRS, to tune the method and to derive an accelerated version of it.