Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems

DOI10.1137/21m1451944arXiv2109.14212MaRDI QIDQ6161309

Unnamed Author, Mingyi Hong, Junyu Zhang, Shu-Zhong Zhang

Publication date: 27 June 2023

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

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

zbMATH Keywords

primal-dual method; first-order method; saddle point problem; iteration complexity; affine constraints; multi-block problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C25: Convex programming

90C47: Minimax problems in mathematical programming

90C30: Nonlinear programming

Related Items

A unified primal-dual algorithm framework for inequality constrained problems

Cites Work

• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
• On the linear convergence of the alternating direction method of multipliers
• The subgradient extragradient method for solving variational inequalities in Hilbert space
• Solving strongly monotone variational and quasi-variational inequalities
• Dual extrapolation and its applications to solving variational inequalities and related problems
• On the sublinear convergence rate of multi-block ADMM
• A first-order primal-dual algorithm for convex problems with applications to imaging
• On the convergence analysis of the alternating direction method of multipliers with three blocks
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Randomized primal-dual proximal block coordinate updates
• On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function
• On the global and linear convergence of the generalized alternating direction method of multipliers
• Convexified modularity maximization for degree-corrected stochastic block models
• Dynamic programming and suboptimal control: a survey from ADP to MPC
• On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
• A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block
• DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Convergence Rate of $\mathcal{O}(1/k)$ for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point Problems
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• Optimal Primal-Dual Methods for a Class of Saddle Point Problems
• Iteration-Complexity of Block-Decomposition Algorithms and the Alternating Direction Method of Multipliers
• Design of Optimal Sparse Feedback Gains via the Alternating Direction Method of Multipliers
• Algorithmic Game Theory
• On the Global Linear Convergence of the ADMM with MultiBlock Variables
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent