A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems

DOI10.1137/18M1213488OpenAlexW3161273445MaRDI QIDQ4989936

Necdet Serhat Aybat, Erfan Yazdandoost Hamedani

Publication date: 27 May 2021

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

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

zbMATH Keywords

primal-dual methodconvex programmingconvergence ratefirst-order methodsaddle point problemline search

Mathematics Subject Classification ID

Convex programming (90C25) Numerical methods involving duality (49M29) Numerical optimization and variational techniques (65K10) Complexity and performance of numerical algorithms (65Y20)

Related Items (24)

Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method ⋮ New Primal-Dual Algorithms for a Class of Nonsmooth and Nonlinear Convex-Concave Minimax Problems ⋮ On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming ⋮ Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs ⋮ A stochastic primal-dual method for a class of nonconvex constrained optimization ⋮ Two Steps at a Time---Taking GAN Training in Stride with Tseng's Method ⋮ First-Order Methods for Problems with $O$(1) Functional Constraints Can Have Almost the Same Convergence Rate as for Unconstrained Problems ⋮ A unified primal-dual algorithm framework for inequality constrained problems ⋮ Cyclic Coordinate Dual Averaging with Extrapolation ⋮ A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems ⋮ A stochastic variance reduction algorithm with Bregman distances for structured composite problems ⋮ Robust Accelerated Primal-Dual Methods for Computing Saddle Points ⋮ Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems ⋮ Bregman-Golden ratio algorithms for variational inequalities ⋮ An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function ⋮ Alternating Proximal-Gradient Steps for (Stochastic) Nonconvex-Concave Minimax Problems ⋮ An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems ⋮ Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games ⋮ An accelerated forward-backward-half forward splitting algorithm for monotone inclusion with applications to image restoration ⋮ Bregman three-operator splitting methods ⋮ Primal-dual incremental gradient method for nonsmooth and convex optimization problems ⋮ Forward-reflected-backward method with variance reduction ⋮ Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization ⋮ Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints

Uses Software

• Mosek

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the ergodic convergence rates of a first-order primal-dual algorithm
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
• An Accelerated HPE-Type Algorithm for a Class of Composite Convex-Concave Saddle-Point Problems
• A Level-Set Method for Convex Optimization with a Feasible Solution Path
• Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization
• An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems
• A First-Order Primal-Dual Algorithm with Linesearch
• Proximal extrapolated gradient methods for variational inequalities
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
• A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity
• A Distributed ADMM-like Method for Resource Sharing over Time-Varying Networks
• Optimal Primal-Dual Methods for a Class of Saddle Point Problems
• Projected Reflected Gradient Methods for Monotone Variational Inequalities

This page was built for publication: A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems