Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM
From MaRDI portal
Publication:6158982
DOI10.1007/S10915-023-02105-9zbMATH Open1519.90259arXiv2301.02984OpenAlexW4318828200MaRDI QIDQ6158982FDOQ6158982
Authors: Yumin Ma, Xing-Ju Cai, Bo Jiang, Deren Han 
Publication date: 20 June 2023
Published in: Journal of Scientific Computing (Search for Journal in Brave)
Abstract: The primal-dual hybrid gradient (PDHG) algorithm is popular in solving min-max problems which are being widely used in a variety of areas. To improve the applicability and efficiency of PDHG for different application scenarios, we focus on the preconditioned PDHG (PrePDHG) algorithm, which is a framework covering PDHG, alternating direction method of multipliers (ADMM), and other methods. We give the optimal convergence condition of PrePDHG in the sense that the key parameters in the condition can not be further improved, which fills the theoretical gap in the-state-of-art convergence results of PrePDHG, and obtain the ergodic and non-ergodic sublinear convergence rates of PrePDHG. The theoretical analysis is achieved by establishing the equivalence between PrePDHG and indefinite proximal ADMM. Besides, we discuss various choices of the proximal matrices in PrePDHG and derive some interesting results. For example, the convergence condition of diagonal PrePDHG is improved to be tight, the dual stepsize of the balanced augmented Lagrangian method can be enlarged to from , and a balanced augmented Lagrangian method with symmetric Gauss-Seidel iterations is also explored. Numerical results on the matrix game, projection onto the Birkhoff polytope, earth mover's distance, and CT reconstruction verify the effectiveness and superiority of PrePDHG.
Full work available at URL: https://arxiv.org/abs/2301.02984
Recommendations
- Precompact convergence of the nonconvex primal-dual hybrid gradient algorithm
- On the convergence of primal-dual hybrid gradient algorithm
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- An algorithmic framework of generalized primal-dual hybrid gradient methods for saddle point problems
- General Inexact Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems and Convergence Analysis
Convex programming (90C25) Minimax problems in mathematical programming (90C47) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Cites Work
- Nonlinear total variation based noise removal algorithms
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Title not available (Why is that?)
- A Singular Value Thresholding Algorithm for Matrix Completion
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- On the convergence of primal-dual hybrid gradient algorithm
- A primal-dual hybrid gradient method for nonlinear operators with applications to MRI
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Bregman three-operator splitting methods
- Moreau's decomposition in Banach spaces
- Inexact first-order primal-dual algorithms
- A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems
- An improved first-order primal-dual algorithm with a new correction step
- A first-order primal-dual algorithm with linesearch
- A parallel method for earth mover's distance
- Optimally linearizing the alternating direction method of multipliers for convex programming
- \(L_p\)-norm regularization algorithms for optimization over permutation matrices
- AIR tools II: algebraic iterative reconstruction methods, improved implementation
- On quasi-Newton forward-backward splitting: proximal calculus and convergence
- The indefinite proximal point algorithms for maximal monotone operators
- A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting
- A unified algorithmic framework of symmetric Gauss-Seidel decomposition based proximal ADMMs for convex composite programming
- A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
- A survey on some recent developments of alternating direction method of multipliers
- The developments of proximal point algorithms
- Golden ratio primal-dual algorithm with linesearch
- Approximate first-order primal-dual algorithms for saddle point problems
- On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
- A generalized primal-dual algorithm with improved convergence condition for saddle point problems
- Split-Douglas-Rachford algorithm for composite monotone inclusions and split-ADMM
- Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes
- Majorized iPADMM for Nonseparable Convex Minimization Models with Quadratic Coupling Terms
Cited In (3)
This page was built for publication: Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6158982)
