Corrigé ENS Ulm 2025 Maths D MP — Partie 2.1 (Q12 à Q18) : Polytopes : faces, existence d'un sommet, enveloppe convexe des sommets, Conv(V) est un polytope par dualité

Sujet officiel du concours ENS Ulm, session 2025, épreuve Maths D MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un polytope de $R^{n}$ est une partie compacte non vide de la forme $P = {x \in R^{n} : ℓ_{i} (x) \leq a_{i} \forall i \in I}$ , avec $I$ fini non vide, $ℓ_{i}$ formes linéaires, $a_{i} \in R$ . Pour $X \subset R^{n}$ , $X$ est le sous-espace engendré par les $x - y$ ( $x, y \in X$ ) ; $dim P = dim P$ . Pour $J \subset I$ , $F_{J} = {x \in P : ℓ_{j} (x) = a_{j} \forall j \in J}$ ; une face est un $F_{J}$ non vide. Pour une face $F$ , $S_{F} = {i : ℓ_{i} = a_{i} sur F}$ et $F^{\circ} = {x \in P : (ℓ_{i} (x) = a_{i} ⟺ i \in S_{F})}$ (intérieur relatif). Un sommet est une face de dimension $0$ . $Conv (X)$ est l'ensemble des combinaisons convexes finies d'éléments de $X$ . On admet que faces et intérieurs relatifs ne dépendent que de $P$ , pas du système d'inégalités.

Q12. Toute face $F$ est un polytope, et $dim F < dim P$ si $F \neq = P$ .
Q13. $P$ a un nombre fini de faces et au moins un sommet.
Q14. Si $V$ est l'ensemble des sommets, $P = Conv (V)$ .
Soit $V \subset R^{n}$ fini non vide.
Q15. Pour montrer que $Conv (V)$ est un polytope, on peut supposer qu'il n'est inclus dans aucun hyperplan et contient $0$ dans son intérieur.
Q16. Sous ces hypothèses, $Q = {ℓ \in R^{n} : ⟨ ℓ, x ⟩ \leq 1 \forall x \in V}$ est un polytope.
Q17. En déduire que $Conv (V)$ est un polytope. (On admet : pour $C$ convexe fermé non vide et $x \in / C$ , il existe $y \in C$ tel que $⟨ x - y, z - y ⟩ \leq 0$ pour tout $z \in C$ .)
Q18. Tout sommet de $Conv (V)$ appartient à $V$ .

Corrigé

Préliminaires. $P$ est une intersection finie de demi-espaces fermés, donc un convexe fermé. Une combinaison convexe de combinaisons convexes d'éléments de $X$ est une combinaison convexe d'éléments de $X$ , donc $Conv (X)$ est convexe ; il est contenu dans tout convexe contenant $X$ . Si $X = {x_{1}, \dots, x_{k}}$ est fini, $Conv (X)$ est l'image du compact $Δ_{k} = {t \in [0, 1]^{k} : \sum t_{i} = 1}$ par l'application continue $t \mapsto \sum t_{i} x_{i}$ , donc est compact.

Deux lemmes.

Lemme L1 (dimension). Si $G \subset F \subset R^{n}$ et si une forme linéaire $ℓ$ est constante sur $G$ mais pas sur $F$ , alors $dim G < dim F$ . En effet $G \subset F$ ; $ℓ$ s'annule sur les $x - x^{'}$ ( $x, x^{'} \in G$ ), donc sur $G$ , mais pas sur $F$ (il existe $x, x^{'} \in F$ avec $ℓ (x - x^{'}) \neq = 0$ ). L'inclusion $G \subset F$ est donc stricte.

Lemme L2 (sortie). Soient $x \in P$ et $u \in R^{n} ∖ {0}$ . L'ensemble $T = {t \geq 0 : x + t u \in P}$ est un segment $[0, t_{1}]$ , et il existe $i \in I$ tel que $ℓ_{i} (x + t_{1} u) = a_{i}$ et $ℓ_{i} (u) > 0$ . En effet $T$ contient $0$ , est convexe ( $P$ l'est), fermé ( $P$ fermé, $t \mapsto x + t u$ continue) et borné ( $∥ x + t u ∥ \geq t ∥ u ∥ - ∥ x ∥$ et $P$ est borné). Pour $m \in N^{*}$ , $x + (t_{1} + \frac{1}{m}) u \in / P$ , donc un indice $i_{m}$ viole sa contrainte. $I$ étant fini, un même $i$ convient pour une infinité de $m$ ; en faisant tendre $m \to + \infty$ le long de ceux-ci, $ℓ_{i} (x + t_{1} u) \geq a_{i}$ , d'où l'égalité puisque $x + t_{1} u \in P$ ; alors $a_{i} + \frac{1}{m} ℓ_{i} (u) > a_{i}$ donne $ℓ_{i} (u) > 0$ .

Q12. Soit $F = F_{J}$ une face. On a

$F = {x \in R^{n} : ℓ_{i} (x) \leq a_{i} (i \in I), - ℓ_{j} (x) \leq - a_{j} (j \in J)},$

système fini d'inégalités linéaires ; $F$ est fermé dans le compact $P$ , donc compact, et non vide par définition : c'est un polytope. Comme $F \subset P$ , $F \subset P$ et $dim F \leq dim P$ . Si $F \neq = P$ , soit $y \in P ∖ F$ : il existe $j \in J$ avec $ℓ_{j} (y) < a_{j}$ , alors que $ℓ_{j} = a_{j}$ sur $F$ (non vide). La forme $ℓ_{j}$ est constante sur $F$ mais pas sur $P$ ; par L1, $dim F < dim P$ .

Deux autres lemmes.

Lemme L3 (faces d'une face). Soit $F = F_{J_{0}}$ une face de $P$ , munie du système de Q12. Les faces de $F$ sont exactement les faces de $P$ contenues dans $F$ . En effet, une face de $F$ pour ce système est l'ensemble (non vide) des points de $F$ où sont saturées certaines contraintes $ℓ_{i} \leq a_{i}$ ( $i \in J_{1}$ ) et $- ℓ_{j} \leq - a_{j}$ ( $j \in J_{2} \subset J_{0}$ ), c'est-à-dire $F_{J_{0} \cup J_{1} \cup J_{2}}$ : une face de $P$ contenue dans $F$ . Réciproquement, si $G = F_{J}$ est une face de $P$ contenue dans $F$ , alors $G = {x \in F : ℓ_{j} (x) = a_{j}, j \in J}$ , face de $F$ . Par l'invariance admise, ceci ne dépend pas du système choisi pour $F$ ; en particulier les sommets de $F$ sont des sommets de $P$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →