Proximal splitting algorithms: Relax them all!
Authors:
Preprint
Abstract
Convex optimization problems, whose solutions live in very high dimensional spaces, have become ubiquitous. To solve them, proximal splitting algorithms are particularly adequate: they consist of simple operations, by handling the terms in the objective function separately. We present several existing proximal splitting algorithms and we derive new ones, within a unified framework, which consists in applying splitting methods for monotone inclusions, like the forward-backward algorithm, in primal-dual product spaces with well-chosen metric. This allows us to derive new convergence theorems with larger parameter ranges. In particular, when the smooth term in the objective function is quadratic, e.g. for least-squares problems, convergence is guaranteed with larger values of the relaxation parameter than previously known. Indeed, it is often the case in practice that the larger the relaxation parameter, the faster the convergence.Keywords
All Related Versions
This publication has 67 references indexed in Scilit:
- Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splittingMathematical Programming, 2019
- On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splittingMathematical Programming, 2018
- Monotone operator theory in convex optimizationMathematical Programming, 2018
- Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operatorsComputational Optimization and Applications, 2017
- Some Facts About Operator-Splitting and Alternating Direction Methods2016
- On the ergodic convergence rates of a first-order primal–dual algorithmMathematical Programming, 2015
- Bregman operator splitting with variable stepsize for total variation image reconstructionComputational Optimization and Applications, 2012
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite functionMathematical Programming, 2012
- A splitting algorithm for dual monotone inclusions involving cocoercive operatorsAdvances in Computational Mathematics, 2011
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992