8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ Oct 22, 2013 at 11:17
  • $\begingroup$ @EwanDelanoy Thanks. I added continuity. $\endgroup$
    – triomphe
    Oct 23, 2013 at 1:13
  • $\begingroup$ 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). $\endgroup$ Oct 23, 2013 at 10:40
  • $\begingroup$ @EwanDelanoy The domain I took to be $\mathbb{R}^n\times \mathbb{R}^m$. So will it work then? $\endgroup$
    – triomphe
    Oct 23, 2013 at 19:40

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.