Primal-Dual Splitting Algorithm for Solving Inclusions with Mixtures of Composite, Lipschitzian, and Parallel-Sum Type Monotone Operators

By Patrick L. Combettes, Jean-Christophe Pesquet. Set-Valued and Variational Analysis, 2011

430 citations recorded by the source corpus.

We propose a primal-dual splitting algorithm for solving monotone inclusions involving a mixture of sums, linear compositions, and parallel sums of set-valued and Lipschitzian operators. An important feature of the algorithm is that the Lipschitzian operators present in the formulation can be processed individually via explicit steps, while the set-valued operators are processed individually via their resolvents. In addition, the algorithm is highly parallel in that most of its steps can be executed simultaneously. This work brings together and notably extends various types of structured monotone inclusion problems and their solution methods. The application to convex minimization problems is given special attention.

Subfields: Computational Theory and Mathematics, Control and Systems Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/a4716765582fb614957df79dede4173608c86a30

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 Control and Systems Engineering

In Numerical Analysis

Citations in the corpus

A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator (2016, methodology): “When all three terms are present, the problem was firstly considered in [10] using a forward–backward–forward scheme, where two gradient evaluations and four linear operators are needed in one iteration.”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, methodology): “…optimisation algorithms that can be massively parallelised, for example the generalised forward backward algorithm (Raguet et al. 2013), the parallel proximal algorithms (Combettes and Pesquet 2008; Pesquet and Pustelnik 2012), and the parallel primal-dual algorithm (Combettes and Pesquet 2012).”
A Primer on Monotone Operator Methods (2015, neutral): “which we call the Combettes-Pesquet method [35].”
A Generalized Forward-Backward Splitting (2011, neutral): “Algorithm 3 Iterations of Primal-Dual Algorithm of [26].”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, methodology): “…optimisation algorithms that can be massively parallelised, for example the generalised forward backward algorithm (Raguet et al. 2013), the parallel proximal algorithms (Com-bettes and Pesquet 2008; Pesquet and Pustelnik 2012), and the parallel primal–dual algorithm (Combettes and Pesquet 2012).”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, methodology): “This selected overview of proximal splitting methods is by no way exhaustive; for instance, we did not cover the forward–backward–forward splitting method and its applications [27,91,97] [25, section 26.6], or Dykstra-like algorithms [98, 99] [25, section 30.2].”
Inertial Douglas-Rachford splitting for monotone inclusion problems (2014, methodology): “ormly convex, then (p 1;n;p 2;1;n;:::;p 2;m;n) n1 and (z 1;n;z 2;1;n;:::;z 2;m;n) n1 converge strongly to the unique primal-dual solution (p 1;p 2;1;:::;p 2;m) to Problem 14. We refer the reader to [15,21] for qualication conditions which guarantee that the inclusion in (44) holds. Finally, let us m”
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (2013, background): “Since then a rich literature has developed around ADMM and related methods [21, 24, 30, 32, 34, 36, 38, 39, 46, 50].”
Convergence Rate Analysis of Several Splitting Schemes (2014, methodology): “Note that Theorem 8 implies the same lower bound for the Forward-Douglas-Rachford splitting algorithm [13] and the many primal-dual operator-splitting schemes [21, 23, 53, 14, 7, 8, 19, 6, 20, 16] (this list is not exhaustive) that contain Chambolle and Pock’s algorithm [16] as a special case becaus”