Convergence Analysis of Primal-Dual Algorithms for a Saddle-Point Problem: From Contraction Perspective

By Bingsheng He, Xiaoming Yuan. SIAM Journal of Imaging Sciences, 2012

443 citations recorded by the source corpus.

Subfields: Computational Mechanics, Mathematical Physics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/3cbe67d197976f4e44261972fdd552e0f2b5c162

How researchers see this paper

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

In Computational Mechanics

In Mathematical Physics

In Numerical Analysis

Citations in the corpus

Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, methodology): “The Condat–Vũ algorithm has the form of a primal–dual forward–backward algorithm [12, 15, 26, 30].”
iPiano: Inertial Proximal Algorithm for Nonconvex Optimization (2014, methodology): “Among the strategies to tackle this problem are splitting approaches such as Douglas–Rachford [28, 18], several primal-dual algorithms [12, 37, 23], and forward-backward splitting [28, 16, 7, 35]; see [15] for a survey.”
Convergence results of two-step inertial proximal point algorithm (2022, methodology): “The primal-dual hybrid gradient (PDHG) method (see, for example, [18,29]) is one of the popular methods for solving problem (58) and it is a preconditioned proximal point algorithm with λ = 1 for the saddle subdifferential operator of φ given in (53) (see, [19,34]).”
Stochastic Approximations and Perturbations in Forward-Backward Splitting for Monotone Operators (2015, methodology): “Particular cases of such fixed metric primal-algorithm can be found in [12, 15, 30, 34, 35].”
Optimal Primal-Dual Methods for a Class of Saddle Point Problems (2013, background): “The study on ﬁrst-order primal-dual method for nonsmooth convex optimization has been mainly motivated by solving total variation based image processing problems (e.g. [45, 9, 37, 6, 4, 13]).”
Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems (2014, background): “Algorithm 2 also constitutes a generalization of [46]–[48] (designated by some authors as PDHG, Primal-Dual Hybrid Gradient).”
An Inertial Forward-Backward Algorithm for Monotone Inclusions (2014, methodology): “In addition, we consider a symmetric positive definite map M , which can be interpreted as a preconditioner or variable metric and is inspired by recently work on primal dual algorithms [10,22,27,42] and forward-backward splitting [11,12,14].”
On the ergodic convergence rates of a first-order primal–dual algorithm (2016, background): “First we consider the overrelaxed primal-dual Algorithm 2, whose convergence has been considered already in [14, 16].”
A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization (2014, unknown): “(12) Lemma 3 Let Assumption 5 hold true.”
A splitting algorithm for dual monotone inclusions involving cocoercive operators (2011, methodology): “Such a renorming technique was used in [22] for a minimization problem in finite-dimensional spaces.”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, background): “…that 2 < 1 and 𝜌 ( 𝑖 ) = 1 [55]. k k The convergence was proved in a diﬀerent way by He and Yuan, with a constant relaxation parameter 𝜌 ( 𝑖 ) = ∈ ( 0 , 2 and the same other hypotheses [58]; indeed, they observed that the Chambolle–Pock algorithm is a primal–dual proximal point algorithm…”