Cours et vidéos

Cours en ligne Vidéos classées

Concours corrigés

HECS
HECE

Programme de concours

HECS

Chaîne Youtube


Pour me soutenir



Autour du site

Auteur du site.

Corrigé HEC 2010

Thèmes abordés

Remarque

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.

Conseil

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!

Autour du sujet

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!


Partie I


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$.

Partie I. Projection sur un convexe fermé

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é?

Afficher

Référence programme : VI-0

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.

Afficher

Références programme : III-4, VI-0

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$.

Afficher

Référence programme : III-1.

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$.

Afficher

Référence programme : VI-0.

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.

Afficher

Référence programme : VI-0.

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)$.

Afficher

Références programme : III-1,2,4.

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$.

Afficher

Référence programme : VI-1.

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$.

Afficher

Référence programme : VI-0.

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)$.

Afficher

Référence programme : VI-1.

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.

Afficher

Référence programme : VI-0.

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$.

Afficher

Référence programme : III-1.

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.

Afficher

Référence programme : VI-0.

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.$$

Afficher

Référence programme : VI-0.

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$.

Afficher

Référence programme : III-1.

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.

Afficher

Référence programme : III-1.

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\}$.

Afficher

Référence programme : III-1.

Inégalité : Comme x n'est pas dans K, $x\neq p(x)$. Il suit que $\Vert x-p(x)\Vert^2>0$, soit encore $\langle x-p(x),x-p(x)\rangle >0$. On développe alors par linéarité à droite et on a : $\langle x-p(x),x\rangle-\langle x-p(x),p(x)\rangle>0$ et l'inégalité cherchée suit.

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!




Formulaire

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