Démonstrations du théorème du minimax

Démonstrations du théorème du minimax
Article principal : Théorème du minimax de von Neumann.

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_{Y\in\Delta_n}\min_{X\in\Delta_k}Y^TAX\leqslant\min_{X\in\Delta_k}\max_{Y\in\Delta_n}Y^TAX, information signalée dans l'article principal qu'on supposera donc connue ici.

Sommaire

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[Note 1].


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é YTAX 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 Cj (1\leqslant j\leqslant k) les colonnes de la matrice A et Ei (1\leqslant i \leqslant n) la base canonique. Introduisons K enveloppe convexe des Cj et des Ei : K est un convexe compact. Soit enfin Y1 la projection de 0 sur ce convexe fermé.


1er cas : si Y1 = 0. Ceci signifie que 0\in K. Il existe donc des réels positifs ou nuls αj et βi dont un au moins n'est pas nul et pour lesquels \sum_{1\leqslant j\leqslant k}\alpha_jC_j+\sum_{1\leqslant i \leqslant n}\beta_i E_i=0, ce qui se réécrit \sum_{1\leqslant j\leqslant k}\alpha_jC_j=\begin{pmatrix}-\beta_1&\ldots&-\beta_n\end{pmatrix}^T\quad (*).

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 X_0=({\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})^T. L'identité ( * ) assure alors que AX0 est à coefficients négatifs ou nuls. Chaque vecteur Y\in\Delta_n étant à coefficients positifs ou nuls, le produit matriciel YTAX0 est donc négatif ou nul. Par conséquent le maximum \max_{Y\in\Delta_n}Y^TAX_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^TAX_0, est lui aussi négatif ou nul.


2nd cas : si Y_1\not=0, notons Y_1=\begin{pmatrix}\gamma_1&\ldots&\gamma_n\end{pmatrix}^T. Pour chaque i, puisque Y1 est la projection de 0 sur K et que Ei est un élément de K, on peut écrire l'inégalité <Y_1-0\, ,\, Y_1-E_i>\leqslant 0 dont on déduit \|Y_1\|^2\leqslant\gamma_i : le vecteur Y1 est donc à coefficients strictement positifs. En exploitant de même pour chaque j l'inégalité <Y_1-0\, ,\, Y_1-C_j>\leqslant 0, on constate que chaque <Y_1\,,\,C_j> est un réel strictement positif, et donc que le vecteur Y_1^tA=\begin{pmatrix}<Y_1\,,\,C_1>&\ldots&<Y_1\,,\,C_k>\end{pmatrix} est à coefficients strictement 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 Δn pour lequel le vecteur ligne Y_0^tA est à coefficients strictement positifs. On finit alors comme au premier cas : on en déduit successivement que chaque produit Y_0^tA est un réel strictement positif, puis que le minimum \min_{X\in\Delta_k}Y^TAX est strictement positif, et enfin que le maximin est lui aussi strictement 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\R^p, l'écriture u\leqslant v signifie que u_i\leqslant v_i pour tout indice i,
  • \Delta_p:=\{z\in\R^p:~e^\top z=1,~z\geqslant 0\} désigne le simplexe unité de \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 α [resp. β] 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 α > 0 et β > 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\R^n: y\geqslant 0,~ e^\top y=1,~ A^\top y\leqslant te \qquad[\mbox{observation 2}] \\&\iff& \exists\, y\in\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 / β, 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é.

Notes

  1. ↑ On a privilégié la concision à l'intuition géométrique dans la rédaction de la preuve ; le lecteur intéressé pourra trouver une présentation du principe de cette preuve qui met davantage en relief les idées géométriques sous-jacentes dans (en) Jörg Bewersdorff et David Kramer, Luck, Logic, and White Lies, Wellesley, A K Peters, Ltd., 2005, poche (ISBN 978-1-56881-210-6), p. p. 369-372 

Bibliographie

  • Michel Willem, Analyse convexe et optimisation, 136 pages, Bruxelles, Edition CIACO, 1989. (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 ).

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Démonstrations du théorème du minimax de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Théorème du minimax — de von Neumann John von Neumann …   Wikipédia en Français

  • Théorème du minimax de von Neumann — John von Neumann Vers où faut il …   Wikipédia en Français

  • Théorème fondamental de la théorie des jeux — Théorème du minimax de von Neumann John von Neumann …   Wikipédia en Français

  • Theoreme de projection sur un convexe ferme — Théorème de projection sur un convexe fermé En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance qui généralise la projection orthogonale sur un espace vectoriel. Il remplace… …   Wikipédia en Français

  • Théorème de projection orthogonale sur un convexe — Théorème de projection sur un convexe fermé En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance qui généralise la projection orthogonale sur un espace vectoriel. Il remplace… …   Wikipédia en Français

  • Théorème de projection sur un convexe fermé — En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance dont le principal corollaire est l existence d un supplémentaire orthogonal, donc d une projection orthogonale sur un sous… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • NEUMANN (J. von) — L’œuvre du mathématicien John von Neumann est remarquable par la très grande variété de son champ et par l’unité conceptuelle qui s’en dégage. Héritier de Hilbert et de l’école formaliste, il sut, de ses premières recherches sur l’axiomatisation… …   Encyclopédie Universelle

  • SYSTÈMES DYNAMIQUES DIFFÉRENTIABLES — Sans doute née avec le mémoire que Poincaré écrivit en 1881 «sur les courbes définies par des équations différentielles», où l’étude quantitative (analytique) locale des équations différentielles dans le champ complexe est remplacée par leur… …   Encyclopédie Universelle

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”