2
$\begingroup$

It might be a trivial question. Consider a continuous and differentiable function (highly non-convex) $f:X \times Y \to ℝ$. Would this always be true that

$$\max_{𝑥 \in 𝑋} \max_{𝑦 \in 𝑌} f(x,y)= \max_{𝑦\in𝑌} \max_{𝑥 \in 𝑋} f(x,y)= \max_{x,y \in X \times Y} f(x,y)$$

Note that both are max operators. If that doesn't always hold, then what are the conditions under which these equalities hold?

I see a similar question in Maximize function of two variables, but I don't think I got what I wanted out of this page! I need a little more clues.

Could you tell me what the definition of $𝑦^∗ = \text{argmax}_{y} f(x,y)$ is? I think that's where I get confused. If it was $x^* = \text{argmax}_{x} f(x)$ (the outer optimization), then the definition would have been something like $f(x^*) > f(x)$ for all $x$ in the feasible set. What would be the analogous definition here?

$\endgroup$

1 Answer 1

0
$\begingroup$

This is identical. If one considers WLOG that

$$\underbrace{\max_{𝑥 \in 𝑋} \max_{𝑦 \in 𝑌} f(x,y)}_{f(x_0,y_0)} < \underbrace{\max_{𝑦\in𝑌} \max_{𝑥 \in 𝑋} f(x,y)}_{f(x_1,y_1)}$$

then obviously $[x_0,y_0] \neq [x_1,y_1]$ and

$f(x_1,y_1) \le \max_{𝑥 \in 𝑋} f(x,y_1) \le \max_{𝑥 \in 𝑋} [\max_{𝑦 \in 𝑌} f(x,y)]=f(x_0,y_0)\,\mathbf{<}\,f(x_1,y_1)$

which is contradictory. Therefore equality is the only possibility.

$\endgroup$
4
  • $\begingroup$ ?? I see! But I am not convinced yet. Could you be kind enough to tell me what the definition of $y^* = \argmax_{y} f(x,y)$ is? I think that's where I get confused. If it was a x^* = \argmax_{x} f(x) (the outer optimization), then the definition would have been something like f(x^*) > f(x) for all x in the feasible set. What would be the analogous definition here? $\endgroup$
    – erfaun
    Commented Jan 17, 2022 at 1:31
  • $\begingroup$ The definition of $ \text{argmax}_{y} f(x,y)$ is standard (en.wikipedia.org/wiki/Arg_max), where $x$ is taken as parameter. It is however a set which can contain more than one element in general. Regarding the result, look also to this article www.zazen.cz/media/av/max-max-opt.pdf to Eq. (7) or to this book www.zazen.cz/media/av/Introduction_to_the_Theory_of_Games_by_McKinsey_page18_Exercice11.pdf to page 18, Exercise 11 (this book is referenced in that article). $\endgroup$ Commented Jan 18, 2022 at 10:44
  • $\begingroup$ New question relevant to this one: math.stackexchange.com/questions/4360002/… $\endgroup$ Commented Jan 18, 2022 at 16:33
  • 1
    $\begingroup$ Very useful link. Thank you. $\endgroup$
    – erfaun
    Commented Jan 19, 2022 at 23:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .