The discussion revolves around the equivalence of the min-max and max-min operations in mathematical optimization, exploring whether the expressions \(\underset{i}{\min}\underset{n}{\max}=\underset{n}{\max}\underset{i}{\min}\) hold true. Participants delve into specific examples and related inequalities, examining the conditions under which these operations may differ or align.
Participants generally disagree on the equivalence of min-max and max-min, with multiple competing views presented. The validity of the introduced inequality is affirmed by some, while the interchangeability of max-max and min-min appears to be more widely accepted.
Limitations include the dependence on the definitions of supremum and infimum, as well as the specific conditions under which the discussed inequalities and equivalences hold.
micromass said:No. Take
x_{i,n}=\left\{\begin{array}{l} 0 ~\text{if}~i+n~\text{even}\\<br /> 1 ~\text{if}~i+n~\text{odd}\end{array}\right.
theorem4.5.9 said:In general you do not have equality between min-max and max-min, however I couldn't resist mentioning a very neat inequality I learned a bit ago.
Given a real valued function ##P(x,y): X \times Y \rightarrow \mathbb{R}## one has
$$\inf_{x\in X} \sup_{y\in Y} P(x,y) \geq \sup_{y\in Y} \inf_{x\in X} P(x,y)$$
If you aren't familiar with sup (supremum - least upper bound) and inf (infimum - greatest lower bound) you can think of sup as max and inf as min.
I learned this from Robert McCann, it's in the following article. Skip to 2.2 Game Theory for an intuitive 'proof'.
http://www.math.toronto.edu/mccann/papers/FiveLectures.pdf
Yes. To see this pick x'\in X and y'\in Y. Clearly \sup_Y P(x',y)\geq \inf_X P(x,y'), and since this is true for all y'\in Y we have \sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y), by definition of the supremum. Similarly, since this is true for all x'\in X we have \inf_X\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y) by definition of the infimum.S_David said:Is this inequality true in general?
dcpo said:Yes. To see this pick x'\in X and y'\in Y. Clearly \sup_Y P(x',y)\geq \inf_X P(x,y'), and since this is true for all y'\in Y we have \sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y), by definition of the supremum. Similarly, since this is true for all x'\in X we have \inf_Y\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y) by definition of the infimum.
Yes. Consider \sup_X\sup_Y P(x,y). By definition we have \sup_X\sup_Y P(x,y)\geq P(x',y') for all x'\in X,y'\in Y, so \sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y) by definition of \sup. Conversely, if \sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y) then there is x'\in X with \sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y), and thus there is y'\in Y with \sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y), which would be a contradiction. So \sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y) and a symmetry argument gives \sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y).S_David said:OK, what abou max max or min min, are they interchangeable?
dcpo said:Yes. Consider \sup_X\sup_Y P(x,y). By definition we have \sup_X\sup_Y P(x,y)\geq P(x',y') for all x'\in X,y'\in Y, so \sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y) by definition of \sup. Conversely, if \sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y) then there is x'\in X with \sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y), and thus there is y'\in Y with \sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y), which would be a contradiction. So \sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y) and a symmetry argument gives \sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y).
Edit: We require that the suprema and infima are defined, I forgot to mention that in my original response.