Golden ratio primal-dual algorithm with linesearch
From MaRDI portal
Publication:5093645
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
- scientific article; zbMATH DE number 3148887 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization
- 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 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
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the convergence of primal-dual hybrid gradient algorithm
- 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
(8)- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- Two subgradient extragradient methods based on the golden ratio technique for solving variational inequality problems
- 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
- A new primal-dual algorithm for structured convex optimization involving a Lipschitzian term
- A golden ratio primal-dual algorithm for structured convex optimization
- 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
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)
