KKT Conditions for Minmax Problem

Question

Let $\mathbf{x}\in\mathbb{R}^n$ and $\mathbf{y}\in\mathbb{R}^m$. Now $$f\left(\mathbf{x}, \mathbf{y}\right):\mathbb{R}^n\times\mathbb{R}^m\rightarrow\mathbb{R}$$ is convex in $\mathbf{x}$ and concave in $\mathbf{y}$. The problem is to find $$\mbox{min}_{\mathbf{x}}\mbox{max}_{\mathbf{y}}f\left(\mathbf{x}, \mathbf{y}\right)$$ constrained by $\mathbf{x}\in\mathcal{F}_1\subseteq\mathbb{R}^n$ and $\mathbf{y}\in\mathcal{F}_2\subseteq\mathbb{R}^m$. $\mathcal{F}_1$ and $\mathcal{F}_2$ are convex sets. Obviously the problem can be tackled in two steps as optimisations with respect to $\mathbf{x}$ and $\mathbf{y}$. But is there any way to formulate a Lagrangian dual and KKT conditions at a single go?

Answer 1

Since the inner problem $\min_y -f(x,y)$ is convex, the first-order conditions are necessary and sufficient for optimality. These optimality conditions have $x$ as a parameter. Hence, you can rewrite your problem as \begin{align*}\min & \quad f(x,y)\\ \text{such that}&\quad y \text{ satisfies the opt. cond. of the inner problem with parameter } x\end{align*} If your set $F_2$ is given by equality and inequality constraints, the first-order conditions become the KKT conditions. If only equality constraints are present in $F_2$, the rewritten problem becomes a classical NLP and you can write down its KKT conditions. However, if inequality constraints are included in $F_2$, the KKT conditions will include complementarity conditions like $g(y) \ge 0$, $\lambda \ge 0$ and $\lambda \, g(y) = 0$, and the rewritten problem becomes a mathematical program with complementarity constraints (MPCC). This type of problems have severe difficulties: MFCQ is violated at every feasible point and KKT multipliers may not exist. For further reading, I suggest this paper and the papers by C. Kanzow.