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

3,0(2 votes)

Explorer les annales

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

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

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficulté moyenne

Transport optimal régularisé par l'entropie et algorithme de Sinkhorn

Le sujet s'appuie sur le transport de masse avec régularisation entropique, qui conserve la convexité du problème et conduit, par dualité lagrangienne, à l'algorithme de Sinkhorn. Il traite d'abord les fonctions convexes, les extrema liés et les points selles, puis l'entropie et la divergence de Kullback-Leibler à travers une version simplifiée du théorème de codage de source de Shannon. Il étudie enfin le minimum d'une fonction strictement convexe sur un ensemble de lois couplées et sa résolution par minimisation alternée sur les variables duales.

1Partie I : convexité et points sellesUnicité du minimum d'une fonction strictement convexe, noyau et image de la transposée, théorème des extrema liés et point selle du lagrangien.
2Partie II : entropie et codageDivergence de Kullback-Leibler, codes binaires préfixes, inégalité sur les longueurs de mots et minoration de la longueur moyenne par l'entropie.
3Partie III : transport régulariséConvexité de l'ensemble des couplages, lois marginales, existence et unicité du minimiseur de la fonctionnelle régularisée.
4Partie IV : dualitéPoint selle du lagrangien, fonction duale concave et convergence de l'algorithme de Sinkhorn.

Difficulté moyenne. Selon le jury, le sujet ne posait pas de difficultés notables, mais seules les très bonnes copies ont su se ramener en dimension 1 et la dernière partie, aux objets lourds, n'a presque pas été abordée correctement.

L'épreuve en chiffres

Moyenne 10 / 20 · écart-type 3,5 · où vous situez-vous ?

Moyenne: 10/ 20
Écart-type: 3,5

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

6 erreurs relevées

Unicité du minimum · Arguments de dimension mal posés · Ne pas se ramener en dimension 1

Les premières parties ont été très largement abordées et les écarts se sont faits sur la précision des arguments. La technique consistant à se ramener en dimension 1 par un segment n'a été maîtrisée que par les très bonnes copies. La lourdeur des notations de la dernière partie a visiblement effrayé les candidats.

Les erreurs les plus sanctionnées

1
Unicité du minimumQ1
L'unicité du point de minimum d'une fonction strictement convexe n'a été correctement démontrée que par la moitié des candidats.
2
Arguments de dimension mal posésQ2c
Pour montrer l'égalité entre le noyau et l'orthogonal de l'image de la transposée, beaucoup ont supposé n = m au lieu de montrer directement l'inclusion réciproque.
3
Ne pas se ramener en dimension 1Q3a, Q3d
La question 3a était très facile en fixant toutes les variables sauf une ou en considérant un segment, mais elle n'a presque pas été abordée. La même idée servait en 3d.
4
Détails de rigueur oubliésQ5, Q6
Le mot vide a rarement été pris en compte en 5b, l'initialisation de la récurrence en 5c demandait de l'attention, et beaucoup oublient d'invoquer 5c pour conclure en 6.
5
Calculs inutilesQ7, Q9
La convexité en 7 et 9 découlait d'arguments directs (intersection avec des hyperplans affines, linéarité), mais beaucoup sont revenus à la définition ou se sont lancés dans des calculs aveugles.
6
Notations lourdes de la partie IVQ13 à Q16
La fin du sujet n'a presque pas été abordée correctement alors que les calculs, comme celui de G(f, g), étaient accessibles.
« des notations fournies cachent rarement des arguments complexes. »

Ce qui a été bien réussi

La première partie de la question 1 a presque toujours été bien traitée.
Les questions 3b et 3c ont été plutôt bien traitées.
La question 4 a été très bien traitée, et la plupart des candidats ont repéré la coquille entre log et ln.
La question de cours 8 a été bien traitée.

Conseils du jury

Savoir se ramener en dimension 1 pour une fonction de plusieurs variables, en fixant les autres variables ou en paramétrant un segment.
Privilégier les arguments structurels (linéarité, intersection de convexes) aux calculs aveugles.
Ne pas hésiter à donner un exemple, même trivial, quand un contre-exemple est demandé.
Garder en mémoire les résultats déjà établis dans le sujet, comme en 12b.

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

ECOLES NORMALES SUPERIEURES ECOLE POLYTECHNIQUE

CONCOURS D'ADMISSION 2023

LUNDI 17 AVRIL 2023 08h00-12h00 FILIERE PSI

MATHEMATIQUES (XUSR)

Notations et RAPPELS

On notera $ℝ_+$ l'ensemble des réels positifs ou nuls et $ℝ_+^*$ l'ensemble des réels strictement positifs.
On rappelle que si $F \subset ℝ^n$ est un fermé borné et $f : F \to ℝ$ est continue, alors le minimum de $f$ sur $F$ est atteint, c'est-à-dire qu'il existe $x \in F$ tel que $f(x) \leq f(y)$ pour tout $y \in F$ .
Soit $E$ un espace vectoriel sur $ℝ$ . On dit que $C \subset E$ est un ensemble convexe si pour tous $x, y \in C$ et tout $t \in [0, 1]$ on a $(1 - t)x + ty \in C$ .

Pour

C \subset E

convexe, une fonction

f : C \to ℝ

est dite convexe, si pour tous

x, y

éléments de

C

et tout

t \in [0, 1]

, on a

f((1 - t)x + ty) \leq (1 - t)f(x) + tf(y)

. On dit que

f

est strictement convexe si cette inégalité est stricte pour

t \in ]0, 1[

x \neq y

Soient $A$ et $B$ deux ensembles et $f : A \times B \to ℝ$ . On dit que $f$ admet un point selle en $(a_*, b_*) \in A \times B$ si pour tout $(a, b) \in A \times B$ on a

f(a_*, b) \leq f(a_*, b_*) \leq f(a, b_*)

Toutes les variables aléatoires seront supposées définies sur un espace probabilisé commun $(Ω, F, P)$ .

Les parties I et II sont indépendantes.

I. Convexité et points selles

Soient

m

n

deux entiers positifs non nuls et

E

un espace vectoriel sur

ℝ

.
(1) Soient

C \subset E

un ensemble convexe. Soient

f

g

deux fonctions convexes de

C

dans

ℝ

.
(a) Montrer que

f + g

est convexe, et strictement convexe s'il l'une des deux fonctions

f

g

est strictement convexe.
(b) On suppose

f

strictement convexe. Vérifier que le minimum de

f

est atteint sur

C

en au plus un point de

C

.
(2) Soit

A \in M_(m, n)(ℝ)

une matrice de

m

lignes et

n

colonnes. On note

⟨u, v⟩_(ℝ^n)

le produit scalaire entre deux vecteurs

u

v

ℝ^n

⟨μ, ν⟩_(ℝ^m)

celui entre deux vecteurs

μ

ν

ℝ^m

.
(a) Montrer que pour tout

(x, ν) \in ℝ^n \times ℝ^m

, on a

⟨Ax, ν⟩_(ℝ^m) = ⟨x, A^⊤ν⟩_(ℝ^n)

où

A^⊤

désigne la matrice transposée de

A

.
(b) En déduire que

kerA \subset (ImA^⊤)^⊥

où

E^⊥

désigne l'orthogonal de

E

pour le produit scalaire sur

ℝ^n

pour tout sous-espace vectoriel

E

ℝ^n

.
(c) Montrer que

kerA = (ImA^⊤)^⊥

(3) On considère un ouvert

U \subset ℝ^n, h : U \to ℝ

une application

C^1

b \in ℝ^m

. On suppose qu'il existe

x_* \in U

un minimum de

h

sur l'ensemble

V_b = {x ∈ U|Ax + b = 0}

.
(a) Montrer que pour tout

u \in ℝ^n

tel que

Au = 0

on a

⟨\nablah(x_*), u⟩_(ℝ^n) = 0

où

\nablah(x)

désigne le gradient de

h

x

.
(b) Montrer l'existence de

ν_* \in ℝ^m

tel que

\nablah(x_*) - A^T ν_* = 0

.
(c) En déduire que l'application

L : U \times ℝ^m \to ℝ

telle que

L(x, ν) = h(x) - ⟨ν, Ax + b⟩_(ℝ^m)

vérifie

(\partialL)/(\partialx_k)(x_*, ν_*) = 0

pour tout

1 \leq k \leq n

où

(\partialL)/(\partialx_k)(x, ν)

désigne la dérivée partielle de

L

par rapport à la

k

-ième coordonnées de

x \in ℝ^n

.
(d) Conclure que si

U

est convexe, et

h

convexe sur

U

, alors

L

admet un point selle en (

x_*, ν_*

), c'est-à-dire que l'on a

L(x_*, ν) \leq L(x_*, ν_*) \leq L(x, ν_*)

pour tout

(x, ν) \in U \times ℝ^m

II. Entropie et codage

Soient

X

un ensemble fini et

p = (p_x)_(x \in X)

une loi de probabilité sur

X

. On suppose que

p

charge tous les points de

X : p_x > 0

pour tout

x \in X

. On appelle entropie de

p

la quantité

H(p) = - \sum_(x \in X)p_x ln(p_x)

On considère l'ensemble

Q_x = {q = (q_x)_(x ∈ X) ∈ ℝ^X|∀x ∈ X, q_x ≥ 0}

. Pour tous

q, q^' \in Q_X

tels que

q_x^' > 0

pour tout

x \in X

, on définit :

KL(q, q^') = \sum_(x \in X)φ(q_x/q_x^')q_x^'

avec

φ : ℝ_+ \to ℝ

définie par

φ(x) = xlog(x) - x + 1

pour

x > 0

et prolongée en 0 par continuité.
(4) (a) Préciser

φ(0)

.
(b) Vérifier que

φ

est continue strictement convexe positive et que

φ(x) = 0

si et seulement si

x = 1

.
(c) Montrer que

Q_X

est convexe et que

q \mapsto KL(q, q^')

est strictement convexe positive et s'annule ssi

q = q^'

Soit

A

un ensemble fini. On appelle mot

surA

une suite finie d'éléments de

A

, on le note

u = u_1\dotsu_n

n

est la longueur du mot

u

, notée

|u|

. Le mot vide est noté

ε

, il est de longueur nulle. On note

A^*

l'ensemble des mots sur

A

A^+ = A^∗∖{ε}

l'ensemble des mots privé du mot vide.

On définit la concaténation

u \cdot v

de deux mots

u, v \in A^*

par

u \cdot ε = ε \cdot u = u

u \cdot v = u_1\dotsu_(|u|)v_1\dotsv_(|v|)

u, v \in A^+

. On dit que

u

est un préfixe de

v

v = u \cdot w

pour

w \in A^*

Soient

X

un ensemble fini non vide et

c : X → {0, 1}^+

une application injective. On dira que

c

est un code binaire sur

X

. On suppose de plus que

c

est un code préfixe, c'est à dire que pour tous

x \neq y

dans

X, c(x)

n'est pas un préfixe de

c(y)

.
(5) On définit

c¯ : X → {0, 1}^∗

tel que pour tout

x \in X, c(x) = c(x)_1 \cdot c¯(x)

où

c(x)_1

est le premier élément du mot

c(x)

.
(a) Vérifier que pour tout

x \neq y \in X

, si

c(x)_1 = c(y)_1

alors

c¯(x) \neq c¯(y)

c¯(x)

n'est pas un préfixe de

c¯(y)

.
(b) Pour

a \in {0, 1}

on note

X_a = {x ∈ X|c(x)_1 = a}

. Montrer que si

X_a

contient au moins deux éléments, alors la restriction de

c¯

X_a

est un code préfixe sur

X_a

.
(c) En déduire que

\sum_(x \in X^2)2^(- |c(x)|) \leq 1

. (Ind. : On pourra décomposer la somme en une somme sur

X_0

X_1

et raisonner par récurrence sur

L(c) = max{|c(x)||x \in X}

)

Soient

q = (2^(- |c(x)|))_(x \in X)

X

une variable aléatoire à valeurs dans

X

de loi

p

.
(6) (a) Vérifier que

ln(2)E(|c(X)|) = - \sum_(x \in X)p_x ln(q_x)

.
(b) En déduire que

E(|c(X)|) \geq (H(p))/(ln(2))

.
(Ind. : On pourra chercher à exprimer

ln(2)E(|c(x)|)

en fonction de

H(p)

KL(p, q)

)

III. Transport régularisé

Dans toute la suite

I

J

désignent deux ensembles finis.

On considère $α = (α_i)_(i \in I) \in (ℝ_+^*)^I$ et $β = (β_j)_(j \in J) \in (ℝ_+^*)^J$ tels que $\sum_(i \in I)α_i = \sum_(j \in J)β_j = 1$ si bien que $α$ et $β$ peuvent être considérés comme définissant deux lois de probabilités sur $I$ et $J$ .
Dans la suite on notera

Q = {(q_(ij))_((i, j) ∈ I × J) ∈ ℝ^(I × J)|q_(ij) ≥ 0 pour tout (i, j) ∈ I × J}

F(α, β) = {q ∈ Q|∑_(j^′ ∈ J)q_(ij^′) = α_i et ∑_(i^′ ∈ I)q_(i^′ j) = β_j pour tout (i, j) ∈ I × J}

On notera

p

l'élément de

F(α, β)

défini par

p_(ij) = α_i β_j > 0

pour tout

(i, j) \in I \times J

.
(7) Vérifier que

F(α, β)

est un ensemble convexe de l'espace vectoriel

E = ℝ^(I \times J)

(8) Soient

X_1

X_2

deux variables aleatoires telles que

X_1

est à valeurs dans

I

X_2

à valeurs dans

J

.
(a) Vérifier que si

q \in F(α, β)

, alors

\sum_(i \in I)\sum_(j \in J)q_(ij) = 1

.
(b) On suppose que

P(X_1 = i, X_2 = j) = q_(ij)

avec

q \in F(α, β)

. Calculer la loi de

X_1

et celle de

X_2

en fonction de

α

β

.
(c) Que dire de

X_1

X_2

lorsque

q = p

Soient

C = (C_(ij))_((i, j) \in I \times J) \in ℝ_+^(I \times J)

ε > 0

. On considère

J_ε : Q \to ℝ

définie par

J_ε(q) = \sum_(ij)q_(ij)C_(ij) + εKL(q, p)

où

KL(q, p)

est défini dans la partie précédente en prenant

X = I \times J

.
(9) Montrer que

J_ε

est strictement convexe sur

Q

.
(10) (a) Vérifier que

F(α, β)

est un fermé borné de

ℝ^(I \times J)

.
(b) Montrer qu'il existe un unique

q(ε) \in Q

minimisant

J_ε

sur

F(α, β)

.
(c) En considérant un contre-exemple simple, montrer que l'unicité n'est plus vraie si on suppose que

ε = 0

.
(11) (a) Vérifier que

q(ε)_(ij) > 0

pour tout

(i, j) \in I \times J

(Ind: On pourra raisonner par l'absurde et considérer pour tout

t \in ]0, 1[q(ε, t) = (1 - t)q(ε) + tp

puis observer le comportement de

φ(x)

au voisinage de

x = 0

).
(b) Montrer que cecin'est plus vrai si on suppose que

ε = 0

IV. Dualité

On définit

Q_(> 0) = (ℝ_+^*)^(I \times J)

ℒ : Q_(> 0) \times (ℝ^I \times ℝ^J) \to ℝ

défini par

ℒ(q, (f, g)) = J_ε(q) + \sum_(i \in I)f_i(α_i - \sum_(j \in J)q_(ij)) + \sum_(j \in J)g_j(β_j - \sum_(i \in I)q_(ij)).

(12) (a) Vérifier que

Q_(> 0)

est un ouvert convexe

ℝ^(I \times J)

.
(b) Montrer qu'il existe

(f(ε), g(ε)) \in ℝ^I \times ℝ^J

tel que

ℒ(q(ε), (f(ε), g(ε))

est un point selle de

ℒ

. (Indication : On pourra identifier

ℝ^(I \times J)

avec

ℝ^n

ℝ^I \times ℝ^J

avec

ℝ^m

pour

n

cardinal de

I \times J

m

somme des cardinaux de

I

J

puis utiliser la question 3 de la partie I.)
(13) (a) Montrer que pour tout

(f, g) \in ℝ^I \times ℝ^J

, le minimum de

q \mapsto ℒ(q, (f, g))

sur

Q_(> 0)

est atteint en

q(f, g)_(ij) = e^((f_i + g_j - C_(ij))/ε)p_(ij)

.
(b) Calculer la valeur de

G(f, g) = ℒ(q(f, g), (f, g))

.
(c) Vérifier que

G

est concave sur

ℝ^I \times ℝ^J

.
(14) Vérifier que si

f_* : ℝ^J \to ℝ^I

g_* : ℝ^I \to ℝ^J

sont définies par

f_*(g)_i = - εlog(\sum_(j \in J)e^((g_j - C_(ij))/ε)β_j) et g_*(f)_j = - εlog(\sum_(i \in I)e^((f_i - C_(ij))/ε)α_i)

alors pour tout

(f, g) \in ℝ^I \times ℝ^J

, on a

(\partialG)/(\partialf_i)(f_*(g), g) = (\partialG)/(\partialg_j)(f, g_*(f)) = 0

pour tout

(i, j) \in I \times J

Soit

(f^0, g^0) \in ℝ^(I \times J)

. Pour tout

k \geq 0

, on considère

g^(k + 1) = g_*(f^k) et f^(k + 1) = f_*(g^(k + 1))

(15) Montrer que la suite

(G(f^k, g^k))_(k \geq 0)

est croissante.
(16) On suppose qu'il existe

f^\infty = (f_i^\infty)_(i \in I)

g^\infty = (g_j^\infty)_(j \in J)

tel que

|f_i^k - f_i^\infty| \to 0

|g_j^k - g_j^\infty| \to

0 pour tous

i \in I

j \in J

. On note

G_∗ = sup{G(f, g)|(f, g) ∈ I × J}

.
(a) Montrer que

G(f^\infty, g^\infty) = G_*

.
(b) Montrer que

G(f(ε), g(ε)) = G_*

.
(c) Montrer qu'il existe une constante

a \in ℝ

telle

f(ε)_i = f_i^\infty + a

g(ε)_j = g_j^\infty - a

pour tout

(i, j) \in I \times J

.
(d) En déduire que

q(f^k, g^k) \to q(ε)

Questions fréquentes

4 questions

Sur quels chapitres porte le sujet X-ENS Maths PSI 2023 ?

Sur les fonctions convexes, le calcul différentiel avec extrema liés, l'algèbre linéaire euclidienne et les probabilités finies, appliqués au transport optimal régularisé et à l'algorithme de Sinkhorn.

Quelle est la moyenne de l'épreuve X-ENS Maths PSI 2023 ?

Selon le rapport, la moyenne a été fixée à 10 avec un écart-type de 3,5. Les quartiles sont 7,6 et 12,6, et dix pour cent des candidats ont plus de 14,5.

Quelles erreurs le jury a-t-il le plus relevées en X-ENS Maths PSI 2023 ?

L'incapacité à se ramener en dimension 1 pour une fonction de plusieurs variables, l'unicité du minimum mal démontrée, l'oubli du mot vide ou d'une question antérieure, et des calculs aveugles à la place d'arguments simples.

Y a-t-il une erreur d'énoncé dans X-ENS Maths PSI 2023 ?

Oui, le jury signale que le log de la partie II aurait dû être un ln. Les candidats ayant utilisé le logarithme décimal n'ont pas été pénalisés et le poids de la question concernée a été réduit.

Pas de description pour le moment

Commentaires• X ENS Mathématiques PSI 2023

Connectez-vous pour participer aux discussions

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

Chargement des commentaires...