2

For a minimization problem of function $f(x,y)$, does the equation $min_{x,y} f(x,y)=min_{y}min_{x}f(x,y)=min_{x}min_{y}f(x,y)$ always hold?

I saw this equation somewhere. It does the minimization in a sort of iterated way, treating either $x$ or $y$ as a constant first. But what about a saddle point? If I use Hessian matrix to consider the convexity of $f(x,y)$, it will let me know it doesn't work if there's a saddle point, while this iterated method may still give me a value.

I think this kind of problems falls into optimization, and I also wonder if $min_{y}max_{x}f(x,y)=max_{x}min_{y}f(x,y)$ holds.

Hank
  • 668

1 Answers1

1

Let $X$ and $Y$ be arbitrary non-empty sets and let $f:X\times Y\to\mathbb R$ be a function.

Claim: $\inf_{(x,y)\in X\times Y}f(x,y)=\inf_{x\in X}\inf_{y\in Y}f(x,y)$.

This includes the possibility that any of the infima is $-\infty$. If all of the infima involved are actually attained, then you can replace “$\inf$ ” with “$\min$.”

Therefore, the answer to your question is affirmative, with the caveat that $\min_{y\in Y}f(x,y)$ may not exist (because the infimum value is not attained by any $y\in Y$) for some of the $x\in X$, even if the joint minimum $\min_{(x,y)\in X\times Y}f(x,y)$ does exist.

Proof: For any $x_0\in X$ and and $y_0\in Y$, it is clear that $$f(x_0,y_0)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$ Leaving $x_0$ fixed and allowing $y_0$ to vary, we then have that $$\inf_{y\in Y}f(x_0,y)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$ This is true for any fixed $x_0\in X$, so we can now take infimum over $X$ to obtain $$\inf_{x\in X}\inf_{y\in Y}f(x,y)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$

For the reverse inequality, fix again $x_0\in X$ and $y_0\in Y$. Clearly, we have that $$\inf_{x\in X}\inf_{y\in Y}f(x,y)\leq\inf_{y\in Y}f(x_0,y)\leq f(x_0,y_0).$$ Now we can take infimum on the right-hand side over all of $X\times Y$ to obtain that $$\inf_{x\in X}\inf_{y\in Y}f(x,y)\leq\inf_{(x,y)\in X\times Y}f(x,y),$$ which completes the proof. $\quad\blacksquare$

For the interchangeability of the maximum and minimum operators, please consult this thread.

triple_sec
  • 23,377
  • How can we get $\inf_{x\in X}\inf_{y\in Y}f(x,y)\geq\inf_{(x,y)\in X\times Y}f(x,y)$? – Hank Nov 04 '17 at 14:18
  • @Hank For each $x_0\in X$, define $$T(x_0)\equiv\inf_{y\in Y}f(x_0,y).$$ By the second inequality from the top, we have $$T(x_0)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$ Note that the right-hand side doesn’t depend on $x_0$, since the $x$ term has already been “infed out.” Now, this inequality is true for all $x_0\in X$, so we may take infimum with respect to $x_0\in X$ to get $$\inf_{x_0\in X}T(x_0)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$ Now, if you use the definition of $T(\cdot)$ and replace $x_0$ with $x$ in it (it is now only a matter of notation), you get the third inequality from the top. – triple_sec Nov 04 '17 at 20:11
  • I see. If $T(x)\geq c$ for any $x$ and some constant $c$, then $\inf T(x)\geq c $ for any $x$, right? I proved this by contradiction. Thanks! – Hank Nov 04 '17 at 23:43
  • @Hank Exactly. Proof by contradiction works, too, but here is a more direct approach. If $T(x)\geq c$ for all $x\in X$, where $c$ is some constant, then $c$ is a lower bound on the set ${T(x),|,x\in X}$ of real numbers. Now, the infimum, by definition, is the greatest lower bound on that set, so that $\inf_{x\in X} T(x)$ must be greater than (or equal to) any other lower bound; in particular, it must be greater than $c$. Therefore, we have $$\inf_{x\in X}T(x)\geq c.$$ – triple_sec Nov 05 '17 at 03:16