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

arXiv: https://arxiv.org/abs/2110.11210 · HTML: https://mlsanity.com/paper/2110.11210/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2021.

## Built on by (most cited first, 4 of 4)

- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023)
- [Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm](https://mlsanity.com/paper/2210.03967/) (2022)
- [Decoupled SGDA for Games with Intermittent Strategy Communication](https://mlsanity.com/paper/2501.14652/) (2025)

## Abstract (arXiv)

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.