Optimality Conditions for Constrained Minimax Optimization

Abstract

Minimax optimization problems arises from both modern machine learning including generative adversarial networks, adversarial training and multi-agent rein-forcement learning, as well as from tradition research areas such as saddle point prob-lems, numerical partial differential equations and optimality conditions of equality constrained optimization. For the unconstrained continuous nonconvex-nonconcave situation, Jin, Netrapalli and Jordan (2019) carefully considered the very basic ques-tion: what is a proper definition of local optima of a minimax optimization problem, and proposed a proper definition of local optimality called local minimax. We shall extend the definition of local minimax point to constrained nonconvex-nonconcave minimax optimization problems. By analyzing Jacobian uniqueness conditions for the lower-level maximization problem and the strong regularity of Karush-Kuhn-Tucker conditions of the maximization problem, we provide both necessary optimality condi-tions and sufficient optimality conditions for the local minimax points of constrained minimax optimization problems.

Keywords

Constrained minimax optimization / value function / Jacobian uniqueness conditions / strong regularity / necessary optimality conditions / sufficient optimality conditions