Démonstrations du théorème du minimax

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

Supposons que l'inégalité entre le maximin et le minimax soit stricte, et introduisons une constante ${\displaystyle c}$ strictement comprise entre ces deux réels. Si on retranche ${\displaystyle c}$ à tous les coefficients de ${\displaystyle A}$, la quantité ${\displaystyle Y^{T}AX}$ est diminuée de ${\displaystyle c}$ pour chaque ${\displaystyle (X,Y)\in \Delta _{k}\times \Delta _{n}}$. Quitte à modifier ${\displaystyle A}$ de cette façon, on peut donc supposer ${\displaystyle 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 à ${\displaystyle n}$ entrées, notons ${\displaystyle C_{j}}$ (${\displaystyle 1\leqslant j\leqslant k}$) les colonnes de la matrice ${\displaystyle A}$ et ${\displaystyle E_{i}}$ (${\displaystyle 1\leqslant i\leqslant n}$) la base canonique. Introduisons K enveloppe convexe des ${\displaystyle C_{j}}$ et des ${\displaystyle E_{i}}$ : ${\displaystyle K}$ est un convexe compact. Soit enfin ${\displaystyle Y_{1}}$ la projection de ${\displaystyle 0}$ sur ce convexe fermé.

1^er cas : ${\displaystyle Y_{1}=0}$. On va montrer que ${\displaystyle \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 ${\displaystyle \max _{Y\in \Delta _{n}}\min _{X\in \Delta _{n}}Y^{T}AX\leq 0}$.

Si ${\displaystyle Y_{1}=0}$, ceci signifie que ${\displaystyle 0\in K}$. Comme ${\displaystyle K}$est convexe, cela signifie qu'il existe des réels positifs ou nuls ${\displaystyle \alpha _{j}}$ et ${\displaystyle \beta _{i}}$ dont un au moins n'est pas nul et pour lesquels ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \alpha _{j}}$ soient nuls (cela entraînerait la nullité de tous les ${\displaystyle \beta _{i}}$) et cela a donc un sens de considérer le vecteur ${\displaystyle 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é ${\displaystyle (*)}$ assure alors que ${\displaystyle AX_{0}}$ est à coefficients négatifs ou nuls. Chaque vecteur ${\displaystyle Y\in \Delta _{n}}$ étant à coefficients positifs ou nuls, le produit matriciel ${\displaystyle Y^{T}AX_{0}}$ est donc négatif ou nul. Par conséquent le maximum ${\displaystyle \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 à ${\displaystyle \max _{Y\in \Delta _{n}}Y^{T}AX_{0}}$, est lui aussi négatif ou nul.

2^d cas : ${\displaystyle Y_{1}\neq 0}$. On va montrer que ${\displaystyle \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 ${\displaystyle \min _{X\in \Delta _{n}}\max _{Y\in \Delta _{n}}Y^{T}AX\geq 0}$.

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

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 :

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

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

${\displaystyle \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 ${\displaystyle \alpha }$ [resp. ${\displaystyle \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 ${\displaystyle A}$, on peut supposer que ${\displaystyle \alpha >0}$ et ${\displaystyle \beta >0}$, ce que nous ferons,
2. ${\displaystyle \max \,\{v^{\top }x:x\in \Delta _{k}\}}$ est le plus grand élément de ${\displaystyle v}$ et ${\displaystyle \min \,\{v^{\top }x:x\in \Delta _{k}\}}$ est le plus petit élément de ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \min }$ et ${\displaystyle \max }$ (au lieu de ${\displaystyle \inf }$ et ${\displaystyle \sup }$) est donc justifiée.

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

Dès lors

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

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

Le résultat est démontré.