Golden ratio primal-dual algorithm with linesearch
From MaRDI portal
Abstract: Golden ratio primal-dual algorithm (GRPDA) is a new variant of the classical Arrow-Hurwicz method for solving structured convex optimization problem, in which the objective function consists of the sum of two closed proper convex functions, one of which involves a composition with a linear transform. In this paper, we propose a linesearch strategy for GRPDA, which not only does not require the spectral norm of the linear transform but also allows adaptive and potentially much larger stepsizes. Within each linesearch step, only the dual variable needs to be updated, and it is thus quite cheap and does not require any extra matrix-vector multiplications for many special yet important applications, e.g., regularized least squares problem. Global convergence and ergodic convergence rate results measured by the primal-dual gap function are established, where denotes the iteration counter. When one of the component functions is strongly convex, faster ergodic convergence rate results are established by adaptively choosing some algorithmic parameters. Moreover, when both component functions are strongly convex, nonergodic linear converge results are established. Numerical experiments on matrix game and LASSO problems illustrate the effectiveness of the proposed linesearch strategy.
Recommendations
- A golden ratio primal-dual algorithm for structured convex optimization
- scientific article; zbMATH DE number 7668280
- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- A new primal-dual algorithm for structured convex optimization involving a Lipschitzian term
- A first-order primal-dual algorithm with linesearch
Cites work
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- 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 golden ratio primal-dual algorithm for structured convex optimization
- A low patch-rank interpretation of texture
- A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Characterization of metric regularity of subdifferentials
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convergence rates with inexact non-expansive operators
- Convex Analysis
- Error bounds, quadratic growth, and linear convergence of proximal methods
- First-order methods in optimization
- Fixed-Point Continuation Applied to Compressed Sensing: Implementation and Numerical Experiments
- Golden ratio algorithms for variational inequalities
- Handbook of robust low-rank and sparse matrix decomposition. Applications in image and video processing
- scientific article; zbMATH DE number 3148887 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- On the convergence of primal-dual hybrid gradient algorithm
- 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
- 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
(30)- A golden ratio primal-dual algorithm for structured convex optimization
- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- A new primal-dual algorithm for structured convex optimization involving a Lipschitzian term
- scientific article; zbMATH DE number 7668280 (Why is no real title available?)
- Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM
- Two subgradient extragradient methods based on the golden ratio technique for solving variational inequality 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
- The golden ratio primal-dual algorithm with two new stepsize rules for convex-concave saddle point problems
- A separate preconditioned primal-dual splitting algorithm for composite monotone inclusion problems
- A hybrid accelerated derivative-free projection method for solving nonlinear equations
- New primal-dual algorithm for convex-concave saddle point problems
- Approximate subgradient extragradient methods for solving variational inequality problems: convergence analysis and applications in signal and image processing
- 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
- Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient
- 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
- An inexact symmetric proximal ADMM with convex combination proximal centers for separable convex programming
- A survey of iterative methods for approximating solutions to variational inequality problems
- Preconditioned golden ratio primal-dual algorithm with linesearch
- Generalized asymmetric forward-backward-adjoint algorithms for convex-concave saddle-point problem
- 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
- 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.
- A primal-dual algorithm with coupled extrapolation: bridging the Chambolle-Pock and Peaceman-Rachford methods
This page was built for publication: Golden ratio primal-dual algorithm with linesearch
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093645)
