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?

Answer 1

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...

Answer 2

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} $$