Démonstrations du théorème du minimax

Cet article ne fait que recenser des preuves du théorème du minimax de John von Neumann. L'énoncé du théorème ainsi qu'une présentation globale de la variété de ses démonstrations sont disponibles dans l'article principal Théorème du minimax de von Neumann auquel on se réfèrera donc.

Toutes les preuves commencent par la même remarque, selon laquelle l'inégalité max-min $\max _{Y\in \Delta _{n}}\min _{X\in \Delta _{k}}Y^{T}AX\leqslant \min _{X\in \Delta _{k}}\max _{Y\in \Delta _{n}}Y^{T}AX$est satisfaite, information signalée dans l'article principal qu'on supposera donc connue ici.

Preuves par arguments de convexité

La preuve de Jean Ville

La preuve qui suit ci-dessous est une variante de celle de Jean Ville et n'utilise que des arguments de convexité élémentaires.

Supposons que l'inégalité entre le maximin et le minimax soit stricte, et introduisons une constante $c$ strictement comprise entre ces deux réels. Si on retranche $c$ à tous les coefficients de $A$, la quantité $Y^{T}AX$ est diminuée de $c$ pour chaque $(X,Y)\in \Delta _{k}\times \Delta _{n}$. Quitte à modifier $A$ de cette façon, on peut donc supposer $c=0$.

Il nous suffit ainsi de montrer qu'il est impossible que le maximin soit strictement négatif tandis que le minimax est strictement positif.

Dans l'espace des vecteurs-colonnes à $n$ entrées, notons $C_{j}$ ($1\leqslant j\leqslant k$) les colonnes de la matrice $A$ et $E_{i}$ ($1\leqslant i\leqslant n$) la base canonique. Introduisons K enveloppe convexe des $C_{j}$ et des $E_{i}$ : $K$ est un convexe compact. Soit enfin $Y_{1}$ la projection de $0$ sur ce convexe fermé.

1^er cas : $Y_{1}=0$. On va montrer que $\min _{X\in \Delta _{n}}\max _{Y\in \Delta _{n}}Y^{T}AX\leq 0$, ce qui impliquera via l'inégalité max-min que $\max _{Y\in \Delta _{n}}\min _{X\in \Delta _{n}}Y^{T}AX\leq 0$.

Si $Y_{1}=0$, ceci signifie que $0\in K$. Comme $K$est convexe, cela signifie qu'il existe des réels positifs ou nuls $\alpha _{j}$ et $\beta _{i}$ dont un au moins n'est pas nul et pour lesquels $\sum _{1\leqslant j\leqslant k}\alpha _{j}C_{j}+\sum _{1\leqslant i\leqslant n}\beta _{i}E_{i}=0$, ce qui se réécrit $\sum _{1\leqslant j\leqslant k}\alpha _{j}C_{j}={\begin{pmatrix}-\beta _{1}&\ldots &-\beta _{n}\end{pmatrix}}^{T}\quad (*)$.

Dans cette égalité il n'est pas possible que tous les $\alpha _{j}$ soient nuls (cela entraînerait la nullité de tous les $\beta _{i}$) et cela a donc un sens de considérer le vecteur $X_{0}=\left({\alpha _{1} \over \displaystyle \sum _{1\leqslant j\leqslant k}\alpha _{j}}\,\,\ldots \,\,{\alpha _{k} \over \displaystyle \sum _{1\leqslant j\leqslant k}\alpha _{j}}\right)^{T}$. L'identité $(*)$ assure alors que $AX_{0}$ est à coefficients négatifs ou nuls. Chaque vecteur $Y\in \Delta _{n}$ étant à coefficients positifs ou nuls, le produit matriciel $Y^{T}AX_{0}$ est donc négatif ou nul. Par conséquent le maximum $\max _{Y\in \Delta _{n}}Y^{T}AX_{0}$ est lui-même négatif ou nul, et enfin le minimax, qui est lui-même inférieur ou égal à $\max _{Y\in \Delta _{n}}Y^{T}AX_{0}$, est lui aussi négatif ou nul.

2^d cas : $Y_{1}\neq 0$. On va montrer que $\max _{Y\in \Delta _{n}}\min _{X\in \Delta _{n}}Y^{T}AX\geq 0$, ce qui impliquera via l'inégalité max-min que $\min _{X\in \Delta _{n}}\max _{Y\in \Delta _{n}}Y^{T}AX\geq 0$.

Notons $Y_{1}={\begin{pmatrix}\gamma _{1}&\ldots &\gamma _{n}\end{pmatrix}}^{T}$. Pour chaque $i$, puisque $Y_{1}$ est la projection de $0$ sur $K$ qui est convexe, et que $E_{i}$ est un élément de $K$, on peut écrire l'inégalité $\langle Y_{1}-0\,,\,Y_{1}-E_{i}\rangle \leqslant 0$ dont on déduit $\|Y_{1}\|^{2}\leqslant \gamma _{i}$ : le vecteur $Y_{1}$ est donc à coefficients strictement positifs. En exploitant de même pour chaque $j$ l'inégalité $\langle Y_{1}-0\,,\,Y_{1}-C_{j}\rangle \leqslant 0$, on constate que chaque $\langle Y_{1}\,,\,C_{j}\rangle$ est un réel positif, et donc que le vecteur ligne $Y_{1}^{T}A={\begin{pmatrix}\langle Y_{1}\,,\,C_{1}\rangle &\ldots &\langle Y_{1}\,,\,C_{k}\rangle \end{pmatrix}}$ est à coefficients positifs. Il n'y a plus qu'à introduire $Y_{0}={1 \over \displaystyle \sum _{1\leqslant i\leqslant n}\gamma _{i}}Y_{1}$ ; c'est un élément de $\Delta _{n}$ pour lequel le vecteur ligne $Y_{0}^{T}A$ est à coefficients positifs. On finit alors comme au premier cas : on en déduit successivement que pour tout $X\in \Delta _{n}$, $Y_{0}^{T}AX$ est un réel positif, et donc que $\min _{X\in \Delta _{n}}Y_{0}^{T}AX$ est un réel positif, et enfin que $\max _{Y\in \Delta _{n}}\min _{X\in \Delta _{n}}Y^{T}AX$ est positif.

Démonstration par la dualité en optimisation linéaire

On se référera à l'article Théorème du minimax de von Neumann pour de multiples informations sur le théorème et à l'article Optimisation linéaire pour les notations utilisées dans l'écriture des problèmes d'optimisation linéaire.

Notations :

• $e$ désigne un vecteur dont tous les éléments valent 1 et dont la dimension dépend du contexte,
• pour deux vecteurs $u$ et $v\in \mathbb {R} ^{p}$, l'écriture $u\leqslant v$ signifie que $u_{i}\leqslant v_{i}$ pour tout indice $i$,
• $\Delta _{p}:=\{z\in \mathbb {R} ^{p}:~e^{\top }z=1,~z\geqslant 0\}$ désigne le simplexe unité de $\mathbb {R} ^{p}$,
• $A$ est une matrice réelle de type $n\times k$.

Le théorème du minimax de von Neumann affirme que

$\max _{x\in \Delta _{k}}\min _{y\in \Delta _{n}}y^{\top }Ax=\min _{y\in \Delta _{n}}\max _{x\in \Delta _{k}}y^{\top }Ax$.

On note $\alpha$ [resp. $\beta$] le membre de gauche [resp. de droite] de cette identité que l'on va à présent démontrer.

Commençons par deux observations simples à démontrer :

1. quitte à augmenter d'une même quantité tous les coefficients de $A$, on peut supposer que $\alpha >0$ et $\beta >0$, ce que nous ferons,
2. $\max \,\{v^{\top }x:x\in \Delta _{k}\}$ est le plus grand élément de $v$ et $\min \,\{v^{\top }x:x\in \Delta _{k}\}$ est le plus petit élément de $v$.

Par ailleurs tous les problèmes d'optimisation dans l'identité de von Neumann ont une solution car on y minimise ou maximise des fonctions continues sur un simplexe (un compact non vide) ; pour le problème externe du membre de droite (le raisonnement est le même pour celui du membre de gauche), on utilise le fait que l'application $y\mapsto \max\{y^{\top }Ax:x\in \Delta _{k}\}$ est continue comme fonction convexe (enveloppe supérieure de fonctions convexes) ne prenant que des valeurs finies. L'utilisation des opérateurs $\min$ et $\max$ (au lieu de $\inf$ et $\sup$) est donc justifiée.

On peut alors écrire la suite d'équivalences suivantes :

${\begin{array}{rcl}\beta \leqslant t&\iff &\exists \,y\in \Delta _{n},~\max\{y^{\top }Ax:x\in \Delta _{k}\}\leqslant t\qquad [{\mbox{définition de}}~\beta ]\\&\iff &\exists \,y\in \mathbb {R} ^{n}:y\geqslant 0,~e^{\top }y=1,~A^{\top }y\leqslant te\qquad [{\mbox{observation 2}}]\\&\iff &\exists \,y\in \mathbb {R} ^{n}:y\geqslant 0,~e^{\top }y=1/t,~A^{\top }y\leqslant e\qquad [y\curvearrowright ty,~t>0]\\&\iff &1/t\leqslant \sup\{e^{\top }y:y\geqslant 0,~A^{\top }y\leqslant e\}.\end{array}}$

Dès lors

${\frac {1}{\beta }}=\max _{y\geqslant 0 \atop A^{\top }y\leqslant e}\,e^{\top }y.$

Il s'agit bien d'un $\max$, car ce problème d'optimisation linéaire est réalisable (par les équivalences ci-dessus) et borné (sa valeur optimale est $1/\beta$, qui est finie) ; il a donc une solution. Un calcul similaire montre que

${\frac {1}{\alpha }}=\min _{x\geqslant 0 \atop Ax\geqslant e}\,e^{\top }x.$

Par le résultat de dualité forte en optimisation linéaire (les deux problèmes d'optimisation linéaire sont duaux l'un de l'autre et ont une solution ; il n'y a donc pas de saut de dualité, ce qui veut dire que les valeurs optimales sont égales), on obtient alors

${\frac {1}{\beta }}=\max _{y\geqslant 0 \atop A^{\top }y\leqslant e}\,e^{\top }y=\min _{x\geqslant 0 \atop Ax\geqslant e}\,e^{\top }x={\frac {1}{\alpha }}.$

Le résultat est démontré.

Bibliographie

• Michel Willem, Analyse convexe et optimisation, Bruxelles, CIACO, 1989, 136 p. (ISBN 9782870852026). (Ce livre contient une démonstration du théorème du minimax à partir du théorème de dualité en optimisation linéaire ainsi que la démonstration de ce dernier.)