Accelerating Block-Decomposition First-Order Methods for Solving Composite Saddle-Point and Two-Player Nash Equilibrium Problems

DOI10.1137/130943649zbMath1326.90107OpenAlexW2113940215MaRDI QIDQ3451761

Renato D. C. Monteiro, Yunlong He

Publication date: 18 November 2015

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

Full work available at URL: https://semanticscholar.org/paper/751a8d02b34fa5b8ac8ab54e47a2fa969a752a7f

zbMATH Keywords

complexityNash equilibriumsaddle pointmonotone variational inequalityblock decompositionaccelerated methodhybrid proximal-extragradient

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Variational and other types of inequalities involving nonlinear operators (general) (47J20) Numerical optimization and variational techniques (65K10) Monotone operators and generalizations (47H05) Applications of game theory (91A80)

Related Items

Iteration Complexity of an Inner Accelerated Inexact Proximal Augmented Lagrangian Method Based on the Classical Lagrangian Function, The saddle point problem of polynomials, An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems, An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems, Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games, Improved Pointwise Iteration-Complexity of A Regularized ADMM and of a Regularized Non-Euclidean HPE Framework, Analysis and Numerical Solution of a Modular Convex Nash Equilibrium Problem, Inexact Cuts in Stochastic Dual Dynamic Programming Applied to Multistage Stochastic Nondifferentiable Problems, Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators, A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems, On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM, Saddle points of rational functions, Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs

Uses Software

• 2EBD-HPE

Cites Work

• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Gradient methods for minimizing composite functions
• Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
• Dual extrapolation and its applications to solving variational inequalities and related problems
• A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
• Epsilon-proximal decomposition method
• A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems
• A family of projective splitting methods for the sum of two maximal monotone operators
• On the maximal monotonicity of subdifferential mappings
• An Inexact Hybrid Generalized Proximal Point Algorithm and Some New Results on the Theory of Bregman Functions
• A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS^*
• A Singular Value Thresholding Algorithm for Matrix Completion
• On the Complexity of the Hybrid Proximal Extragradient Method for the Iterates and the Ergodic Mean
• Complexity of Variants of Tseng's Modified F-B Splitting and Korpelevich's Methods for Hemivariational Inequalities with Applications to Saddle-point and Convex Optimization Problems
• General Projective Splitting Methods for Sums of Maximal Monotone Operators
• Monotone Operators and the Proximal Point Algorithm
• 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 class of decomposition methods for convex optimization and monotone variational inclusions via the hybrid inexact proximal point framework
• A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
• Iteration-Complexity of Block-Decomposition Algorithms and the Alternating Direction Method of Multipliers