2022-X-Ens-Psi-Corrigé

X–ENS 2022 — PSI — Mathématiques

Notations

Pour {x,y\in\mathbb R^d}, {x\cdot y=\sum\limits_{i=1}^dx_iy_i} est le produit scalaire usuel et {\|x\|=\sqrt{x\cdot x}} sa norme. Le segment {[x,y]} est l’ensemble des {\lambda x+(1-\lambda)y} pour {0\le\lambda\le1}.

Une partie est convexe lorsqu’elle contient tout segment joignant deux de ses points. Pour des parties non vides {A,B}, on pose {A+B=\{a+b:a\in A,b\in B\}} et {\lambda A=\{\lambda a:a\in A\}}. On écrit {A-B=A+(-B)} et {A-x=A-\{x\}}.

La dimension d’une partie non vide {A} est celle de {\operatorname{Vect}(A-a)}, pour un point quelconque {a\in A} ; c’est sa dimension affine.

On identifie une matrice réelle {M} à l’application linéaire qu’elle représente dans les bases canoniques. On note {\ker M}, {\operatorname{Im}M} et {M^T} son noyau, son image et sa transposée.

Les inégalités entre vecteurs sont comprises coordonnée par coordonnée ; {\mathbb R_+^k} est l’ensemble des vecteurs à coordonnées positives ou nulles. On rappelle que toute suite bornée de {\mathbb R^k} possède une sous-suite convergente.

Partie I — Projection et séparation

Projection

Soit {C} une partie non vide, convexe et fermée de {\mathbb R^d}, et {x\in\mathbb R^d}.

On considère {\inf_{y\in C}\|x-y\|^2.\tag{1}}

Séparation

Soient {C,D} deux convexes non vides de {\mathbb R^d}, avec {C} fermé et borné, {D} fermé, et {C\cap D=\varnothing}.

Partie II — Points extrémaux

Pour {E\subset\mathbb R^d}, son enveloppe convexe {\operatorname{co}(E)} est l’ensemble des combinaisons convexes finies {\sum_{i=1}^I\lambda_ix_i,\quad I\ge1,\quad x_i\in E,\quad\lambda_i\ge0,\quad\sum_{i=1}^I\lambda_i=1.} Pour un convexe non vide {A}, un point {x\in A} est extrémal si toute égalité {x=(1-\lambda)y+\lambda z}, avec {y,z\in A} et {0\lt \lambda\lt 1}, impose {y=z}. On note {\operatorname{Ext}(A)} l’ensemble de ces points.

Cas particuliers

Soient {x_1,\ldots,x_I\in A} et des poids {\lambda_i\ge0} de somme {1}.

Cas d’un convexe fermé borné

Dans les trois questions suivantes, {K} est un convexe non vide, fermé et borné de {\mathbb R^d}.

Partie III — Un résultat de dualité

Cônes convexes

Une partie {F} est un cône si {\lambda F\subset F} pour tout {\lambda\ge0}. Pour une partie non vide {E}, on définit {E^+=\{p:p\cdot x\ge0\text{ pour tout }x\in E\},\quad E^{++}=(E^+)^+.}

Programmation linéaire

Soient {M\in\mathcal M_{k\times d}(\mathbb R)}, {b\in\mathbb R^k} et {p\in\mathbb R^d}. On pose {\alpha=\inf\{p\cdot x:x\ge0,\ Mx\le b\},} {\beta=\sup\{b\cdot q:q\le0,\ M^Tq\le p\},} avec {\inf\varnothing=+\infty} et {\sup\varnothing=-\infty}.

Dans la question 20, on suppose qu’il existe {\overline x\ge0} tel que {M\overline x\le b} et {p\cdot\overline x=\alpha}.

On note {M_i} la {i}-ème ligne de {M}, identifiée à un vecteur de {\mathbb R^d}, et {I=\{i:M_i\cdot\overline x=b_i\},\quad J=\{j:\overline x_j=0\}.}

Partie IV — Systèmes linéaires sous-déterminés

Pour {x\in\mathbb R^d}, on pose {\|x\|_1=\sum_{i=1}^d|x_i|,\quad\|x\|_\infty=\max_{1\le i\le d}|x_i|.} On note {I_+(x)=\{i:x_i>0\}}, {I_-(x)=\{i:x_i\lt 0\}} et {I_0(x)=\{i:x_i=0\}}.

On suppose {M\in\mathcal M_{k\times d}(\mathbb R)} de rang {k} et {b\in\mathbb R^k\setminus\{0\}}. On cherche une solution de {Mx=b} ayant au plus {k} coordonnées non nulles, en étudiant {r=\inf\{\|x\|_1:Mx=b\}.}