A golden ratio primal-dual algorithm for structured convex optimization
From MaRDI portal
Publication:2025858
Abstract: We design, analyze and test a golden ratio primal-dual algorithm (GRPDA) for solving structured convex optimization problem, where the objective function is the sum of two closed proper convex functions, one of which involves a composition with a linear transform. GRPDA preserves all the favorable features of the classical primal-dual algorithm (PDA), i.e., the primal and the dual variables are updated in a Gauss-Seidel manner, and the per iteration cost is dominated by the evaluation of the proximal point mappings of the two component functions and two matrix-vector multiplications. Compared with the classical PDA, which takes an extrapolation step, the novelty of GRPDA is that it is constructed based on a convex combination of essentially the whole iteration trajectory. We show that GRPDA converges within a broader range of parameters than the classical PDA, provided that the reciprocal of the convex combination parameter is bounded above by the golden ratio, which explains the name of the algorithm. An O(1/N) ergodic convergence rate result is also established based on the primal-dual gap function, where N denotes the number of iterations. When either the primal or the dual problem is strongly convex, an accelerated GRPDA is constructed to improve the ergodic convergence rate from O(1/N) to O(1/N2). Moreover, we show for regularized least-squares and linear equality constrained problems that the reciprocal of the convex combination parameter can be extended from the golden ratio to 2 and meanwhile a relaxation step can be taken. Our preliminary numerical results on LASSO, nonnegative least-squares and minimax matrix game problems, with comparisons to some state-of-the-art relative algorithms, demonstrate the efficiency of the proposed algorithms.
Recommendations
- Golden ratio primal-dual algorithm with linesearch
- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- scientific article; zbMATH DE number 7668280
- A new primal-dual algorithm for structured convex optimization involving a Lipschitzian term
- Primal-dual proximal algorithms for structured convex optimization: a unifying framework
Cites work
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A first-order primal-dual algorithm with linesearch
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- A low patch-rank interpretation of texture
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Atomic decomposition by basis pursuit
- Complexity of Variants of Tseng's Modified F-B Splitting and Korpelevich's Methods for Hemivariational Inequalities with Applications to Saddle-point and Convex Optimization Problems
- Compressed sensing
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convex analysis and monotone operator theory in Hilbert spaces
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- First-order methods in optimization
- Golden ratio algorithms for variational inequalities
- Handbook of robust low-rank and sparse matrix decomposition. Applications in image and video processing
- Hankel matrix rank minimization with applications to system identification and realization
- scientific article; zbMATH DE number 3148887 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Projection methods for variational inequalities with application to the traffic assignment problem
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- Subgradient methods for saddle-point problems
Cited in
(50)- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes
- Golden Complementary Dual in Quadratic Optimization
- A new primal-dual algorithm for structured convex optimization involving a Lipschitzian term
- Golden ratio primal-dual algorithm with linesearch
- scientific article; zbMATH DE number 7668280 (Why is no real title available?)
- A golden ratio proximal alternating direction method of multipliers for separable convex optimization
- A partially inexact generalized primal-dual hybrid gradient method for saddle point problems with bilinear couplings
- Golden ratio proximal gradient ADMM for distributed composite convex optimization
- Two subgradient extragradient methods based on the golden ratio technique for solving variational inequality problems
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- An improved subgradient extragradient self-adaptive algorithm based on the golden ratio technique for variational inequality problems in Banach spaces
- A simple proximal algorithm based on the golden ratio for equilibrium problem on Hadamard manifolds
- An inexact accelerated stochastic PRSM with convex combination proximal centers for separable convex optimization
- Golden ratio algorithm with inertia for non-Lipschitz variational inequalities
- The golden ratio primal-dual algorithm with two new stepsize rules for convex-concave saddle point problems
- Convergence analysis of Bregman projection methods with a new extrapolation technique for solving variational inequalities in reflexive Banach spaces
- A separate preconditioned primal-dual splitting algorithm for composite monotone inclusion problems
- A new double inertial subgradient extragradient method for solving quasimonotone variational inequality problems
- A hybrid accelerated derivative-free projection method for solving nonlinear equations
- Approximate subgradient extragradient methods for solving variational inequality problems: convergence analysis and applications in signal and image processing
- On novel golden ratio-like techniques for solving the split feasibility problem with multiple output sets
- A golden ratio technique for equilibrium problem in reflexive Banach spaces
- A fast generalized prediction-correction dual-primal hybrid gradient algorithm for bilinear saddle point problems with applications to total variation image processing
- A splitting preconditioned primal-dual algorithm with interpolation and extrapolation for bilinear saddle point problem
- A primal-dual splitting algorithm with convex combination and larger step sizes for composite monotone inclusion problems
- A proximal-type algorithm with Bregman distance for solving equilibrium problems
- Proximal alternating direction method of multipliers with convex combination proximal centers
- An indefinite proximal Peaceman-Rachford splitting method-based algorithm integrating the generalization acceleration technique for separable convex programming problems in image restoration
- Convergence analysis of a resolvent-free method for solving inclusion problems beyond co-coercivity
- An inexact symmetric proximal ADMM with convex combination proximal centers for separable convex programming
- A symmetric version of the generalized Chambolle-Pock-He-Yuan method for saddle point problems
- A convex combined symmetric alternating direction method of multipliers for separable optimization
- A survey of iterative methods for approximating solutions to variational inequality problems
- An improved proximal primal-dual ALM-based algorithm with convex combination proximal centers for equality-constrained convex programming in basis pursuit practical problems
- Preconditioned golden ratio primal-dual algorithm with linesearch
- An accelerated mirror descent algorithm for constrained nonconvex problems
- A step-free primal-dual algorithm for solving bilinear saddle point problem
- Golden ratio type Douglas-Rachford splitting method for solving structured inverse variational inequality problems
- A family of hybrid acceleration DFPMs and applications for pseudo-monotone nonlinear equations with convex constraints
- Backward inertial modification of the Bregman golden ratio algorithm for solving variational inequalities
- Adaptive primal-dual algorithms for generic saddle point problems
- A hybrid acceleration Douglas-Rachford splitting method for solving large-scale absolute value equations
- A Tseng algorithm based on the golden ratio technique for solving variational inequality problems in Hilbert spaces.
- Two parallel golden ratio iterative algorithms for approximate solution of equilibrium problem in real Hilbert space
- A primal-dual algorithm with coupled extrapolation: bridging the Chambolle-Pock and Peaceman-Rachford methods
- Inexact golden ratio primal-dual algorithms for structured convex optimization problems
- Self-adaptive Bregman projection method based on the golden ratio technique for variational inequalities
- Convergence results for proximal-type algorithm beyond the classical golden-ratio constant for equilibrium problems
- A note on golden means, nonlinear matrix equations and structured doubling algorithms
This page was built for publication: A golden ratio primal-dual algorithm for structured convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2025858)
