Douglas-Rachford Splitting: Complexity Estimates and Accelerated Variants

Problems arising in many application areas (such as optimal control, statistics, machine learning, image and signal processing) can be cast into the form of a nonsmooth convex composite problems. Recently a lot of attention has been dedicated to the so called operator splitting methods for solving problems of this form. In this work we propose a new approach for analyzing convergence of the Douglas-Rachford splitting method (DRS), in the particular but important case where the objective contains a quadratic term. The approach is based on a continuously differentiable function, the Douglas-Rachford Envelope (DRE), whose stationary points correspond to the solution of the original (possibly nonsmooth) problem. By proving the equivalence between the Douglas-Rachford splitting and a scaled gradient method applied to the DRE, results from smooth unconstrained optimization are employed to analyze the convergence properties of DRS, to tune the method and to derive an accelerated version of it.