# $\max\min$ problem

Suppose there is a real valued function $f(x,y)$ where $x,y$ are vector variables $x\in\mathbb{R}^n$ $y\in\mathbb{R}^m$. Moreover $f$ is strictly/concave in $x$ and strictly/convex in $y$. $f$ is also continuous. The problem is $$\max_x\min_y f(x,y)=\min_y\max_x f(x,y).$$

Please explain to me how to analyse this problem. From When $\min \max = \max \min$? I see that it is not generally true. But I guess the convexity information given above may force equality.

Thanks a lot

• If $f$ (or its partial functions) is not continuous, the $\sf min$ and $\sf max$ may not exist (convexity/concavity is not enough to guarantee continuity). Perhaps you mean $\sf inf$ and $\sf sup$. Oct 22, 2013 at 11:17
• @EwanDelanoy Thanks. I added continuity. Oct 23, 2013 at 1:13
• I guess you also need the the domain of definition to be compact (think of $f(x,y)=xy$ : there is no $\min$ or $\max$ except when $x$ or $y$ is zero). Oct 23, 2013 at 10:40
• @EwanDelanoy The domain I took to be $\mathbb{R}^n\times \mathbb{R}^m$. So will it work then? Oct 23, 2013 at 19:40

## 1 Answer

According to the definitions that you made, first the $\min$ and $\max$ should exist. For this you will need a compact space from where you draw $x$ and $y$. In addition to this, if your objective function $f$ is convex in $y$ and concave $x$ then According to Von Neumann's minimax theorem

$$\max_x\min_y f(x,y)=\min_y\max_x f(x,y).$$

holds. This also implies that the topology that you have accepts a saddle point. http://en.wikipedia.org/wiki/Saddle_point If you have such a topology then the order of minimization or maximization doesnt matter. If this does not hold, then you have

$$\max_x\min_y f(x,y)\leq \min_y\max_x f(x,y)$$

Von Neumann's minimax theorem gives us a sufficient condition such that we have a saddle point