A Three-Operator Splitting Scheme and its Optimization Applications

By Damek Davis, Wotao Yin. 2015

439 citations recorded by the source corpus.

Operator-splitting methods convert optimization and inclusion problems into fixed-point equations; when applied to convex optimization and monotone inclusion problems, the equations given by operator-splitting methods are often easy to solve by standard techniques. The hard part of this conversion, then, is to design nicely behaved fixed-point equations. In this paper, we design a new, and thus far, the only nicely behaved fixed-point equation for solving monotone inclusions with three operators; the equation employs resolvent and forward operators, one at a time, in succession. We show that our new equation extends the Douglas-Rachford and forward-backward equations; we prove that standard methods for solving the equation converge; and we give two accelerated methods for solving the equation.

Subfields: Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “The co-coercive condition is relatively standard in operator splitting literature [Davis and Yin, 2017, V˜u, 2013] and for variational inequalities [Zhu and Marcotte, 1996].”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, positive): “Recent work has shown that additional assumptions (involving at least one strongly convex objective function) can guarantee convergence for N = 3 with certain modifications to the algorithm [6,18, 26,27,11].”
An introduction to continuous optimization for imaging (2016, methodology): “Convergence of these algorithms under various conditions on ψ are studied in a few important papers; see in particular the papers of Eckstein (1993), Teboulle (1992), Chen and Teboulle (1993), Kiwiel (1997), Beck and Teboulle (2003) and Auslender and Teboulle (2004).”
Convergence Rate Analysis of Several Splitting Schemes (2014, methodology): “Operator-splitting schemes are iterative algorithms for solving optimization problems (and more generally PDE) [39, 52, 32, 47, 27].”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, neutral): “and if we set f = 1/g , the PD3O algorithm reverts to the Davis–Yin algorithm [92]:  G (8+ 1 2 ) = proxg 5 (B (8) ) D (8+ 1 2 ) = prox6∗/g ( ( 2G (8+ 1 2 ) − B (8) − g∇h(G (8+ 1 2 ) ) ) /g ) = (Id − proxg6) ( 2G (8+ 1 2 ) − B (8) − g∇h(G (8+ 12 ) ) ) /g B (8+1) = B (8) + d (8) ( G (8+ 1 2”
Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, neutral): “I Three-operator splitting [16], parallel variants, .”
A Primer on Monotone Operator Methods (2015, background): “Here, we briefly present Davis and Yin’s recent breakthrough [40].”
On the ergodic convergence rates of a first-order primal–dual algorithm (2016, positive): “The new proofs we propose easily incorporate additional smooth terms such as considered in [9, 31] (where convergence is already been proved, without rates), and [4] (where the proofs of [5] are extended to the framework of [31] which considers general monotone operators—in this setting one must als”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, methodology): “The Davis–Yin splitting (DYS) algorithm [12], is dedicated to this problem; that is, ﬁnd a zero of the sum of three monotone operators, one of which is cocoercive.”
Linear convergence of primal-dual gradient methods and their performance in distributed optimization (2019, methodology): “Similarly, the conditions used in [19]–[21] require the saddle-point problem (2) to be strongly-convex with respect to w and strongly-concave with respect to λ.”
A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator (2016, methodology): “Since this is a primal–dual algorithm for three functions (h l is considered as one function) and it has connections to the three-operator splitting scheme in [15], we name it as Primal–Dual Three-Operator splitting (PD3O).”