Golden ratio primal-dual algorithm with linesearch

DOI10.1137/21M1420319zbMATH Open1496.90053arXiv2105.07108OpenAlexW4294106839MaRDI QIDQ5093645FDOQ5093645

Authors: Xiaokai Chang, Junfeng Yang, Hongchao Zhang 

Publication date: 29 July 2022

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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 $calO(1/N)$ ergodic convergence rate results measured by the primal-dual gap function are established, where $N$ denotes the iteration counter. When one of the component functions is strongly convex, faster $calO(1/N^2)$ 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.

Full work available at URL: https://arxiv.org/abs/2105.07108

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

zbMATH Keywords

accelerationsaddle point problemlinear convergencelinesearchergodic sublinear convergencegolden ratio primal-dual algorithm

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Complexity and performance of numerical algorithms (65Y20)

Cites Work

• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Title not available (Why is that?)
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• First-order methods in optimization
• Convex Analysis
• Handbook of robust low-rank and sparse matrix decomposition. Applications in image and video processing
• Subgradient methods for saddle-point problems
• 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
• Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
• Projection methods for variational inequalities with application to the traffic assignment problem
• 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
• Title not available (Why is that?)
• Fixed-Point Continuation Applied to Compressed Sensing: Implementation and Numerical Experiments
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Convergence rates with inexact non-expansive operators
• Characterization of metric regularity of subdifferentials
• A first-order primal-dual algorithm with linesearch
• Error bounds, quadratic growth, and linear convergence of proximal methods
• A low patch-rank interpretation of texture
• Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
• A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization
• A golden ratio primal-dual algorithm for structured convex optimization
• Golden ratio algorithms for variational inequalities
• Acceleration of primal-dual methods by preconditioning and simple subproblem procedures

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
• Title not available (Why is that?)
• 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)