Namespaces
Variants
Actions

Difference between revisions of "Maximin"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
The mixed extrema
 
The mixed extrema
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630201.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$\sup_{x\in X}\inf_{y\in Y}F(x,y),\quad\max_{x\in X}\min_{y\in Y}F(x,y),\quad\text{etc.}\tag{*}$$
  
 
A maximin can be interpreted (for example, in decision theory, [[Operations research|operations research]] or game theory, cf. [[Games, theory of|Games, theory of]]) as the greatest gain among those that can be attained by decision making under the worst conditions; it is, thereby, a guaranteed gain. Therefore, decision making oriented on a maximin may reasonably be regarded as optimal.
 
A maximin can be interpreted (for example, in decision theory, [[Operations research|operations research]] or game theory, cf. [[Games, theory of|Games, theory of]]) as the greatest gain among those that can be attained by decision making under the worst conditions; it is, thereby, a guaranteed gain. Therefore, decision making oriented on a maximin may reasonably be regarded as optimal.
  
The value of a maximin does not exceed the value of the corresponding [[Minimax|minimax]]. Conditions for their equality are very important in game theory (see [[Minimax principle|Minimax principle]]). Such conditions are, for example, the presence of a linear structure in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630202.png" />, the convexity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630203.png" /> and the concavity of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630204.png" /> relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630205.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630206.png" /> (or, the linearity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630207.png" /> and convexity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630208.png" />, and convexity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m0630209.png" /> relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302010.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302011.png" />).
+
The value of a maximin does not exceed the value of the corresponding [[Minimax|minimax]]. Conditions for their equality are very important in game theory (see [[Minimax principle|Minimax principle]]). Such conditions are, for example, the presence of a linear structure in $X$, the convexity of $X$ and the concavity of the function $F$ relative to $x\in X$ for each $y\in Y$ (or, the linearity of $X$ and convexity of $Y$, and convexity of $F$ relative to $y\in Y$ for each $x\in X$).
  
Finding a maximin as a mathematical operation formally consists in the successive calculation of extrema, that is, in the solution of standard ( "single-criterion" ) optimal programming problems, and, therefore, involves no conceptual complications. However, even when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302012.png" /> is  "well arranged"  and the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302013.png" /> is uniformly continuous on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302014.png" />, the function which associates to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302015.png" /> the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302016.png" /> at which the extremum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302017.png" /> is attained (or  "almost attained" ) can turn out to be  "badly arranged"  and, in particular, can be a discontinuous function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063020/m06302018.png" />. In these cases the calculation of a maximum (*) analytically is difficult and it must be found by numerical methods (see [[Maximin, numerical methods|Maximin, numerical methods]]). The above also applies to finding the minimax.
+
Finding a maximin as a mathematical operation formally consists in the successive calculation of extrema, that is, in the solution of standard ("single-criterion") optimal programming problems, and, therefore, involves no conceptual complications. However, even when $Y$ is  "well arranged"  and the function $F$ is uniformly continuous on $X$, the function which associates to $x$ the value of $y$ at which the extremum $\inf_{y\in Y}F(x,y)$ is attained (or  "almost attained") can turn out to be  "badly arranged"  and, in particular, can be a discontinuous function of $x$. In these cases the calculation of a maximum \ref{*} analytically is difficult and it must be found by numerical methods (see [[Maximin, numerical methods|Maximin, numerical methods]]). The above also applies to finding the minimax.
  
  

Revision as of 18:17, 14 August 2014

The mixed extrema

$$\sup_{x\in X}\inf_{y\in Y}F(x,y),\quad\max_{x\in X}\min_{y\in Y}F(x,y),\quad\text{etc.}\tag{*}$$

A maximin can be interpreted (for example, in decision theory, operations research or game theory, cf. Games, theory of) as the greatest gain among those that can be attained by decision making under the worst conditions; it is, thereby, a guaranteed gain. Therefore, decision making oriented on a maximin may reasonably be regarded as optimal.

The value of a maximin does not exceed the value of the corresponding minimax. Conditions for their equality are very important in game theory (see Minimax principle). Such conditions are, for example, the presence of a linear structure in $X$, the convexity of $X$ and the concavity of the function $F$ relative to $x\in X$ for each $y\in Y$ (or, the linearity of $X$ and convexity of $Y$, and convexity of $F$ relative to $y\in Y$ for each $x\in X$).

Finding a maximin as a mathematical operation formally consists in the successive calculation of extrema, that is, in the solution of standard ("single-criterion") optimal programming problems, and, therefore, involves no conceptual complications. However, even when $Y$ is "well arranged" and the function $F$ is uniformly continuous on $X$, the function which associates to $x$ the value of $y$ at which the extremum $\inf_{y\in Y}F(x,y)$ is attained (or "almost attained") can turn out to be "badly arranged" and, in particular, can be a discontinuous function of $x$. In these cases the calculation of a maximum \ref{*} analytically is difficult and it must be found by numerical methods (see Maximin, numerical methods). The above also applies to finding the minimax.


Comments

See also (references

and

to) Maximin, numerical methods.

How to Cite This Entry:
Maximin. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Maximin&oldid=32924
This article was adapted from an original article by N.N. Vorob'ev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article