Démonstrations du théorème du minimax - Définition

Introduction

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é , 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^TAX est diminuée de c pour chaque . 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 ( ) les colonnes de la matrice A et E_i ( ) la base canonique. Introduisons K enveloppe convexe des C_j et des E_i : K est un convexe compact. Soit enfin Y₁ la projection de 0 sur ce convexe fermé.

1er cas : si Y₁ = 0. Ceci signifie que . Il existe donc des réels positifs ou nuls α_j et β_i dont un au moins n'est pas nul et pour lesquels , ce qui se réécrit .

Dans cette égalité il n'est pas possible que tous les α_j soient nuls (cela entraînerait la nullité de tous les β_i) et cela a donc un sens de considérer le vecteur . L'identité ( * ) assure alors que AX₀ est à coefficients négatifs ou nuls. Chaque vecteur étant à coefficients positifs ou nuls, le produit matriciel Y^TAX₀ est donc négatif ou nul. Par conséquent le maximum est lui-même négatif ou nul, et enfin le minimax, qui est lui-même inférieur ou égal à , est lui aussi négatif ou nul.

2nd cas : si , notons . Pour chaque i, puisque Y₁ est la projection de 0 sur K et que E_i est un élément de K, on peut écrire l'inégalité dont on déduit  : le vecteur Y₁ est donc à coefficients strictement positifs. En exploitant de même pour chaque j l'inégalité , on constate que chaque est un réel strictement positif, et donc que le vecteur est à coefficients strictement positifs. Il n'y a plus qu'à introduire  ; c'est un élément de Δ_n pour lequel le vecteur ligne est à coefficients strictement positifs. On finit alors comme au premier cas : on en déduit successivement que chaque produit est un réel strictement positif, puis que le minimum est strictement positif, et enfin que le maximin est lui aussi strictement positif.

Le théorème du minimax comme corollaire du théorème de dualité en programmation linéaire

On se réfèrera à l'article programmation linéaire pour l'énoncé du théorème et les notations utilisées dans l'écriture des programmes linéaires.

On note e la matrice colonne .

On rappelle qu'en programmation linéaire, pour deux matrices de même taille u et v, on convient de noter lorsque chaque coefficient de u est inférieur ou égal au coefficient correspondant de v.

Quitte à augmenter d'une même quantité tous les coefficients de A, on peut supposer le maximin strictement positif. On notera le maximin et le minimax . Ona donc supposé que , et on veut montrer que α = β

On remarque préalablement (c'est facile) que pour X fixé, n'est autre que le plus grand coefficient de AX.

Soit t un réel strictement positif. On peut écrire la suite d'équivalences suivantes :

avec max{entrées de

avec

avec (en posant )

Il apparaît à la suite de ce calcul que le minimax est l'inverse de la valeur du programme linéaire :

(on utilise ici les notations de l'article programmation linéaire).

Un calcul similaire montre que le maximin est l'inverse de la valeur du programme linéaire :

Le théorème de dualité en programmation linéaire garantit donc leur égalité.