Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality
研究一类最小化和最大化变量受共同线性约束的极小极大问题，证明其违反经典极大极小不等式且即使目标强凸-强凹也是NP难的，并建立对偶理论分析零对偶间隙的条件。
.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.Keywordsmin-max problemcoupled constraintsduality theorycomputational complexitymax-min inequalityMSC codes49K3565K0590C47