View source for 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|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

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

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>

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

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

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:

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

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

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>

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]]]),

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

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.

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

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

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>

(<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

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

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

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

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

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

(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]]]):

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

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

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

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

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

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

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>

Here the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063040/m06304046.png" /> 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>

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

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 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 [[#References|[6]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.F. Dem'yanov,   V.N. Malozemov,   "Introduction to minimax" , Wiley  (1974)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J.M. Danskin,   "The theory of max-min and its application to weapons allocation problems" , Springer  (1967)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.F. Dem'yanov,   L.V. Vasil'ev,   "Non-differentiable optimization" , Optim. Software  (1985)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  Yu.B. Germeier,   "Introduction to the theory of operations research" , Moscow  (1971)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  Yu.M. Ermol'ev,   "Methods of stochastic programming" , Moscow  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.B. Germeier,   "Non-antagonistic games" , Reidel  (1986)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  V.V. Fedorov,   "Numerical maximin methods" , Moscow  (1979)  (In Russian)</TD></TR></table>