0

I am reading this post where @Yanko gives an answer that proves

$$\max_{x} \max_{y} f(x,y) = \max_{x, y} f(x,y)$$ for a function $f(x,y)$. Please let me quote the answer

Let $(x_0,y_0)$ be any two elements. Then clearly we have that $f(x_0 ,y_0) \leq\max_y f(x_0 ,y)$

Moreover we notice that $\max_x \max_y f(x,y)$ is the maximum over elements of the form $\max_y f(x',y)$ for some $x'$. In particular this implies that $f(x_0 ,y_0)\leq \max_y f(x_0 ,y)\leq \max _x \max_y f(x,y)$. As $x_0,y_0$ were chosen arbitrarily we may conclude that $\max_{x,y} f(x,y)\leq \max_x\max_y f(x,y)$ and the inequality in the other direction is obvious.

I am trying to understand the last sentence, i.e.,

As $x_0,y_0$ were chosen arbitrarily we may conclude that $\max_{x,y} f(x,y)\leq \max_x\max_y f(x,y)$ and the inequality in the other direction is obvious.

Could you please someone provide some more details on how this? Also, does this proof hold for non-separable functions $f(x,y)$? Could you please give an example?

Thoth
  • 863

1 Answers1

2

By definition of max, it should be immediate that

$$\max_{x}\max_{y}f(x,y)\leq \max_{x,y}f(x,y).\quad (1)$$

Now note we have the following for any $(x_0,y_0)$:

$$ f(x_0,y_0)\leq \max_y f(x_0,y)\leq \max_x\max_yf(x,y).\quad (2)$$

Choosing $(x_0,y_0)\in \arg\max_{x,y}f(x,y)$ in $(2)$ gives

$$ \max_{x,y}f(x,y)\leq \max_x\max_yf(x,y).\quad (3)$$

$(1)$ and $(3)$ give the desired result.

Golden_Ratio
  • 12,591
  • Thank you for your answer. Could you please elaborate a little more your first statement about the definition of max? What is the definition in this case? I do not catch it sorry. – Thoth Mar 14 '22 at 13:06
  • 1
    $\max_{x,y}f(x,y)$ is at least as great as any other value of $f(x,y)$ in the domain. Choose $\max_x \max_y f(x,y)$ as this other value. – Golden_Ratio Mar 14 '22 at 13:08
  • A little better, but it is more natural for me to think $f(x,y)\leq \max_{x,y}f(x,y)$. Any comment is highly appreciated to understand it a little better. – Thoth Mar 14 '22 at 13:19
  • @Thoth That's correct. But then note that $\max_x\max_yf(x,y)=f(x_0,y_0)$ for some $x_0,y_0$ – Golden_Ratio Mar 14 '22 at 13:22
  • @Thoth Btw just a minor notational point: it may not be the best idea to use $x,y$ both to label an arbitrary point and to denote the dummy variables you are maximizing over. – Golden_Ratio Mar 14 '22 at 13:26
  • Still don't get it. Let $x^$ and $y^$ the optimal points that maximize $f(x, y)$ w.r.t. $x$ and $y$, respectively. That is, $x^$ and $y^$ are those that solve $\partial_x f(x,y)=0$ and $\partial_y f(x,y)=0$, for some $y$ and $x$, respectively. Then, what I can think about some $x_0, y_0$ is $\max_x\max_yf (x,y)\geq f(x_0,y_0)$ ? – Thoth Mar 14 '22 at 13:33
  • @Thoth You are complicating the problem. The statement has nothing to do with derivatives (it would hold if the function is not differentiable). First, do you acknowledge that $f(x_0,y_0)\leq \max_{x,y} f(x,y)$ for any $(x_0,y_0)$? This is the definition of a maximum... – Golden_Ratio Mar 14 '22 at 13:35
  • Sorry if I complicated thinks. I was thinking optimization in terms of first order optimality condition. Yes I acknowledge $f(x' ,y') \leq \max_{x,y} f(x,y)$, for any $x', y'$. – Thoth Mar 14 '22 at 13:54
  • @Thoth Ok and do you acknowledge that at some point $(x_0,y_0)$ we have $f(x_0,y_0)=\max_x\max_y f(x,y)$? This follows because a function always attains its maximum. The RHS first fixes x and maximizes over y and then maximizes over x; wherever that winds up, it is some point on the function. – Golden_Ratio Mar 14 '22 at 13:55
  • Ok I acknowledge that. Please continue. – Thoth Mar 14 '22 at 14:01
  • @Thoth Put together my last two comments and you get the first remark in my answer – Golden_Ratio Mar 14 '22 at 14:02
  • I think now I see your point, given $f(x' ,y') \leq \max_{x,y} f(x,y)$ which holds for any point $x', y'$ and also given $x_0,y_0$ that is defined by $f(x_0,y_0)=\max_x\max_y f(x,y)$, you finally get $\max_{x}\max_{y}f(x,y)\leq \max_{x,y}f(x,y)$. – Thoth Mar 14 '22 at 14:08
  • 1
    @Thoth that's correct – Golden_Ratio Mar 14 '22 at 14:10
  • I see that a similar procedure is followed for $(2)$ and $(3)$ but in the opposite direction. I think I got the entire intuition. Thanks you your time! – Thoth Mar 14 '22 at 14:15
  • @Thoth I think (1) is more immediate. Note the intermediate term used to justify (2) – Golden_Ratio Mar 14 '22 at 14:17
  • Ok I think I see you point. Thanks for the comment. – Thoth Mar 14 '22 at 14:24
  • @Thoth no prob. feel free to accept the ans if it helps – Golden_Ratio Mar 14 '22 at 14:27