X/ENS Maths PSI 2025

ECOLES NORMALES SUPERIEURES
ECOLE POLYTECHNIQUE

CONCOURS D'ADMISSION 2025

LUNDI 14 AVRIL 2025
08h00 - 12h00

FILIERE PSI - Epreuve n° 1

MATHEMATIQUES (XUSR)

Durée : 4 heures

L'utilisation des calculatrices n'est pas
autorisée pour cette épreuve

Le sujet comprend 7 pages numérotées de 1 à 7.
Début de l'épreuve

Notations
On note C(R) l'ensemble des fonctions continues de R dans R, et C 1 (R) 
l'ensemble de
celles qui sont dérivables sur R à dérivée continue. On dit qu'une fonction g : 
R  R est
L-Lipschitzienne où L > 0 est un nombre réel, si elle satisfait
x, y  R, |g(x) - g(y)|  L|x - y|.
On dit qu'une fonction f : R  R est convexe si elle satisfait
x, y  R, t  [0, 1], f ((1 - t)x + ty)  (1 - t)f (x) + tf (y).

(1)

On pourra utiliser sans démonstration le fait qu'une fonction f  C 1 (R) est 
convexe si et
seulement si sa dérivée f  est croissante.
Dans les partie I, II et III du sujet, la suite (xn )nN est toujours définie 
par la relation
de récurrence
n  N, xn+1 := xn -  f  (xn ) ,

(2)

déterminée par un terme initial x0  R, un pas de temps  > 0, et une fonction f  
C 1 (R).

Objectif de l'énoncé
L'objet de cette composition est d'établir certaines propriétés de l'algorithme 
de
 la
1
d
descente de gradient et de ses variantes. Dans le cas général d'une fonction f  
C R de
plusieurs variables continûment différentiable, cette méthode s'écrit
n  N, xn+1 = xn -  f (xn ) .
Le choix de la dimension d = 1 a été fait dans ce sujet (dernière partie 
exceptée) dans
le but d'alléger les notations, cependant la plupart des résultats obtenus et 
des méthodes
de preuve s'étendent naturellement en dimension arbitraire. Lorsque la fonction 
f possède
de fortes propriétés (convexité, régularité, ...), la suite (xn )nN des itérées 
converge rapidement vers un minimiseur de f . Sous des hypothèses plus faibles, 
on peut parfois obtenir
une convergence plus lente, ou bien avoir recours à une variante telle que la 
descente de
gradient implicite. Comprendre le comportement fin de l'algorithme lorsque f a 
des propriétés plus faibles (par exemple f non-convexe) fait l'objet de 
recherches actuelles, et du
champ d'investigation mathématique dit de l'optimisation numérique, dont les 
applications
sont nombreuses (ingénierie, intelligence artificielle, etc).
A l'exception des préliminaires, toutes les parties sont indépendantes. Ne pas 
hésiter à
admettre le résultat d'une question pour répondre aux suivantes.

Partie I : Préliminaires
Dans cette partie préliminaire, on établit d'abord l'existence d'un minimiseur, 
sous des
hypothèses adéquates, puis une première propriété des itérées (xn )nN de la 
descente de
gradient.
1. Soit f  C(R) telle que
lim f (x) = +

x-

et

lim f (x) = +

x+

(3)

a) Montrer que l'ensemble {x  R | f (x)  f (0)} est fermé et borné.
b) En déduire qu'il existe x  R tel que f (x ) = min{f (x) | x  R}.
2. On suppose dans cette question que f  C 1 (R) est convexe, et que f  est 
L-Lipschitzienne, pour un certain L > 0.
a) Montrer que pour tous x, y  R
f  (x) - f  (y)

2

 L(x - y) f  (x) - f  (y)

b) Soient x, y  R, et soient x := x -  f  (x) et y := y -  f  (y). Montrer que

|x - y|2  |x - y|2 -  (2 -  L)(x - y) f  (x) - f  (y) .
c) On suppose de plus que f admet un minimiseur x , et que 0 <   2/L. Montrer que la suite (|xn - x |)nN est décroissante. (On rappelle que (xn )nN satisfait (2).) Partie II : Convergence rapide, sous des hypothèses fortes Dans cette partie, on montre que la suite (xn )nN définie par l'algorithme de descente de gradient converge rapidement vers un minimiseur de f , on parle de convergence géométrique, en faisant des hypothèses fortes sur cette fonction. Commençons par l'étude d'un exemple. 3. Dans cette question seulement, on pose f (x) := 12 Lx2 pour tout x  R, où L > 0
est fixé.
a) Montrer que xn+1 = (1 -  L)xn , puis exprimer directement xn en fonction de
x0 et n.
b) On suppose x0 = 0. Justifier que xn  0 si et seulement si 0 <  < 2/L. Hypothèses : Dans la suite, on se donne f  C 1 (R) telle que f  est L-Lipschitzienne, avec L > 0, et on fixe  tel que 0 <   2/L. On suppose de plus que f est -convexe, avec > 0, c'est à dire que
1
g(x) := f (x) - |x|2 , est une fonction convexe sur R.
(4)
2
4. Justifier que f  (x) - x est une fonction croissante de x  R. En déduire que 
  L.
5. Montrer que f (x)  f (0) + f  (0)x + x2 /2 pour tout x  R. En déduire que f 
admet
un minimiseur sur R.
On note x  R un minimiseur de f , dont l'existence vient d'être établie. Les 
hypothèses faites permettent d'établir que les itérées (xn )nN de la descente 
de gradient s'en
rapprochent.

6. Montrer que pour tous x, y  R

|x - y|2  f  (x) - f  (y) (x - y).
7. En déduire que pour tous x, y  R, en notant x := x -  f  (x) et y := y -  f  
(y), on a
|x - y|2  |x - y|2 (1 -  (2 - L ))
8. On suppose 0 <  < 2/L. Montrer que |xn - x |  n |x0 - x |, où  est une constante que l'on précisera, et telle que 0   < 1. Partie III : Convergence lente, sous des hypothèses faibles Dans cette partie, on se passe de l'hypothèse très forte (4) utilisée précédemment. On montre que la suite (xn )nN des itérées de la descente de gradient converge, a priori assez lentement, vers un minimiseur de f , a priori non-unique. Commençons de nouveau par l'étude d'un exemple : 1 f (x) := x3 3 si x  0, f (x) := 0 si x < 0 9. Justifier que f  C 1 (R) et que f est convexe. Donner l'ensemble de ses minimiseurs. 10. On suppose dans cette question que 0 < x0 < 1/ . a) Justifier que la suite (xn )nN , définie par la relation de récurrence (2), est décroissante, à valeurs strictement positives, et satisfait xn+1 = xn (1 - xn ) pour tout n  N. b) Justifier que xn  0 lorsque n  . c) Montrer que 1/xn+1 = 1/xn +  / (1 -  xn ) pour tout n  N. En déduire que xn  x0 / (1 + n x0 ). 11. On suppose seulement  > 0. Montrer que pour tout x0  R, la suite (xn )nN 
converge
vers un minimiseur de f .
Hypothèses : On se donne dans la suite f  C 1 (R). On suppose que f est 
convexe, admet un
minimiseur x  R, et que f  est L-Lipschitzienne. On suppose également que 0 < < 2/L. 12. a) Montrer que pour tous x, y  R f (y)  f (x) + f  (x)(y - x) Indication : considérer un développement limité de (1) lorsque t  0+ . b) Montrer que pour tous x, y  R f (y)  f (x) + f  (x)(y - x) + L (y - x)2 . 2 c) Etablir que pour tout n  N 2 f (xn+1 )  f (xn ) - (2 -  L) f  (xn ) . 2 En déduire que la suite (f (xn ))nN est décroissante. Dans les questions suivantes, on montre que l'algorithme du gradient converge en valeur, c'est à dire que la suite (f (xn ))nN tend vers le minimum f (x ) de la fonction f . 13. Montrer que 0  f (x) - f (x )  |x - x | |f  (x)| pour tout x  R. 14. Montrer que pour tout n  N, en supposant x0 = x , |f (xn ) - f (x )|2 . f (xn+1 )  f (xn ) - (2 -  L) 2 |x0 - x |2 Indication : Utiliser 2.c) 15. Soit c > 0 et soit (an )nN une suite de nombres réels positifs telle que 
an+1  an - c (an )2
pour tout n  N. Montrer an  a0 / (1 + nca0 ) pour tout n  N.
Indication : adapter le raisonnement de la question 10.c)
16. Etablir une majoration de la suite de terme général an := f (xn ) - f (x ). 
Conclure
que f (xn )  f (x ) lorsque n  .
On cherche maintenant à établir que la suite (xn )nN tend vers un minimiseur de 
f . On
rappelle qu'on a noté x  R un tel minimiseur, que l'on suppose exister, mais 
que celui-ci
n'est pas forcément unique comme le montre l'exemple introductif.
P
17. Montrer que 2 (2- L) 0i 0.
19. Montrer que la fonction Fx0 (x) := 21 |x - x0 |2 +  f (x) admet un unique 
minimiseur
sur R, que l'on notera pf (x0 ).
Indication : On pourra considérer des minimiseurs x1 et x2 de Fx0 , et 
remarquer que
2
1
1
1
(x1 + x2 ) - x0 < |x1 - x0 |2 + |x2 - x0 |2 2 2 2 si x1 = x2 . 20. Montrer que x0  R est un minimiseur de f si et seulement si pf (x0 ) = x0 . Indication : considérer la quantité Fx0 ((1 - t)x0 + tx ) lorsque t  0+ . 21. Dans cette question seulement, on suppose que f  C 1 (R). Montrer que x1 := pf (x0 ) satisfait x1 = x0 -  f  (x1 ) Dans toute la suite, étant donné x0  R, on définit la suite récurrente (xn )nN par xn+1 := pf (xn ) . (5) Illustrons le comportement de cette suite sur un exemple. 22. Dans cette question seulement, on pose f (x) := |x| pour tout x  R. a) Montrer que x - pf (x) = x + 0 si x  , si x  -, sinon. b) En déduire que xn  0 lorsque n  , quels que soient x0  R et  > 0.
Les questions suivantes étudient les différences entre les termes successifs de 
la suite
(xn )nN , désormais définie par (5). (Attention : (2) n'a plus cours.)
23. Montrer que 12 |x1 - x0 |2 +  f (x1 )   f (x0 ). En déduire que pour tous 
entiers
N >M 0
1
2

X

|xn - xn-1 |2   (f (xM ) - f (xN ))

M  0 et
y, v < 0, où v := x - y. b) On suppose par l'absurde que (7) n'est pas satisfaite. Montrer qu'il existe v  Rd tel que v, f (x ) > 0 et v, x  > 0. En déduire une contradiction et conclure.
Indication : considérer les quantités f (x - tv) et x - tv2 , dans la limite
t  0+ .
Dans la suite de cette section, M désigne une matrice réelle symétrique de 
taille d × d non
nulle telle que
x  Rd , x, M x  0
(Les vecteurs de Rd sont ici considérés comme des vecteurs colonnes.)
On définit la fonction f de Rd dans R par
1
f (x) := - x, M x.
2
34. Montrer que f (x) = -M x, pour tout x  Rd .
35. Décrire l'ensemble des minimiseurs de f sur C.
Etant donné x0  Rd , on définit une suite récurrente par
xn+1 := PC (xn -  f (xn )) ,

avec

(
x
PC (x) :=
x/x

si x  1,
sinon.

Cette suite correspond à l'algorithme de la descente de gradient projetée.

36. On suppose dans cette question que x0   1.
a) Montrer que
n  N\{0}, xn =

(Id +  M )n x0
.
(Id +  M )n x0 

b) Calculer limn xn .
P
Indication. Décomposer x0 =
1id i ei dans une base orthonormée de vecteurs
propres (e1 , · · · , ed ), associés aux valeurs propres 1 , · · · , d de M . 
Introduire l'ensemble d'indices
I := {i  J1, dK | i = 0}, la valeur propre  := maxiI i , et le vecP
teur x0 := iI  i ei où I  := {i  I | i = }.
37. Comment la suite se comporte-t-elle lorsque x0  < 1 ? 38. Montrer qu'il existe un hyperplan H  Rd tel que, pour tout x0  Rd \H, on a limn f (xn ) = min{f (x) | x  C}. Fin du sujet