Maximin, numerical methods

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)