On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting

DOI10.1007/s10107-018-1321-1zbMath1498.90156OpenAlexW2886903283WikidataQ102123434 ScholiaQ102123434MaRDI QIDQ2288187

Daniel O'Connor, Lieven Vandenberghe

Publication date: 17 January 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-018-1321-1

zbMATH Keywords

monotone operatorsDouglas-Rachford splittingproximal algorithmsprimal-dual algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical methods involving duality (49M29) Decomposition methods (49M27) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10)

Related Items (19)

A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems ⋮ Unified linear convergence of first-order primal-dual algorithms for saddle point problems ⋮ Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists ⋮ Nonlinear forward-backward splitting with momentum correction ⋮ Primal-dual fixed point algorithm based on adapted metric method for solving convex minimization problem with application ⋮ Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM ⋮ Resolvent of the parallel composition and the proximity operator of the infimal postcomposition ⋮ Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming ⋮ Convergence analysis of the generalized Douglas-Rachford splitting method under Hölder subregularity assumptions ⋮ Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes ⋮ Bregman three-operator splitting methods ⋮ Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator ⋮ The distance between convex sets with Minkowski sum structure: application to collision detection ⋮ Splitting with Near-Circulant Linear Systems: Applications to Total Variation CT and PET ⋮ Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates ⋮ Bregman primal-dual first-order method and application to sparse semidefinite programming ⋮ Dualize, split, randomize: toward fast nonsmooth optimization algorithms ⋮ A primal-dual flow for affine constrained convex optimization ⋮ Degenerate Preconditioned Proximal Point Algorithms

Uses Software

• UNLocBoX

Cites Work

• Unnamed Item
• On the ergodic convergence rates of a first-order primal-dual algorithm
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• Compositions and convex combinations of averaged nonexpansive operators
• Partial inverse of a monotone operator
• A three-operator splitting scheme and its optimization applications
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Tight global linear convergence rate bounds for Douglas-Rachford splitting
• A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
• Proximal Splitting Methods in Signal Processing
• Convergence Analysis of Primal-Dual Algorithms for a Saddle-Point Problem: From Contraction Perspective
• Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
• A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science
• Applications of the method of partial inverses to convex programming: Decomposition
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Monotone Operators and the Proximal Point Algorithm
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Variational Analysis
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
• Primal-Dual Decomposition by Operator Splitting and Applications to Image Deblurring
• The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions
• An introduction to continuous optimization for imaging
• Convex analysis and monotone operator theory in Hilbert spaces

This page was built for publication: On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting