When $\min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y)$?

Question

When $$ \min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y) \qquad? $$
I mean when we are minimizing a function with respect to two variables, under what conditions we are allowed to minimize over one variable and then minimize over the other one?

when you do your first minimization (the inner one on $y$), you implicitly assume that you can compare functions (the functions $x\mapsto f(x,y)$) . What order do you use on functions? — Denis, Jul 07 '13 at 17:57
I mean what is the meaning of $\min_y f(x,y)$? The only meaning I see would be the minimum of all functions $f(\cdot,y)$, but then you need to define what is the minimum operation for functions. — Denis, Jul 07 '13 at 18:02
To take an example, let's say $f(x,y)=\sin(x)+\sin(y)$, what is the result of $\min_x \min_y f(x,y)$ ? — Denis, Jul 07 '13 at 18:05
when you say "under what conditions we are allowed to minimize over one variable and then minimize over the other one?", I don't understand what your first step is. How can you minimize a two-variable function on only one variable? Do you see the problem? — Denis, Jul 07 '13 at 18:08
In your example we are allowed to do so. I'm looking for a general condition that we are allowed to do so. — Mahdi Khosravi, Jul 07 '13 at 18:10
if you compare functions via their minimum values (which you are probably doing without noticing), then $\min_{x,y}$ is exactly the same as $\min_x\min_y$. If you claim it's not always the same, can you give an example? — Denis, Jul 07 '13 at 18:10
$x$ and $y$ are not necessarily are possible real numbers. Let me edit the question! — Mahdi Khosravi, Jul 07 '13 at 18:13
so you mean we are always allowed to do minimization separately? — Mahdi Khosravi, Jul 07 '13 at 18:14
Again, you didn't define precisely what it means to do it separately. But in the only way that makes sense, yes you always can, and the order does not matter. — Denis, Jul 07 '13 at 18:14
Would you mind looking at this link? All I want to do is that. Thanks — Mahdi Khosravi, Jul 07 '13 at 18:19
in the link you have $\min$ and $\max$, which cannot be reverted in general. You ask about $\min$ and $\min$, that always can. — Denis, Jul 07 '13 at 18:29
Thank you. You know if we separate the minimization, the argmin of the inner minimization ($y^$) would be function of the outer minimzation parameter ($x$). When the inner minimizer is independent of the outer minimization parameter. For my case when $y^$ is independent of parameter $x$? — Mahdi Khosravi, Jul 07 '13 at 18:33
Assume we are going to minimize $xy+y^2$. First minimizing over $y$ gives $y^=-x \over 2$ and we must put this $y^$ in $g(x)=f(x,y^)$ and minimize over $x$. I'm looking for a condition that the solution $y^$ is not a function of $x$. Thanks — Mahdi Khosravi, Jul 07 '13 at 18:52
I don't agree with your $y^*$, for instance with $x=-10$, choosing $y=1$ is better than $y=5$. — Denis, Jul 07 '13 at 19:37
$y=1$ leads to $-9$ and $y=5$ leads to $-25$ and obviously the latter is better. — Mahdi Khosravi, Jul 07 '13 at 19:40
oups yes sorry, I thought you were aiming at $0$, went too fast. So for the independence of $y^*$ in $x$, the easy case is when $x$ do not appear in the derivative of $f(x,y)$ with respect to $y$. So $f(x,y)$ is of the form $g(x)+h(y)$. It could only be that $x$ do appear in the formula, but not in the solution for the minimum, for instance for $f(x,y)=x^2y^2$. This case can probably be detected by showing that the $y$-derivative $2x^2 y$ is of the form $h(x)g(y)$, so $x$ does not influence its roots. — Denis, Jul 07 '13 at 19:48

score 5 · Answer 1 · answered Jul 07 '13 at 22:54

For each $x$, $$ \min_yf(x,y)\ge\min_{x,y}f(x,y)\tag{1} $$ Taking the minimum over $x$, $$ \min_x\min_yf(x,y)\ge\min_{x,y}f(x,y)\tag{2} $$ However, there is an $(x_0,y_0)$ so that $f(x_0,y_0)=\min\limits_{x,y}f(x,y)$. Then $$ \min_yf(x_0,y)=\min_{x,y}f(x,y)\tag{3} $$ Therefore, we must have that the minimum over all $x$ is at most the value at one $x_0$: $$ \min_x\min_yf(x,y)\le\min_{x,y}f(x,y)\tag{4} $$ $(2)$ and $(4)$ show that $$ \min_x\min_yf(x,y)=\min_{x,y}f(x,y)\tag{5} $$

score 1 · Accepted Answer · answered Jul 07 '13 at 22:20

I compile the answer here for clarity.

First I reformulate the question : given a function of two variables $f(x,y)$, its minimum can be written $\min_x y^*(x)$, where $y^*(x)=\min_y f(x,y)$. Question: under which condition $y^*(x)$ is a constant function, so is independent of $x$?

Answer: Let $f'(x,y)$ be the $y$-derivative of $f(x,y)$. $y^*(x)$ is exprimable as a solution of $f'(x,y)=0$. A sufficient condition for $y^*$ to be a constant is if $f'(x,y)$ is of the form $h(x,y)g(y)$, where $y^*$ is a root of $g$.

I don't know about a proof of the converse, but this should cover most cases in practice...

When $\min_{x \in X,y \in Y} f(x,y) = \min_{x \in X} \min_{y \in Y} f(x,y)$?

2 Answers2

Linked

Related