# Linearly constrained saddle-point optimization

Let $f(x,y)$ be a smooth (twice differentiable) saddle function (convex in $x$ and concave in $y$), where $f \colon X \times Y \rightarrow \mathbb{R}$, and $X \subset \mathbb R^n$, $Y \subset \mathbb R^m$ are convex compact sets.

I consider a constrained optimization problem of the form:

$$\min_{x \in X} \max_{y \in Y} f(x,y)$$

subject to:

$$A x + B y = c$$

where $A \in \mathbb R^{r\times n}, B \in \mathbb R^{r\times m}, c \in \mathbb R^r$.

Can $\min\max$ be exchanged with $\max\min$? Is the following equality true or false?

$$\min_{x \in X} \max_{y \in Y} f(x,y) = \max_{y \in Y} \min_{x \in X} f(x,y)$$

Given a smooth function $g(x)$ on a convex compact $X \subset\mathbb R^n$, there is $K$ such that $K \|x\|^2 + g(x)$ is convex. Let $f(x,y) = g(x) + K \|x\|^2 - K \|y\|^2$, which is convex in $x$ and concave in $y$. Then minimizing $g$ on $X$ is equivalent to $\min_{x \in X} \max_{y \in Y} f(x,y)$ on $X \times Y$ subject to $x - y = 0$. So your problem is no more special than an ordinary minimization problem.
• That's just a particular case. What about more general $f$? For example, an $f$ that is not a sum of the form $f(x,y) = g(x)+h(y)$? May 8, 2018 at 14:09