- #1
- 1,368
- 61
Hello,
Is
[tex]\underset{i}{\min}\underset{n}{\max}=\underset{n}{\max}\underset{i}{\min}[/tex]?
Thanks
Is
[tex]\underset{i}{\min}\underset{n}{\max}=\underset{n}{\max}\underset{i}{\min}[/tex]?
Thanks
micromass said:No. Take
[tex]x_{i,n}=\left\{\begin{array}{l} 0 ~\text{if}~i+n~\text{even}\\
1 ~\text{if}~i+n~\text{odd}\end{array}\right.[/tex]
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 [itex]x'\in X[/itex] and [itex]y'\in Y[/itex]. Clearly [itex]\sup_Y P(x',y)\geq \inf_X P(x,y')[/itex], and since this is true for all [itex]y'\in Y[/itex] we have [itex]\sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y)[/itex], by definition of the supremum. Similarly, since this is true for all [itex]x'\in X[/itex] we have [itex]\inf_X\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y)[/itex] by definition of the infimum.S_David said:Is this inequality true in general?
dcpo said:Yes. To see this pick [itex]x'\in X[/itex] and [itex]y'\in Y[/itex]. Clearly [itex]\sup_Y P(x',y)\geq \inf_X P(x,y')[/itex], and since this is true for all [itex]y'\in Y[/itex] we have [itex]\sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y)[/itex], by definition of the supremum. Similarly, since this is true for all [itex]x'\in X[/itex] we have [itex]\inf_Y\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y)[/itex] by definition of the infimum.
Yes. Consider [itex]\sup_X\sup_Y P(x,y)[/itex]. By definition we have [itex]\sup_X\sup_Y P(x,y)\geq P(x',y')[/itex] for all [itex]x'\in X,y'\in Y[/itex], so [itex]\sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y)[/itex] by definition of [itex]\sup[/itex]. Conversely, if [itex]\sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y)[/itex] then there is [itex]x'\in X[/itex] with [itex]\sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y)[/itex], and thus there is [itex]y'\in Y[/itex] with [itex]\sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y)[/itex], which would be a contradiction. So [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)[/itex] and a symmetry argument gives [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y)[/itex].S_David said:OK, what abou max max or min min, are they interchangeable?
dcpo said:Yes. Consider [itex]\sup_X\sup_Y P(x,y)[/itex]. By definition we have [itex]\sup_X\sup_Y P(x,y)\geq P(x',y')[/itex] for all [itex]x'\in X,y'\in Y[/itex], so [itex]\sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y)[/itex] by definition of [itex]\sup[/itex]. Conversely, if [itex]\sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y)[/itex] then there is [itex]x'\in X[/itex] with [itex]\sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y)[/itex], and thus there is [itex]y'\in Y[/itex] with [itex]\sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y)[/itex], which would be a contradiction. So [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)[/itex] and a symmetry argument gives [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y)[/itex].
Edit: We require that the suprema and infima are defined, I forgot to mention that in my original response.
"Min max" and "max min" refer to two different methods of optimization. "Min max" is a method where the goal is to minimize the maximum value of a function, while "max min" is a method where the goal is to maximize the minimum value of a function.
No, the min max and max min methods are not always equivalent. It depends on the specific function being optimized and the constraints of the problem.
The method used depends on the specific problem and the desired outcome. Some problems may require minimizing the maximum value, while others may require maximizing the minimum value. It is important to carefully consider the problem and its constraints before deciding on a method.
One example would be a problem where the goal is to allocate resources to different projects in order to maximize the minimum profit. In this case, the max min method would be used. However, if the goal was to minimize the maximum cost of the projects, the min max method would be used. This would likely result in different allocations of resources and thus different results.
Each method has its own advantages and disadvantages. The min max method may be more suitable for problems where minimizing risk is a priority, while the max min method may be better for problems where maximizing rewards is the main goal. It is important to carefully consider the problem and its constraints before deciding on a method. Additionally, some problems may have multiple solutions that can be found using either method, while others may only have one optimal solution with one of the methods.