Namespaces
Variants
Actions

Difference between revisions of "Maximin, numerical methods"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
m0630401.png
 +
$#A+1 = 50 n = 0
 +
$#C+1 = 50 : ~/encyclopedia/old_files/data/M063/M.0603040 Maximin, numerical methods
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
The branch of computational mathematics devoted to the solution of maximin (minimax) problems. Problems of calculating maximins and minimaxes often arise in [[Operations research|operations research]] and in game theory (cf. [[Games, theory of|Games, theory of]]), for example, from the [[Minimax principle|minimax principle]] or from the [[Principle of the largest sure result|principle of the largest sure result]].
 
The branch of computational mathematics devoted to the solution of maximin (minimax) problems. Problems of calculating maximins and minimaxes often arise in [[Operations research|operations research]] and in game theory (cf. [[Games, theory of|Games, theory of]]), for example, from the [[Minimax principle|minimax principle]] or from the [[Principle of the largest sure result|principle of the largest sure result]].
  
 
First there is the problem of calculating the maximin
 
First there is the problem of calculating the maximin
  
<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/m063040/m0630401.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\sup _ {x \in X } \
 +
\inf _ {y \in Y } \
 +
F ( x , y ) ,
 +
$$
  
 
which arises, for example, in the solution of two-person zero-sum games with complete information. A natural generalization of it is the problem of finding a maximin with  "constrained"  variables:
 
which arises, for example, in the solution of two-person zero-sum games with complete information. A natural generalization of it is the problem of finding a maximin with  "constrained"  variables:
  
<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/m063040/m0630402.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
\sup _ {x \in X }  \inf _
 +
{y \in B ( x) }  F ( x , y ) ,
 +
$$
  
where the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m0630403.png" /> is often given in the form
+
where the set $  B ( x) $
 +
is often given in the form
  
<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/m063040/m0630404.png" /></td> </tr></table>
+
$$
 +
B ( x)  = \{ {y \in Y } : {\phi ( x , y ) \geq  0 } \}
 +
\neq  \emptyset
 +
$$
  
for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m0630405.png" />. This problem is fundamental in the theory of two-person games with exchange of information (see, for example, [[Game with a hierarchy structure|Game with a hierarchy structure]]). Iteration of the first problem leads to a multiple or sequential maximin problem:
+
for each $  x \in X $.  
 +
This problem is fundamental in the theory of two-person games with exchange of information (see, for example, [[Game with a hierarchy structure|Game with a hierarchy structure]]). Iteration of the first problem leads to a multiple or sequential maximin problem:
  
<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/m063040/m0630406.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
\sup _ {x _ {1} \in X _ {1} } \
 +
\inf _ {y _ {1} \in Y _ {1} } \dots
 +
\sup _ {x _ {n} \in X _ {n} } \
 +
\inf _ {y _ {n} \in Y _ {n} } \
 +
F ( x _ {1} , y _ {1} \dots x _ {n} , y _ {n} ) ,
 +
$$
  
 
which is related to the solution of certain dynamical games. Stochastic problems of calculating a maximin and also minimax problems of optimal control are of interest.
 
which is related to the solution of certain dynamical games. Stochastic problems of calculating a maximin and also minimax problems of optimal control are of interest.
Line 21: Line 51:
 
The basis of most methods for solving minimax problems is the [[Gradient method|gradient method]] or the method of penalty functions (cf. [[Penalty functions, method of|Penalty functions, method of]]). In the first of these, (1) is regarded as a problem in optimal programming:
 
The basis of most methods for solving minimax problems is the [[Gradient method|gradient method]] or the method of penalty functions (cf. [[Penalty functions, method of|Penalty functions, method of]]). In the first of these, (1) is regarded as a problem in optimal programming:
  
<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/m063040/m0630407.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
\sup _ {x \in X }  f ( x) ,
 +
$$
  
 
where
 
where
  
<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/m063040/m0630408.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$ \tag{5 }
 +
f ( x)  = \
 +
\inf _ {y \in Y } \
 +
F ( x , y ) .
 +
$$
  
 
The construction of numerical methods for solving (4)–(5) is connected with directional differentiability of the minimum function (5).
 
The construction of numerical methods for solving (4)–(5) is connected with directional differentiability of the minimum function (5).
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m0630409.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304010.png" /> is a compact set in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304011.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304012.png" /> is the derivative in the direction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304013.png" /> (see [[#References|[1]]]–[[#References|[3]]]),
+
If $  X \subset  \mathbf R  ^ {n} $,  
 +
if $  Y $
 +
is a compact set in $  \mathbf R  ^ {n} $
 +
and if $  \partial  f ( x) / \partial  g $
 +
is the derivative in the direction $  g \in \mathbf R  ^ {n} $(
 +
see [[#References|[1]]]–[[#References|[3]]]),
 +
 
 +
$$ \tag{6 }
 +
\left .
 +
\begin{array}{c}
 +
{} \\
 +
 
 +
\frac{\partial  f ( x) }{\partial  g }
 +
  = \
 +
\min _ {y \in Y ( x) }
 +
\left (
 +
 
 +
\frac \partial {\partial  x }
 +
 
 +
F ( x , y ) , g
 +
\right ) ,
 +
\\
  
<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/m063040/m06304014.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>
+
Y ( x)  = \{ {y \in Y } : {
 +
F ( x , y ) = f ( x) } \}
 +
,
 +
 +
\end{array}
 +
\right \}
 +
$$
  
then for a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304015.png" /> formula (6) allows one to construct an iterative sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304016.png" /> in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304017.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304018.png" /> and which, under certain additional restrictions, converges to a point satisfying the necessary condition for a maximin.
+
then for a finite set $  Y $
 +
formula (6) allows one to construct an iterative sequence $  x _ {1} , x _ {2} \dots $
 +
in which $  x _ {k+} 1 = x _ {k} + \alpha _ {k} g _ {k} $
 +
for $  k = 0 , 1 \dots $
 +
and which, under certain additional restrictions, converges to a point satisfying the necessary condition for a maximin.
  
In the method of penalty functions the problem (1), for a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304019.png" /> that is continuous on the product of a compact set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304020.png" /> and the unit cube <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304021.png" />, reduces to finding
+
In the method of penalty functions the problem (1), for a function $  F ( x , y ) $
 +
that is continuous on the product of a compact set $  X \subset  \mathbf R  ^ {n} $
 +
and the unit cube $  Y \subset  \mathbf R  ^ {m} $,  
 +
reduces to finding
  
<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/m063040/m06304022.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {c \rightarrow \infty } \
 +
\max _ {x,u \in X } \
 +
{\mathcal L} ( x , u , c ) ,
 +
$$
  
 
where
 
where
  
<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/m063040/m06304023.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>
+
$$ \tag{7 }
 +
{\mathcal L} ( x , u , c )  = \
 +
u - c \int\limits _ { Y }
 +
( \min ( 0 , F ( x , y ) - u ) )  ^ {2}  d y
 +
$$
 +
 
 +
( $  u $
 +
is an auxiliary variable). Here, if a pair  $  ( u ( c) , c ( c) ) $
 +
realizes the maximum
 +
 
 +
$$
 +
\max _ { {u , x \in X } } \
 +
{\mathcal L} ( x , u , c ) ,
 +
$$
 +
 
 +
then any limit point  $  ( u  ^ {*} , x  ^ {*} ) $
 +
of the sequence  $  \{ {( u ( c _ {k} ) , x ( c _ {k} ) ) } : {c _ {k} \rightarrow \infty } \} $
 +
gives
 +
 
 +
$$
 +
u  ^ {*}  = \
 +
\max _ {x \in X } \
 +
\min _ {y \in Y } \
 +
F ( x , y )
 +
$$
 +
 
 +
as the maximin of (1) and one of the optimal strategies  $  x  ^ {*} $
 +
for which
 +
 
 +
$$
 +
u  ^ {*}  = \
 +
\min _ {y \in Y } \
 +
F ( x  ^ {*} , y )
 +
$$
  
(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304024.png" /> is an auxiliary variable). Here, if a pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304025.png" /> realizes the maximum
+
(see [[#References|[4]]]). Thereby the solution of (1), up to arbitrary accuracy, reduces to the search for the maximum of the function (7) for sufficiently large values of the penalty  $  c $.  
 +
To avoid difficulties connected with the calculation of the integrals in (7), the stochastic gradient method is used (see [[#References|[5]]], [[#References|[8]]]):
  
<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/m063040/m06304026.png" /></td> </tr></table>
+
$$ \tag{8 }
 +
\left .
 +
\begin{array}{c}
  
then any limit point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304027.png" /> of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304028.png" /> gives
+
x _ {k+} 1  = x _ {k} + \alpha _ {k} \xi _ {k} ( c _ {k} ) ,
 +
\\
  
<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/m063040/m06304029.png" /></td> </tr></table>
+
u _ {k+} 1  = u _ {k} + \alpha _ {k} \eta _ {k} ( c _ {k} ) ,
 +
 +
\end{array}
 +
\right \} \ \
 +
k = 1 , 2 \dots
 +
$$
  
as the maximin of (1) and one of the optimal strategies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304030.png" /> for which
+
where  $  ( \xi _ {k} ( c _ {k} ) , \eta _ {k} ( c _ {k} ) ) $
 +
is the stochastic gradient of $  {\mathcal L} ( x , u , c ) $,
 +
that is, a random variable whose mathematical expectation is
  
<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/m063040/m06304031.png" /></td> </tr></table>
+
$$
 +
\left (
  
(see [[#References|[4]]]). Thereby the solution of (1), up to arbitrary accuracy, reduces to the search for the maximum of the function (7) for sufficiently large values of the penalty <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304032.png" />. To avoid difficulties connected with the calculation of the integrals in (7), the stochastic gradient method is used (see [[#References|[5]]], [[#References|[8]]]):
+
\frac \partial {\partial  x }
  
<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/m063040/m06304033.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>
+
{\mathcal L} ( x _ {k} , u _ {k} , c _ {k} ) ,\
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304034.png" /> is the stochastic gradient of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304035.png" />, that is, a random variable whose mathematical expectation is
+
\frac \partial {\partial  u }
  
<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/m063040/m06304036.png" /></td> </tr></table>
+
{\mathcal L} ( x _ {k} , u _ {k} , c _ {k} )
 +
\right ) .
 +
$$
  
Under certain conditions on the sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304038.png" /> and the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304039.png" />, for any first approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304040.png" /> the sequence defined by (8) converges with probability 1 to the set of solutions of the maximin problem (1).
+
Under certain conditions on the sequences $  \{ \alpha _ {k} \} $
 +
and $  \{ c _ {k} \} $
 +
and the function $  F ( x , y ) $,
 +
for any first approximation $  ( x _ {1} , y _ {1} ) $
 +
the sequence defined by (8) converges with probability 1 to the set of solutions of the maximin problem (1).
  
To avoid large values of the penalty <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304041.png" /> in (7), the so-called  "method of discrepanciesmethod of discrepancies"  is used (see [[#References|[6]]]), which is another method of transforming the problem (1). Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304042.png" />, the maximin of (1), is defined as the maximum value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304043.png" /> for which
+
To avoid large values of the penalty $  c $
 +
in (7), the so-called  "method of discrepanciesmethod of discrepancies"  is used (see [[#References|[6]]]), which is another method of transforming the problem (1). Here $  u  ^ {*} $,  
 +
the maximin of (1), is defined as the maximum value of $  u $
 +
for which
  
<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/m063040/m06304044.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>
+
$$ \tag{9 }
 +
\min _ {x \in X } \
 +
\Phi ( x , u )  = 0 ,
 +
$$
  
 
where
 
where
  
<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/m063040/m06304045.png" /></td> </tr></table>
+
$$
 +
\Phi ( x , y )  = \
 +
\int\limits _ { Y }
 +
( \min ( 0 , F ( x , y ) - u ) )
 +
^ {2}  d y .
 +
$$
  
Here the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304046.png" /> that realizes
+
Here the value $  x  ^ {*} $
 +
that realizes
  
<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/m063040/m06304047.png" /></td> </tr></table>
+
$$
 +
\min _ {x \in X } \
 +
\Phi ( x , u  ^ {*} )
 +
$$
  
is an optimal strategy for (1). In order to find the largest root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304048.png" /> of (9) it is possible to use gradient methods for minimizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304049.png" /> relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304050.png" />.
+
is an optimal strategy for (1). In order to find the largest root $  u  ^ {*} $
 +
of (9) it is possible to use gradient methods for minimizing $  \Phi $
 +
relative to $  x $.
  
 
The transformation methods based on the method of penalty functions permit the approximate reduction of the minimax problem with constrained variables (2) to a maximum problem (see [[#References|[7]]], [[#References|[8]]]).
 
The transformation methods based on the method of penalty functions permit the approximate reduction of the minimax problem with constrained variables (2) to a maximum problem (see [[#References|[7]]], [[#References|[8]]]).

Latest revision as of 08:00, 6 June 2020


The branch of computational mathematics devoted to the solution of maximin (minimax) problems. Problems of calculating maximins and minimaxes often arise in operations research and in game theory (cf. Games, theory of), for example, from the minimax principle or from the principle of the largest sure result.

First there is the problem of calculating the maximin

$$ \tag{1 } \sup _ {x \in X } \ \inf _ {y \in Y } \ F ( x , y ) , $$

which arises, for example, in the solution of two-person zero-sum games with complete information. A natural generalization of it is the problem of finding a maximin with "constrained" variables:

$$ \tag{2 } \sup _ {x \in X } \inf _ {y \in B ( x) } F ( x , y ) , $$

where the set $ B ( x) $ is often given in the form

$$ B ( x) = \{ {y \in Y } : {\phi ( x , y ) \geq 0 } \} \neq \emptyset $$

for each $ x \in X $. This problem is fundamental in the theory of two-person games with exchange of information (see, for example, Game with a hierarchy structure). Iteration of the first problem leads to a multiple or sequential maximin problem:

$$ \tag{3 } \sup _ {x _ {1} \in X _ {1} } \ \inf _ {y _ {1} \in Y _ {1} } \dots \sup _ {x _ {n} \in X _ {n} } \ \inf _ {y _ {n} \in Y _ {n} } \ F ( x _ {1} , y _ {1} \dots x _ {n} , y _ {n} ) , $$

which is related to the solution of certain dynamical games. Stochastic problems of calculating a maximin and also minimax problems of optimal control are of interest.

The basis of most methods for solving minimax problems is the gradient method or the method of penalty functions (cf. Penalty functions, method of). In the first of these, (1) is regarded as a problem in optimal programming:

$$ \tag{4 } \sup _ {x \in X } f ( x) , $$

where

$$ \tag{5 } f ( x) = \ \inf _ {y \in Y } \ F ( x , y ) . $$

The construction of numerical methods for solving (4)–(5) is connected with directional differentiability of the minimum function (5).

If $ X \subset \mathbf R ^ {n} $, if $ Y $ is a compact set in $ \mathbf R ^ {n} $ and if $ \partial f ( x) / \partial g $ is the derivative in the direction $ g \in \mathbf R ^ {n} $( see [1][3]),

$$ \tag{6 } \left . \begin{array}{c} {} \\ \frac{\partial f ( x) }{\partial g } = \ \min _ {y \in Y ( x) } \left ( \frac \partial {\partial x } F ( x , y ) , g \right ) , \\ Y ( x) = \{ {y \in Y } : { F ( x , y ) = f ( x) } \} , \end{array} \right \} $$

then for a finite set $ Y $ formula (6) allows one to construct an iterative sequence $ x _ {1} , x _ {2} \dots $ in which $ x _ {k+} 1 = x _ {k} + \alpha _ {k} g _ {k} $ for $ k = 0 , 1 \dots $ and which, under certain additional restrictions, converges to a point satisfying the necessary condition for a maximin.

In the method of penalty functions the problem (1), for a function $ F ( x , y ) $ that is continuous on the product of a compact set $ X \subset \mathbf R ^ {n} $ and the unit cube $ Y \subset \mathbf R ^ {m} $, reduces to finding

$$ \lim\limits _ {c \rightarrow \infty } \ \max _ {x,u \in X } \ {\mathcal L} ( x , u , c ) , $$

where

$$ \tag{7 } {\mathcal L} ( x , u , c ) = \ u - c \int\limits _ { Y } ( \min ( 0 , F ( x , y ) - u ) ) ^ {2} d y $$

( $ u $ is an auxiliary variable). Here, if a pair $ ( u ( c) , c ( c) ) $ realizes the maximum

$$ \max _ { {u , x \in X } } \ {\mathcal L} ( x , u , c ) , $$

then any limit point $ ( u ^ {*} , x ^ {*} ) $ of the sequence $ \{ {( u ( c _ {k} ) , x ( c _ {k} ) ) } : {c _ {k} \rightarrow \infty } \} $ gives

$$ u ^ {*} = \ \max _ {x \in X } \ \min _ {y \in Y } \ F ( x , y ) $$

as the maximin of (1) and one of the optimal strategies $ x ^ {*} $ for which

$$ u ^ {*} = \ \min _ {y \in Y } \ F ( x ^ {*} , y ) $$

(see [4]). Thereby the solution of (1), up to arbitrary accuracy, reduces to the search for the maximum of the function (7) for sufficiently large values of the penalty $ c $. To avoid difficulties connected with the calculation of the integrals in (7), the stochastic gradient method is used (see [5], [8]):

$$ \tag{8 } \left . \begin{array}{c} x _ {k+} 1 = x _ {k} + \alpha _ {k} \xi _ {k} ( c _ {k} ) , \\ u _ {k+} 1 = u _ {k} + \alpha _ {k} \eta _ {k} ( c _ {k} ) , \end{array} \right \} \ \ k = 1 , 2 \dots $$

where $ ( \xi _ {k} ( c _ {k} ) , \eta _ {k} ( c _ {k} ) ) $ is the stochastic gradient of $ {\mathcal L} ( x , u , c ) $, that is, a random variable whose mathematical expectation is

$$ \left ( \frac \partial {\partial x } {\mathcal L} ( x _ {k} , u _ {k} , c _ {k} ) ,\ \frac \partial {\partial u } {\mathcal L} ( x _ {k} , u _ {k} , c _ {k} ) \right ) . $$

Under certain conditions on the sequences $ \{ \alpha _ {k} \} $ and $ \{ c _ {k} \} $ and the function $ F ( x , y ) $, for any first approximation $ ( x _ {1} , y _ {1} ) $ the sequence defined by (8) converges with probability 1 to the set of solutions of the maximin problem (1).

To avoid large values of the penalty $ c $ in (7), the so-called "method of discrepanciesmethod of discrepancies" is used (see [6]), which is another method of transforming the problem (1). Here $ u ^ {*} $, the maximin of (1), is defined as the maximum value of $ u $ for which

$$ \tag{9 } \min _ {x \in X } \ \Phi ( x , u ) = 0 , $$

where

$$ \Phi ( x , y ) = \ \int\limits _ { Y } ( \min ( 0 , F ( x , y ) - u ) ) ^ {2} d y . $$

Here the value $ x ^ {*} $ that realizes

$$ \min _ {x \in X } \ \Phi ( x , u ^ {*} ) $$

is an optimal strategy for (1). In order to find the largest root $ u ^ {*} $ of (9) it is possible to use gradient methods for minimizing $ \Phi $ relative to $ x $.

The transformation methods based on the method of penalty functions permit the approximate reduction of the minimax problem with constrained variables (2) to a maximum problem (see [7], [8]).

The extremal problems obtained by reducing minimax problems to maximum problems are very complicated and their solution by known methods entails great, sometimes even insurmountable, difficulties for modern electronic computers. In particular, this makes the problem of finding a sequential maximin (3) very difficult. Together with these general approaches to the solution of minimax problems there are a number of methods orientated towards particular classes of problems; for example, to problems of the theory of two-person games and transmission of information (see [6]).

References

[1] V.F. Dem'yanov, V.N. Malozemov, "Introduction to minimax" , Wiley (1974) (Translated from Russian)
[2] J.M. Danskin, "The theory of max-min and its application to weapons allocation problems" , Springer (1967)
[3] V.F. Dem'yanov, L.V. Vasil'ev, "Non-differentiable optimization" , Optim. Software (1985) (Translated from Russian)
[4] Yu.B. Germeier, "Introduction to the theory of operations research" , Moscow (1971) (In Russian)
[5] Yu.M. Ermol'ev, "Methods of stochastic programming" , Moscow (1976) (In Russian)
[6] Yu.B. Germeier, "Non-antagonistic games" , Reidel (1986) (Translated from Russian)
[7] F.I. Ereshko, A.S. Zlobin, "An algorithm for centralized resource distribution among active subsystems" Ekonomika i Mat. Metody , 13 : 4 (1977) pp. 703–713 (In Russian)
[8] V.V. Fedorov, "Numerical maximin methods" , Moscow (1979) (In Russian)
How to Cite This Entry:
Maximin, numerical methods. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Maximin,_numerical_methods&oldid=17852
This article was adapted from an original article by V.V. Fedorov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article