Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods

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.

References in corpus (9)

• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Near-Optimal Algorithms for Minimax Optimization
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Efficient Algorithms for Smooth Minimax Optimization
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Stochastic Hamiltonian Gradient Methods for Smooth Games
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function