Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality
From MaRDI portal
Abstract: In this work we study a special minimax problem where there are linear constraints that couple both the minimization and maximization decision variables. The problem is a generalization of the traditional saddle point problem (which does not have the coupling constraint), and it finds applications in wireless communication, game theory, transportation, just to name a few. We show that the considered problem is challenging, in the sense that it violates the classical max-min inequality, and that it is NP-hard even under very strong assumptions (e.g., when the objective is strongly convex-strongly concave). We then develop a duality theory for it, and analyze conditions under which the duality gap becomes zero. Finally, we study a class of stationary solutions defined based on the dual problem, and evaluate their practical performance in an application on adversarial attacks on network flow problems.
Recommendations
Cites work
- A course in game theory.
- A Generalized Iterative Water-Filling Algorithm for Distributed Power Control in the Presence of a Jammer
- A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
- Bilevel optimization. Advances and next challenges
- Bilevel programming: a survey
- Convergence rate of \(\mathcal{O}(1/k)\) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems
- Convex optimization theory.
- Generalized Nash equilibrium problem, variational inequality and quasiconvexity
- Generalized Nash equilibrium problems
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 1351867 (Why is no real title available?)
- Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
- Introduction to algorithms.
- Lectures on convex optimization
- Mathematical Programs with Optimization Problems in the Constraints
- Multi-level decision making. Models, methods and applications
- Note on noncooperative convex games
- On a theorem of Danskin with an application to a theorem of Von Neumann-Sion
- On solving simple bilevel programs with a nonconvex lower level program
- On the solution of the KKT conditions of generalized Nash equilibrium problems
- Optimality conditions for bilevel programming problems
- Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions
- Penalty Methods for the Solution of Generalized Nash Equilibrium Problems
- Quadratic programming with one negative eigenvalue is NP-hard
- Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games
Cited in
(10)- On reduction of some multifold minimax problems with coupled constraints
- Bilinear minimax problems with linear constraints: Theory and numerical experiment
- scientific article; zbMATH DE number 7377700 (Why is no real title available?)
- Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems
- Accelerated minimax algorithms flock together
- Convergence properties of gradient-based methods for minimax problems with nonlinear constraints
- A first-order method for nonconvex-strongly-concave constrained minimax optimization
- A first-order augmented Lagrangian method for constrained minimax optimization
- A minimization approach for minimax optimization with coupled constraints
- An alternating proximal gradient algorithm for nonsmooth nonconvex-linear minimax problems with coupled linear constraints
This page was built for publication: Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076865)
