Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality

DOI10.1137/21m1462428zbMath1523.49028arXiv2110.11210MaRDI QIDQ6076865

Ioannis Tsaknakis, Shu-Zhong Zhang, Mingyi Hong

Publication date: 17 October 2023

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

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

zbMATH Keywords

computational complexity; duality theory; coupled constraints; min-max problem; max-min inequality

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C47: Minimax problems in mathematical programming

49N15: Duality theory (optimization)

49K35: Optimality conditions for minimax problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lectures on convex optimization
• Bilevel programming: a survey
• Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions
• Generalized Nash equilibrium problem, variational inequality and quasiconvexity
• Quadratic programming with one negative eigenvalue is NP-hard
• Geometric algorithms and combinatorial optimization
• Multi-level decision making. Models, methods and applications
• Bilevel optimization. Advances and next challenges
• Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games
• On solving simple bilevel programs with a nonconvex lower level program
• Note on noncooperative convex games
• Penalty Methods for the Solution of Generalized Nash Equilibrium Problems
• On the solution of the KKT conditions of generalized Nash equilibrium problems
• A Generalized Iterative Water-Filling Algorithm for Distributed Power Control in the Presence of a Jammer
• Optimality conditions for bilevel programming problems
• On a theorem of Danskin with an application to a theorem of Von Neumann-Sion
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Convergence Rate of $\mathcal{O}(1/k)$ for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point Problems
• Mathematical Programs with Optimization Problems in the Constraints
• A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Generalized Nash equilibrium problems