X ENS Mathématiques PSI 2022Sujet, corrigé et rapport du jury

Pas encore noté

Explorer les annales

BanqueX-ENS Année2022 FilièrePSI MatièreMathématiques

Annales X-ENS PSI Mathématiques X-ENS PSI 2022 PSI Mathématiques Mathématiques 2022

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Corrigé 2

Corrigé 3

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficile

Ensembles convexes : projection, séparation, points extrémaux, dualité en programmation linéaire et systèmes sous-déterminés

Le sujet étudie des propriétés des parties convexes de R^d : projection sur un convexe fermé, séparation de convexes, puis points extrémaux et enveloppe convexe. Il en donne deux applications : un résultat de dualité en programmation linéaire, obtenu via les cônes convexes, et l'existence, pour un système linéaire sous-déterminé, d'une solution ayant peu de coordonnées non nulles, par minimisation de la norme 1.

1Partie I : projection et séparationExistence et unicité du projeté sur un convexe fermé, caractérisation par un produit scalaire, séparation stricte et large de convexes (questions 1 à 8).
2Partie II : points extrémauxEnveloppe convexe, points extrémaux d'un polyèdre défini par des inégalités, puis d'un convexe fermé borné qui est l'enveloppe convexe de ses points extrémaux (questions 9 à 15).
3Partie III : un résultat de dualitéCônes polaire et bipolaire, cônes engendrés par un nombre fini de vecteurs, puis dualité en programmation linéaire (questions 16 à 20).
4Partie IV : systèmes linéaires sous-déterminésNormes 1 et infini, ensemble des solutions de norme 1 minimale et points extrémaux ayant au plus k coordonnées non nulles (questions 21 à 26).

Difficile. Le jury écrit que le sujet s'est révélé très difficile pour les candidats et qu'il a dû adapter le barème à chaque question ; les questions les plus dures n'ont presque jamais été résolues.

Ce qu'a observé le jury

5 erreurs relevées

Unicité du projeté négligée · Caractère fermé oublié · Réciproques non traitées

Le sujet s'est révélé très difficile et le jury a récompensé toute démarche constructive pour faire ressortir les meilleures copies. Beaucoup de questions reposaient sur la construction d'éléments par des suites dont on extrait une sous-suite convergente, démarche rarement mise en œuvre. Les dernières parties ont été très peu abordées et les questions 23 à 26 ne l'ont pas été du tout.

Les erreurs les plus sanctionnées

1
Unicité du projeté négligéeQuestion 1
L'existence passe par le théorème des bornes atteintes sur un compact, mais l'unicité, qui pouvait utiliser l'identité du parallélogramme, n'est presque jamais bien traitée.
2
Caractère fermé oubliéQuestion 5
La convexité de D − C est vue, mais le caractère fermé, qui demandait une approche par les suites et le théorème de Bolzano-Weierstrass rappelé par l'énoncé, est presque toujours ignoré.
3
Réciproques non traitéesQuestions 2, 7, 17
Les sens faciles des équivalences sont vus, mais les réciproques, qui demandaient de réutiliser la séparation stricte de la question 6, sont rarement abordées.
4
Absence de dessinQuestions 2, 4, 11
Un dessin aidait à comprendre la propriété demandée ou le contre-exemple, par exemple un point limite de points extrémaux qui n'est pas extrémal.
« Il fallait ensuite savoir illustrer par un dessin »
5
Résultats intermédiaires non réutilisésQuestions 19, 20
Les candidats cherchent souvent une solution en repartant de zéro au lieu d'exploiter la projection et la séparation établies plus tôt ; peu ont tenté de reprendre pied en programmation linéaire avec les résultats admis.

Ce qui a été bien réussi

Le sens direct de la caractérisation du projeté (question 2) est souvent correctement abordé.
La question 3 est correctement traitée dans les bonnes copies.
La question 9 est assez bien traitée par récurrence.
La question 16 sur les cônes polaires est bien traitée.

Conseils du jury

Maîtriser la construction d'éléments par des suites et l'extraction d'une sous-suite convergente, surtout pour manipuler des bornes inférieures et supérieures.
Illustrer par un dessin l'énoncé à démontrer.
Réutiliser les résultats intermédiaires du sujet plutôt que de repartir de zéro.
En cas de blocage, reprendre pied dans une nouvelle partie en admettant les résultats précédents.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

Début de l'épreuve

Pour

d \in ℕ^*

x = (x_1, \dots, x_d)

y = (y_1, \dots, y_d)

dans

ℝ^d

, nous noterons :

$x \cdot y$ le produit scalaire usuel de $x$ et $y$ .

x \cdot y:=\sum_(i = 1)^d x_i y_i

$‖x‖:=\sqrt(x \cdot x)$ , la norme euclidienne usuelle de $x$ ,
$[x, y]:={λx + (1 - λ)y, λ \in [0, 1]}$ le segment joignant $x$ à $y$ .

On rappelle qu'une partie

A

ℝ^d

est convexe si pour tout

(x, y) \in A^2

, on a

[x, y] \subset A

. Si

A

B

sont deux parties non vides de

ℝ^d, x \in ℝ^d

λ \in ℝ

, nous noterons

A + B:={a + b, a \in A, b \in B}, λA:={λa, a \in A}; A - B:=A + (- 1)B, A - x:=A - {x}

nous noterons

dim(A)

la dimension de l'espace vectoriel engendré par

A - a

où

a

est un élément quelconque de

A

(cette définition étant indépendante du choix de

a \in A

). En particulier si

x

y

appartiennent à

ℝ^d

x \neq y

, on a

dim({x}) = 0

, et

dim([x, y]) = 1

Pour

M \in M_(m \times d)(ℝ)

, nous identifierons toujours

M

à l'application linéaire dont

M

est la matrice dans les bases canoniques de

ℝ^d

ℝ^m

et noterons donc

Ker(M):={x ∈ ℝ^d : Mx = 0}, Im(M):={Mx, x ∈ ℝ^d}

enfin

M^T

désignera la transposée de

M

.
Pour tout

k \in ℕ^*

, nous noterons

ℝ_+^k

l'ensemble des éléments de

ℝ^k

dont les coordonnées sont dans

ℝ_+

et pour

y_1

y_2

dans

ℝ^k

, nous écrirons

y_1 ⩾ y_2

(ou

y_2 ⩽ y_1

) quand

y_1 - y_2 \in ℝ_+^k

On rappelle enfin que toute suite bornée d'éléments de

ℝ^k

possède une extraction qui converge.

Partie I : Projection et séparation

Projection

Soit

C

une partie non vide, convexe et fermée de

ℝ^d

x \in ℝ^d

, considérons :

inf_(y \in C)‖x - y‖^2.

Montrer que (1) possède une unique solution (c'est à dire qu'il existe un unique $y \in C$ tel que $‖x - y‖^2 ⩽ ‖x - z‖^2$ pour tout $z \in C$ ) que nous appellerons projection de $x$ sur $C$ et noterons $proj_C(x)$ . Montrer que $x = proj_C(x)$ si et seulement si $x \in C$ .
Soit $y \in ℝ^d$ montrer que

y = proj_C(x) ⟺ y \in C et (x - y) \cdot (z - y) ⩽ 0, \forallz \in C.

Montrer que pour tout $(x_1, x_2) \in ℝ^d \times ℝ^d$ , on a

(proj_C(x_1) - proj_C(x_2)) \cdot (x_1 - x_2) ⩾ ‖proj_C(x_1) - proj_C(x_2)‖^2,

et en déduire que

proj_C

est continue.
4) Déterminer explicitement

proj_C

dans les cas suivants :

i) C = ℝ_+^d, ii)C = {y ∈ ℝ^d : ‖y‖ ⩽ 1}; iii) C = {y ∈ ℝ^d : ∑_(i = 1)^d y_i ⩽ 1}, iv)C = [ − 1, 1]^d

Séparation

Soit

C

D

deux parties convexes non vides de

ℝ^d

telles que

é é é C est fermée et bornée, D est fermée, et C \cap D = \emptyset.

Montrer que $D - C$ est une partie convexe fermée de $ℝ^d$ ne contenant pas 0 .
Montrer qu'il existe $p \in ℝ^d$ et $ε > 0$ tels que

p \cdot x ⩽ p \cdot y - ε, \forall(x, y) \in C \times D

(on dit que

C

D

peuvent être séparés strictement).
7) Soit

C

une partie convexe fermée non vide de

ℝ^d

et soit

σ_C : ℝ^d → ℝ ∪ { + ∞}

définie par :

σ_C(p):=sup{p ⋅ x, x ∈ C}

montrer que

C = {x ∈ ℝ^d : p ⋅ x ⩽ σ_C(p), ∀p ∈ ℝ^d}

(de sorte que

C

est une intersection de demi-espaces fermés).
8) Soit

A

une partie convexe non vide de

ℝ^d

x \in ℝ^d∖A

, montrer qu'il existe

p ∈ ℝ^d∖{0}

tel que

p \cdot x ⩽ p \cdot y, \forally \in A

Partie II : Points extrémaux

Soit

E

une partie de

ℝ^d

, on appelle enveloppe convexe de

E

et l'on note

co(E)

l'ensemble

co(E):={∑_(i = 1)^I λ_i x_i, I ∈ ℕ^∗, λ_i ⩾ 0, ∑_(i = 1)^I λ_i = 1, (x_1, …, x_I) ∈ E^I}

Soit

A

une partie convexe non vide de

ℝ^d

, nous dirons que

x \in A

est un point extrémal de

A

\forall(y, z, λ) \in A \times A \times ]0, 1[

, on a

x = (1 - λ)y + λz \Rightarrow y = z.

Nous noterons

Ext(A)

l'ensemble des points extrémaux de

A

Cas particuliers

Soit $A$ une partie convexe non vide de $ℝ^d$ . Soit $I \in ℕ^*, x_1, \dotsx_I \in A^I$ et $(λ_1, \dots, λ_I) \in ℝ_+^I$ tels que $\sum_(i = 1)^I λ_i = 1$ , montrer que:

a) $\sum_(i = 1)^I λ_i x_i \in A$ ,
b) si $x:=\sum_(i = 1)^I λ_i x_i \in Ext(A)$ alors $x_i = x$ pour tout $i \in {1, \dots, I}$ tel que $λ_i > 0$ .

Soit $E$ une partie de $ℝ^d$ montrer que $co(E)$ est le plus petit convexe contenant $E$ et que $Ext(co(E)) \subset E$ .
Soit $A = co(E)$ où $E$ est la partie de $ℝ^3$ définie par

E = {(0, 0, 1), (0, 0, - 1)} \cup {(1 + cos(θ), sin(θ), 0), θ \in [0, 2π]}

montrer que

Ext(A)

est non vide et n'est pas fermée.
12) Soit

k \in ℕ^*, (p_1, \dots, p_k) \in (ℝ^d)^k

(b_1, \dots, b_k) \in ℝ^k

tels que

A:={x ∈ ℝ^d : p_i ⋅ x ⩽ b_i, i = 1, …, k}

soit non vide. Montrer que

A

est convexe et fermée. Soit

x \in A

, soit

I(x):={i ∈ {1, …, k} : p_i ⋅ x = b

montrer que

x ∈ Ext(A) ⟺ rang({p_i, i ∈ I(x)}) = d

en déduire que

Ext(A)

est un ensemble fini (éventuellement vide) dont le cardinal est inférieur ou égal à

2^k

Cas d'un convexe fermé borné

Dans les trois questions qui suivent,

K

est une partie non vide, convexe, fermée et bornée de

ℝ^d

.
13) Soit

p \in ℝ^d

, posons

K_p:={x ∈ K : p ⋅ x ⩽ p ⋅ y, ∀y ∈ K}.

Montrer que

K_p

est non vide, convexe et fermée et que

Ext(K_p) \subset Ext(K)

.
14) Montrer que

Ext(K)

est non vide (on pourra se ramener au cas où

0 \in K

et raisonner sur la dimension de

K

).
15) Montrer que

K = co(Ext(K))

Partie III : Un résultat de dualité

Cônes convexes

On dit qu'une partie

F

ℝ^d

est un cône si

λF \subset F

pour tout

λ \in ℝ_+

. Soit

E

une partie non vide de

ℝ^d

, le cône polaire de

E

est défini par

E^+:={p ∈ ℝ^d : p ⋅ x ⩾ 0, ∀x ∈ E}

et son cône bi-polaire par

E^(+ +) = (E^+)^+:={ξ ∈ ℝ^d : ξ ⋅ p ⩾ 0, ∀p ∈ E^+}.

Montrer que $E^+$ et $E^(+ +)$ sont des cônes convexes fermés et que $E \subset E^(+ +)$ .
Montrer que $E = E^(+ +)$ si et seulement si $E$ est un cône convexe fermé.
Soit $ξ_1, \dots, ξ_k, k$ éléments de $ℝ^d$ et

F:={∑_(i = 1)^k λ_i ξ_i, (λ_1, …, λ_k) ∈ ℝ_+^k}

montrer que

F

est un cône convexe fermé. Soit

ξ \in ℝ^d

, montrer que l'équivalence entre :

$ξ \in F$ ,
$ξ \cdot x ⩾ 0$ pour tout $x \in ℝ^d$ tel que

ξ_i \cdot x ⩾ 0, i = 1, \dots, k.

Programmation linéaire

Soit

M \in M_(k \times d)(ℝ), b = (b_1, \dots, b_k) \in ℝ^k

p \in ℝ^d

. Posons

α:=inf{p ⋅ x : x ∈ ℝ^d, x ⩾ 0, Mx ⩽ b}

β:=sup{b ⋅ q : q ∈ ℝ^k, q ⩽ 0, M^T q ⩽ p}

(en adoptant la convention :

inf\emptyset = + \infty

sup\emptyset = - \infty

).
19) Montrer que

α ⩾ β

.
20) On suppose qu'il existe

x¯ = (x¯_1, \dots, x¯_d) \in ℝ^d

tel que

x¯ ⩾ 0, Mx¯ ⩽ b et p \cdot x¯ = α.

En notant

M_i

le vecteur de

ℝ^d

dont les coordonnées sont les coefficients de la

i

-ème ligne de

M

, posons :

I:={i ∈ {1, …, k} : M_i ⋅ x¯ = b_i}

J:={j ∈ {1, …, d} : x¯_j = 0}.

a) Montrer que $p \cdot z ⩾ 0$ pour tout $z \in ℝ^d$ tel que

z_j ⩾ 0 pour tout j \in J et M_i \cdot z ⩽ 0 pour tout i \in I.

b) Montrer qu'il existe $q¯ \in ℝ^k$ tel que :

q¯ ⩽ 0, M^T q¯ ⩽ p, q¯ \cdot (Mx¯ - b) = 0 et (p - M^T q¯) \cdot x¯ = 0.

c) Montrer que $b \cdot q¯ = α = β$ .

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

Pour tout

x = (x_1, \dots, x_d) \in ℝ^d

, on pose

‖x‖_1:=∑_(i = 1)^d|x_i|, ‖x‖_∞:=max{|x_i|, i = 1, …, d}; I_+(x):={i ∈ {1, …, d} : x_i > 0}, I_−(x):={i ∈ {1, …, d} : x_i < 0}

I_0(x):={i ∈ {1, …, d} : x_i = 0}

Soit

M \in M_(k \times d)(ℝ)

et supposons que

rang(M) = k.

Soit

b ∈ ℝ^k∖{0}

, l'objectif de cette partie est de trouver une solution du système linéaire

Mx = b

ayant au plus

k

coordonnées non nulles par une méthode de minimisation. Pour ce faire, on s'intéresse à :

r:=inf{‖x‖_1, x ∈ ℝ^d, Mx = b}.

Montrer que pour tout $x \in ℝ^d$ , on a

‖x‖_1 = max{x ⋅ y, y ∈ ℝ^d, ‖y‖_∞ ⩽ 1},

‖x‖_∞ = max{x ⋅ y, y ∈ ℝ^d, ‖y‖_1 ⩽ 1}

Notons $C$ l'ensemble :

C:={x ∈ ℝ^d : Mx = b, ‖x‖_1 = r}.

Montrer que

C

est non vide, convexe, fermé et borné.
23) Fixons

x¯ \in C

. Montrer qu'il existe

q ∈ Ker(M)^⊥∖{0}

tel que pour tout

i \in {1, \dots, d}

, on ait

q_i x¯_i = ‖q‖_\infty|x¯_i|

Soit $K$ l'ensemble des $y \in ℝ^d$ tels que

My = b, y_i = 0∀i ∈ I_0(x¯), q_i y_i ⩾ 0∀i ∈ {1, …d}

Montrer que

K

est non vide et inclus dans

C

.
25) Montrer que si

y \in Ext(K)

alors

h \in Ker(M) et I_0(y) \subset I_0(h) \Rightarrow h = 0.

En déduire que si $y \in Ext(K)$ alors le cardinal de $I_+(y) \cup I_-(y)$ est inférieur ou égal à $k$ .

Fin du sujet.

Questions fréquentes

4 questions

Sur quoi porte le sujet de maths X-ENS PSI 2022 ?

Sur les ensembles convexes de R^d : projection, séparation, points extrémaux, puis deux applications, la dualité en programmation linéaire et les systèmes linéaires sous-déterminés.

Le sujet de maths X PSI 2022 est-il difficile ?

Oui, le jury le qualifie de très difficile : il a adapté le barème pour valoriser toute idée pertinente, et les questions 23 à 26 n'ont pas été abordées.

Quelles erreurs le jury a-t-il relevées en maths X-ENS PSI 2022 ?

L'unicité du projeté et le caractère fermé des ensembles presque jamais justifiés, des réciproques non traitées, l'absence de dessin et la non-réutilisation des résultats intermédiaires.

Quelles méthodes travailler pour réussir le sujet X-ENS maths PSI 2022 ?

La construction d'éléments par des suites avec extraction d'une sous-suite convergente (théorème de Bolzano-Weierstrass), le théorème des bornes atteintes, l'inégalité de Cauchy-Schwarz et l'usage de dessins.

Pas de description pour le moment

Commentaires• X ENS Mathématiques PSI 2022

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...