Are the min max is equivalent to max min?

In summary, there is a neat inequality that states that the infimum of the supremum of a real valued function is greater than or equal to the supremum of the infimum of the same function. This is a general inequality and holds true for all functions. However, the equality between min-max and max-min does not always hold.
  • #1
1,368
61
Hello,

Is

[tex]\underset{i}{\min}\underset{n}{\max}=\underset{n}{\max}\underset{i}{\min}[/tex]?

Thanks
 
Mathematics news on Phys.org
  • #2
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]
 
  • #3
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]

Yeah, right.
 
  • #4
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
 
  • #5
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

Is this inequality true in general?
 
  • #6
S_David said:
Is this inequality true in general?
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.
 
Last edited:
  • #7
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.

OK, what abou max max or min min, are they interchangeable?
 
  • #8
S_David said:
OK, what abou max max or min min, are they interchangeable?
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.
 
  • #9
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.

Yes, of course they are defined.

Thanks
 

1. What does "min max" and "max min" mean in this context?

"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.

2. Are the min max and max min methods always equivalent?

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.

3. How do you determine which method to use?

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.

4. Can you provide an example of when the min max and max min methods would give different results?

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.

5. Are there any advantages or disadvantages to using one method over the other?

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.

Similar threads

  • General Math
Replies
8
Views
2K
Replies
8
Views
1K
Replies
2
Views
965
Replies
6
Views
3K
  • General Math
Replies
11
Views
1K
Replies
3
Views
930
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
1K
  • General Math
Replies
7
Views
1K
  • Introductory Physics Homework Help
Replies
5
Views
780
  • General Math
Replies
1
Views
1K
Back
Top