2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Denis Jul 7 '13 at 17:57
  • $\begingroup$ Thank you! what do you mean by order? $\endgroup$ – Mahdi Khosravi Jul 7 '13 at 18:00
  • $\begingroup$ 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. $\endgroup$ – Denis Jul 7 '13 at 18:02
  • $\begingroup$ 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)$ ? $\endgroup$ – Denis Jul 7 '13 at 18:05
  • $\begingroup$ obviously, it's $\min_x \sin(x) + \min_y \sin(y)$ $\endgroup$ – Mahdi Khosravi Jul 7 '13 at 18:06
1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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