Cette première partie demande une bonne maîtrise de la fin du cours de deuxième année. Il s'avère donc très difficile pour les prépas qui l'ont abordé tardivement.
On a vite fait de s'empêtrer à essayer de rédiger proprement le b) de l'Exemple 1. Mon conseil est donc d'essayer de la comprendre mais de ne pas perdre de temps à essayer de la rédiger. Quand ça bloque, pas de scrupules : avancer!
Ce sujet traite un cas particulier du théorème d'équilibre de Nash. Ce théorème est célèbre dans le monde des matheux et des économistes, il a d'ailleurs valu le prix Nobel d'économie à John Nash en 1994. Pour faire simple, il dit que si on considère un jeu à plusieurs joueurs, il existe toujours une stratégie pour optimise les gains (voir les pertes) de tous les joueurs. Si cela vous intéresse, l'article de wikipédia donne quelques explications simples avec des exemples de jeux et les implications de ce théorème.
Dans le sujet, les mises des joueurs sont représentées par un vecteur $(x_1,\dots,x_n)$, où $x_i$ est la mise du joueur i. Ces mises sont soumises à une contrainte en restant dans un ensemble donné. Par exemple dans la partie II, on impose $\sum_{i=1}^n\alpha_ix_i^2\leq 1$. On voit dans cette formule qui si par exemple le joueur 1 mise beaucoup, cela va pénaliser tous les autres joueurs. La question est donc de savoir si il existe une stratégie de coopération qui permette de maximiser les opportunités de gains de tous les joueurs. Le sujet donne un cadre particulier dans lequel une telle stratégie existe et est unique et cerise sur le gateaux, il donne un moyen de la calculer!
Dans tous le problème, $n$ désigne un entier supérieur ou égal à 2, et $\mathbb R^n$ est muni de sa structure Euclidienne canonique. Le produit scalaire et la norme associée sont notés respectivement $\langle,\rangle$ et $\Vert\ \Vert$. Pour tous vecteurs $x=(x_1,x_2,\dots,x_n)$ et $y=(y_1,y_2,\dots,y_n)$ de $\mathbb R^n$, on note $x\geq y$ si pour tout $i$ de $[\![1,n]\!]$, on a : $x_i\leq y_i$.
Le vecteur nul de $\mathbb R^n$ est noté $\vec 0$ et le vecteur de $\mathbb R^n$ dont toutes les composantes sont égales à 1 est noté $\vec 1$.
On rappelle ou on admet les deux résultats suivants :
On dit qu'un vecteur $h$ de $\mathbb R^n$ sépare deux convexes $K_1$ et $K_2$, s'il existe un réel $c$ qui vérifie, pour tous vecteurs $u$ de $K_1$ et $v$ de $K_2$, l'encadrement : $\langle h,u\rangle<\ c<\ \langle h,v\rangle$.
Si $K$ est une partie non vide et convexe de $\mathbb R^n$, et $x$ un vecteur de $\mathbb R^n$, on appelle projection de $x$ sur $K$ et on note $p(x)$ s'il existe, tout vecteur $y$ de $K$ qui vérifie, pour tout vecteur $z$ de $K$ : $\Vert x-y\Vert\leq\Vert x-z\Vert$, c'est à dire tel que $\displaystyle\Vert x-y\Vert=\min_{z\in K}\Vert x-z\Vert$.
1. Exemple 1.Soit $K$ le sous-ensemble de $\mathbb R^2$ défini par : $K=\{(z_1,z_2)\in\mathbb R^2/z_1\leq 1\ et\ z_2\leq 1\}$, et $(x_1,x_2)$ un vecteur donné de $\mathbb R^2$ n'appartenant pas à $K$ tel que $x_1>0$ et $x_2>0$.
a) Montrer que l'ensemble $K$ est convexe et fermé. $K$ est-il borné?
Convexité : Soient $(z_1,z_2)$ et $(z'_1,z'_2)$ deux points de $K$, qui vérifient donc $z_1\leq 1, z_2\leq 1, z'_1\leq 1, z'_2\leq 1$. Soit $t\in[0,1]$, on a donc : $$tz_1\leq t\ et\ tz_2\leq t$$ $$(1-t)z'_1\leq (1-t)\ et\ tz'_2\leq (1-t).$$ En sommant ces inégalités, on en déduit que : $$tz_1+(1-t)z'1\leq 1\ et \ tz_2+(1-t)2'1\leq 1,$$ soit encore $$t(z_1,z_2)+(1-t)(z'_1,z'_2)\in K.$$ Donc K est convexe.
Fermé : On observe que K peut aussi s'écrire comme : $$K=\{(z_1,z_2)\in\mathbb R^2/z_1\leq 1\}\cap \{(z_1,z_2)\in\mathbb R^2/z_2\leq 1\}.$$ Or si on note $p_1$ la projection définie par $p_1(z_1,z_2)=z_1$, on observe que : $$\{(z_1,z_2)\in\mathbb R^2/z_1\leq 1\}=p_1^{-1}(]-\infty,1]).$$ Or $p_1$ est continue donc d'après le rappel en préambule, $p_1^{-1}(]-\infty,1])$ est fermé. On montre de même en utilisant la projection (au sens linéaire du terme) sur la deuxième coordonnée que $\{(z_1,z_2)\in\mathbb R^2/z_2\leq 1\}$ est également fermé. Enfin comme l'intersection de deux fermés est un fermé, on en déduit que K est fermé.
Borné : K n'est pas borné, il suffit de considérer la suite $(-n,1)$ qui est dans K mais tend vers l'infini.
b) Etablir l'existence et l'unicité de la projection $p(x)$ de $x$ sur $K$. Déterminer cette projection.
Un petit dessin nous suggère que la projection de $x=(z_1,z_2)$ sur K a pour expression $y=(\min(1,z_1),\min(1,z_2))$. Pour le montrer rigoureusement, on commencera par montrer que y est bien dans K (ce qui est facile car ses deux coordonnées sont plus petites que 1), puis on pourra faire par exemple une étude de cas en fonction de la position de x par rapport à K.
Pour l'unicité, raisonner comme dans le cours sur les projections sur un espace vectoriel.
c) Faire une figure représentant le convexe $K$, un vecteur $x$ et la projection $p(x)$.
d) Ecrire une fonction Pascal d'en-tête distance(x_1,x_2) : real qui à tout vecteur $x=(x_1,x_2)$ de $\mathbb R^2$ n'appartenant pas à $K$ et tel que $x_1>0$, $x_2>0$, associe le réel $\Vert x-p(x)\Vert$.
e) Vérifier que pour tout vecteur $z$ de $K$, on a : $\langle z-p(x),x-p(x)\rangle\leq 0$.
Un calcul direct à partir de p(x) trouvé en b) fonctionne bien.
f) Montrer qu'il existe un réel $c$ qui vérifie, pour tout vecteur $z$ de $K$ : $\langle x-p(x),z\rangle <\! c<\! \langle x-p(x),x\rangle$.
Par calcul, on observe que $\langle x-p(x),z\rangle\leq (x_1-\min(x_1,1))+(x_2-\min(x_2,1))$ et que $\langle x-p(x),x\rangle>(x_1-\min(x_1,1))+(x_2-\min(x_2,1))$ (pour cette dernière inégalité, on n'oubliera pas que x n'est pas dans K, c'est à dire $x_1>1$ ou $x_2>1$). Comme cette dernière inégalité est stricte, il suffit de prendre c tel que $\langle x-p(x),x\rangle>c>(x_1-\min(x_1,1))+(x_2-\min(x_2,1))$.
2. Exemple 2. Soit $E$ un sous-espace vectoriel de $\mathbb R^n$, différent de $\{\vec 0\}$ et de $\mathbb R^n$.
a) Montrer que $E$ est une partie convexe de $\mathbb R^n$. On admet qu'elle est fermée.
Soient x et y dans E et $t\in[0,1]$. Comme E est un espace vectoriel, tx et (1-t)y sont dans E, et toujours car E est un espace vectoriel, tx+(1-t)y est dans E. Donc E est convexe.
b) Dans cette question, $E$ est l'ensemble des vecteurs $w=(w_1,w_2,w_3,w_4)$ de $\mathbb R^4$ qui vérifient l'équation : $w_1+w_2-w_3-w_4=0$. Soit $x=(x_1,x_2,x_3,x_4)$ un vecteur de $\mathbb R^4$ n'appartenant pas à $E$. Déterminer $\displaystyle\min_{w\in E}\Vert x-w\Vert$ et le vecteur $p(x)$.
On observe d'abord que l'équation $w_1+w_2-w_3-w_4=0$ s'écrit aussi $\langle (w_1,w_2,w_3,w_4),(1,1,-1,-1)\rangle=0$. Il suit que $E=\left(Vect(1,1,-1,-1)\right)^\bot$. D'autre part pour déterminer $\displaystyle\min_{w\in E}\Vert x-w\Vert$, on utilise le cours des projections orthogonales sur un espace vectoriel. Ce minimum est atteint par $x-p(x)$ où $p(x)$ est la projection orthogonale de x sur E. On sait que x-p(x) est orthogonal à E, donc colinéaire à $(1,1,-1,-1)$, d'où : $p(x)=x+\lambda(1,1,-1,-1)$. D'autre part $p(x)$ est dans E donc orthogonal à $(1,1,-1,-1)$, d'où : $0=\langle p(x),(1,1,-1,-1)\rangle=4\lambda+x_1+x_2-x_3-x_4$. On en déduit $\lambda$, p(x) et $\Vert x-p(x)\Vert$.
Cas général : Soit $K$ une partie convexe, fermée et non vide de $\mathbb R^n$, et $x$ un vecteur de $\mathbb R^n$ qui n'appartient pas à $K$.
3. Soit $f$ la fonction à valeurs réelles définies sur $K$ par : pour tout $z$ de $K$, $f(z)=\Vert x-z\Vert$.
a) Justifier la continuité de la fonction $f$.
On utilisera l'inégalité triangulaire inverse : $$|f(z)-f(z')|=|\Vert x-z\Vert-\Vert x-z'\Vert|\leq \Vert(x-z)-x-z'\Vert=\Vert z-z'\Vert.$$
b) Soit $z_0$ un vecteur quelconque de $K$. On considère la boule fermée $B_0$ de centre $x$ et de rayon $\Vert x-z_0\Vert$. On pose : $K'=B_0\cap K$. Justifier que $K'$ est une partie fermée et bornée de $\mathbb R^n$.
L'intersection de deux fermés est fermé donc K' est fermé. D'autre part $K'\subset B_0$ donc K' est borné.
c) En déduire que $f$ admet un minimum sur $K'$. Soit $\hat z$ tel que $\displaystyle f(\hat z)=\min_{z\in K'}f(z)$.
Une fonction continue sur un fermé borné de $\mathbb R^n$ est bornée et atteint ses bornes.
d) Montrer que l'inégalité $\Vert x-z\Vert \geq \Vert x-\hat z\Vert$ est satisfaite pour tout vecteur $z$ de $K$. Conclure.
Si z est dans $B_0\cap K$, l'inégalité à lieu d'après c), et si z est dans $K\backslash B_0$, utiliser le fait que z n'est pas dans $B_0$ c'est à dire $\Vert z-x\Vert>\Vert x-z_0\Vert$. Pour la conclusion, l'inégalité veut dire que $\hat z$ atteint le minimum : $\displaystyle\min_{z\in K}f(z)$.
4.a) Vérifier pour tous vecteur $a$ et $b$ de $\mathbb R^n$, l'identité : $\left\Vert x-\frac{a+b}{2}\right\Vert^2+\frac{1}{4}\Vert a-b\Vert^2=\frac{1}{2}\Vert x-a\Vert^2+\frac{1}{2}\Vert x-b\Vert^2$.
Utiliser à plein l'égalité : $\Vert x+y\Vert^2=\Vert x\Vert^2+2\langle x,y\rangle+\Vert y\Vert^2$.
b) On pose : $\displaystyle d=\min_{z\in K}\Vert x-z\Vert$. Soit $u$ et $v$ deux vecteurs de $K$ vérifiant $d=\Vert x-u\Vert=\Vert x-v\Vert$.
A l'aide de la question précédente, montrer que $u=v$. Conclure.
Dans 4.a), remplacer a par u et b par v. Si $u\neq v$, on en déduit que $\Vert x-\frac{u+v}{2}\Vert^2<\! d$. Or par convexité $\frac{u+v}{2}$ est dans $K$ ce qui est impossible par minimalité de d. On en déduit que u=v, c'est à dire l'unicité de la projection sur un convexe.
5. On rappelle que $p(x)$ désigne la projection du vecteur $x$ sur $K$.
a) Etablir pour tout vecteur $z$ de $K$ et pour tout réel $t$ de $[0,1]$, l'inégalité : $$\Vert x-p(x)\Vert^2\leq\Vert x-(tz+(1-t)p(x))\Vert^2.$$
Observer que z et p(x) sont dans K donc par convexité de K, tz+(1-t)p(x) est aussi dans K. L'inégalité suit de la définition de p(x) comme minimisant la distance au convexe.
b) En déduire pour tout $z$ de $K$, l'inégalité : $\langle z-p(x),x-p(x)\rangle\leq 0$.
On réorganise le membre de droite de l'inégalité établie en 5)a) sous la forme $\Vert x-p(x)-t(z-p(x))\Vert^2$ puis on développe la norme au carré à l'aide du produit scalaire. Après réorganisation et simplification par t, on fera tendre t vers 0.
c) Réciproquement, on suppose qu'il existe un vecteur $y$ de $K$ tel que pour tout vecteur $z$ de $K$; on a : $\langle z-y,x-y\rangle\leq 0$. Montrer que $y=p(x)$. Conclure.
Partir du fait que $\Vert z-x\Vert^2=\Vert (z-y)+(y-x)\Vert^2$ puis développer la norme au carré. Grâce à l'inégalité, on en déduit que $\Vert x-y\Vert\leq \Vert z-x\Vert$ pour tout $z\in K$ et donc que $y=p(x)$. Il suit que $y$ est caractérisé par la propriété : $\forall z\in K,\ \langle z-p(x),x-p(x)\rangle\leq 0$
d) Etablir l'inégalité : $\langle x-p(x),p(x)\rangle < \langle x-p(x),x\rangle$. Montrer que $x-p(x)$ sépare les ensembles $K$ et $\{x\}$.
Séparation des convexes : On part de l'inégalité de b) et par linéarité à gauche du produit scalaire, on a $$\forall z\in K,\ \langle z,x-p(x)\rangle\leq \langle p(x),x-p(x)\rangle.$$ Grâce à l'inégalité stricte établie précédemment on a aussi : $$\forall z\in K,\ \langle z,x-p(x)\rangle\leq \langle p(x),x-p(x)\rangle<\langle x-p(x),x\rangle.$$ Comme la seconde inégalité est stricte, on peut prendre c tel que $\langle p(x),x-p(x)\rangle<\! c<\langle x-p(x),x\rangle$. Il suit que : $$\forall z\in K,\ \langle z,x-p(x)\rangle<\! c<\langle x-p(x),x\rangle,$$ c'est à dire $x-p(x)$ sépare K et $\{x\}$.
Pour afficher le fil des commentaires : Commentaires.
Pour poster un commentaire ou obtenir de l'aide : c'est ici!
L'insertion de formules suit la syntaxe LATEX. Toute formule doit être encadrée par des dollars : $\bf{\$formule\$}$. Par exemple $\bf{\$ u\_n \$}$ sera interprétée comme une formule et donnera $\bf{u_n}$. Voici quelques exemples pour ceux qui ne sont pas habitués :
Contacter l'auteur du site : frederic.millet @ math-sup.fr