Understanding subsequence convergence for Neumann's Minimax theorem.

59 Views Asked by At

Context: von Neumann proved that if $f$ is a continuous function on two compact sets $X,Y$ of the Generalized Euclideian Field, such that: $f$ is convex on $X$ and concave on $Y$ (vice versa also allowed and applies the same) then we have that \begin{align} \boxed{\max_{x \in X} \min_{y \in Y} f(x,y) = \max_{y \in Y} \min_{x \in X}f(x,y)}. \end{align}

Basically what it says is that it outlines the necessary and able conditions for guaranteeing the equality part on the also very well known (from Multivariable Calculus) Max-Min Inequality.

My question starts now: I have been studying a part of this proof for a while now. The first parts are easy enough, since they start with the assumption that $f$ is already strictly-convex/strictly-concave.

However, what happens when $f$ is NOT strictly-convex/strictly-concave? The author says we take $\epsilon > 0$ and create \begin{align} f_{\epsilon} (x,y) = f(x,y) - \epsilon ||x||^2 + \epsilon ||y||^2 \end{align} so that $f_{\epsilon}$ now can fulfill our original premise and therefore it can have a sagmatic/saddle point $(x_\epsilon, y_\epsilon) \in X \times Y $. We then take the compactness of $A \times B$ and setting $\epsilon_j \to 0$ we can find a subsequence $(x_{\epsilon_{j}}, y_{\epsilon_{j}} )$ that converges to a sagmatic/saddle point of $f$.

I am completely out of ideas. What I know is that another condition for sagmatic point is \begin{align} f: X \times Y \to \mathbb{R}, \exists (x_0 ,y_0): f(x, y_0) \leq f(x_0, y_0 ) \leq f(x_0, y). \end{align}

How can we tie those together?

Many thanks!

1

There are 1 best solutions below

1
On BEST ANSWER

Let $(x_\epsilon,y_\epsilon)$ be a saddle point of $f_\epsilon$. That is, for all $(x,y)\in X\times Y$, we have $$ f_\epsilon(x,y_\epsilon) \le f_\epsilon(x_\epsilon,y_\epsilon) \le f_\epsilon(x_\epsilon,y) . $$ Assume $(x_\epsilon,y_\epsilon)\to (x_0,y_0)$, then we can pass to the limit in the above inequality for $\epsilon\searrow0$ and fixed $(x,y)$ to obtain $$ f(x,y_0) \le f(x_0,y_0) \le f(x_0,y) . $$ Here, we used that $X\times Y$ is compact hence bounded, and $f$ is continuous. Now this inequality is fulfilled for all $(x,y)$, and $(x_0,y_0)$ is a saddle point.