0
$\begingroup$

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)$$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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)$? $\endgroup$ Commented May 8, 2018 at 14:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.