A simple algorithm for a class of nonsmooth convex-concave saddle-point problems

DOI10.1016/J.ORL.2015.02.001zbMath1408.90234OpenAlexW2071236014MaRDI QIDQ1785640

Marc Teboulle, Yoel Drori, Shoham Sabach

Publication date: 1 October 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2015.02.001

zbMATH Keywords

saddle-point problemsiteration complexitynonsmooth convex minimization

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)

Related Items (30)

On the ergodic convergence rates of a first-order primal-dual algorithm ⋮ Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators ⋮ On the information-adaptive variants of the ADMM: an iteration complexity perspective ⋮ A globally linearly convergent method for pointwise quadratically supportable convex-concave saddle point problems ⋮ Unified linear convergence of first-order primal-dual algorithms for saddle point problems ⋮ Preconditioned three-operator splitting algorithm with applications to image restoration ⋮ Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists ⋮ Some extensions of the operator splitting schemes based on Lagrangian and primal–dual: a unified proximal point analysis ⋮ Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting ⋮ A stochastic variance reduction algorithm with Bregman distances for structured composite problems ⋮ Primal-dual fixed point algorithm based on adapted metric method for solving convex minimization problem with application ⋮ No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization ⋮ A generalized forward-backward splitting operator: degenerate analysis and applications ⋮ Convergence Results for Primal-Dual Algorithms in the Presence of Adjoint Mismatch ⋮ The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis ⋮ Improved Pointwise Iteration-Complexity of A Regularized ADMM and of a Regularized Non-Euclidean HPE Framework ⋮ Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes ⋮ The Shannon total variation ⋮ Bregman three-operator splitting methods ⋮ First-order algorithms for convex optimization with nonseparable objective and coupled constraints ⋮ Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization ⋮ Nonlinear Forward-Backward Splitting with Projection Correction ⋮ An introduction to continuous optimization for imaging ⋮ On starting and stopping criteria for nested primal-dual iterations ⋮ New convergence analysis of a primal-dual algorithm with large stepsizes ⋮ A new primal-dual algorithm for minimizing the sum of three functions with a linear operator ⋮ Easily Parallelizable and Distributable Class of Algorithms for Structured Sparsity, with Optimal Acceleration ⋮ Dualize, split, randomize: toward fast nonsmooth optimization algorithms ⋮ Convergence analysis of the stochastic reflected forward-backward splitting algorithm ⋮ A nested primal-dual FISTA-like scheme for composite convex optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A proximal-based deomposition method for compositions method for convex minimization problems
• Interior projection-like methods for monotone variational inequalities
• Smoothing and First Order Methods: A Unified Framework
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
• Monotone Operators and the Proximal Point Algorithm
• Variational Analysis
• Alternating Projection-Proximal Methods for Convex Programming and 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
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Convex Optimization in Signal Processing and Communications
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
• Proximité et dualité dans un espace hilbertien
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent

This page was built for publication: A simple algorithm for a class of nonsmooth convex-concave saddle-point problems