8
$\begingroup$

Let $X \subset \mathbb{R}^n$ and $Y \subset \mathbb{R}^m$ be compact sets.

Consider a continuous function $f : X \times Y \rightarrow \mathbb{R}$.

Say under which condition we have

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

From this we have that $\max_{y \in Y} \min_{x \in X} f(x,y) \leq \min_{x \in X} \max_{y \in Y} f(x,y)$. So here we are looking for conditions on $f$ such that we have the equality.

  • 0
    I am intersted in a similar question, but in the presence of constrains coupling $x$ and $y$.2018-05-11

3 Answers 3

-2

take two examples:

$f(x,y) = \cos(x+y)$

and

$f(x,y)=2xy(x-y)$

In the first case $\min_x \max_y f(x,y)=1 $ and $\max_y\min_x f(x,y)=-1$ for all $x,y$.

In the second one we have $y=0.5x$ and $x=0.5y$ since we have $f(x,y)^{''}>0$ for $\frac{d^2}{dx}f(x,y)$ and $f(x,y)^{''}<0$ for $\frac{d^2}{dy}f(x,y)$, they are minima and maxima respectively. As a result one gets $\min_x \max_y f(x,y) = \max_y \min_x f(x,y)$

for the second case.

3

If you look at this problem as a Primal Problem and its Dual Problem then you're basically asking when Strong Duality Holds.

Basically when $ f\left( x, y \right) $ is Convex in $ x $ and Concave in $ y $.

3

A general result called Von Neumann-Fan minimax theorem states the following:

Theorem 2 (Von Neumann-Fan minimax theorem). Let $X$ and $Y$ be Banach spaces.Let $C \subset X$ be nonempty and convex, and let $D \subset Y$ be nonempty, weakly compact and convex. Let $g : X \times Y \to \Bbb{R}$ be convex with respect to $x \in C$ and concave and upper-semicontinuous with respect to $y \in D$, and weakly continuous in $y$ when restricted to $D$. Then $d := \max_{y\in D} \inf_{x\in C} g(x, y) = \inf_{x\in C} \max_{y\in D} g(x, y).$

See for example the following link: https://www.carma.newcastle.edu.au/jon/minimax.pdf

  • 0
    Can we replace weak with weak$^{\star}$ in the statement?2018-10-15