J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

X ENS Mathématiques PSI 2025

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Fonctions (limites, continuité, dérivabilité, intégration)Algèbre bilinéaire et espaces euclidiensCalcul différentiel et fonctions à plusieurs variablesSéries et familles sommablesTopologie/EVN
Logo x-ens
🔗 Explorer
Banque
X-ENS
Année
2025
Filière
PSI
Matière
Maths
X-ENS PSIX-ENS 2025PSI MathsMaths 2025
2025_08_29_38a3f673be8ed0a8f570g

ECOLES NORMALES SUPERIEURES ECOLE POLYTECHNIQUE

CONCOURS D'ADMISSION 2025

LUNDI 14 AVRIL 2025
08h00-12h00
FILIERE PSI - Epreuve n
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 l'ensemble des fonctions continues de dans , et l'ensemble de celles qui sont dérivables sur à dérivée continue. On dit qu'une fonction est -Lipschitzienne, où est un nombre réel, si elle satisfait
On dit qu'une fonction est convexe si elle satisfait
On pourra utiliser sans démonstration le fait qu'une fonction est convexe si et seulement si sa dérivée est croissante.
Dans les parties I, II et III du sujet, la suite est toujours définie par la relation de récurrence
déterminée par un terme initial , un pas de temps , et une fonction .

Objectif de l'énoncé

L'objet de cette composition est d'établir certaines propriétés de l'algorithme de la descente de gradient et de ses variantes. Dans le cas général d'une fonction de plusieurs variables continûment différentiable, cette méthode s'écrit
Le choix de la dimension 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 possède de fortes propriétés (convexité, régularité, ...), la suite des itérées converge rapidement vers un minimiseur de . 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 a des propriétés plus faibles (par exemple 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 de la descente de gradient.
  1. Soit telle que
a) Montrer que l'ensemble est fermé et borné.
b) En déduire qu'il existe tel que .
2. On suppose dans cette question que est convexe, et que est -Lipschitzienne, pour un certain .
a) Montrer que pour tous
b) Soient , et soient et . Montrer que
c) On suppose de plus que admet un minimiseur , et que . Montrer que la suite est décroissante. (On rappelle que satisfait (2).)

Partie II: Convergence rapide, sous des hypothèses fortes

Dans cette partie, on montre que la suite définie par l'algorithme de descente de gradient converge rapidement vers un minimiseur de , 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 pour tout , où est fixé.
a) Montrer que , puis exprimer directement en fonction de et .
b) On suppose . Justifier que si et seulement si .
Hypothèses : Dans la suite, on se donne telle que est -Lipschitzienne, avec , et on fixe tel que . On suppose de plus que est -convexe, avec , c'est à dire que
  1. Justifier que est une fonction croissante de . En déduire que .
  2. Montrer que pour tout . En déduire que admet un minimiseur sur .
On note un minimiseur de , dont l'existence vient d'être établie. Les hypothèses faites permettent d'établir que les itérées de la descente de gradient s'en rapprochent.
6. Montrer que pour tous
  1. En déduire que pour tous , en notant et , on a
  1. On suppose . Montrer que , où est une constante que l'on précisera, et telle que .

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 des itérées de la descente de gradient converge, a priori assez lentement, vers un minimiseur de , a priori non-unique. Commençons de nouveau par l'étude d'un exemple :
  1. Justifier que et que est convexe. Donner l'ensemble de ses minimiseurs.
  2. On suppose dans cette question que .
    a) Justifier que la suite , définie par la relation de récurrence (2), est décroissante, à valeurs strictement positives, et satisfait pour tout .
    b) Justifier que lorsque .
    c) Montrer que pour tout . En déduire que .
  3. On suppose seulement . Montrer que pour tout , la suite converge vers un minimiseur de .
Hypothèses : On se donne dans la suite . On suppose que est convexe, admet un minimiseur , et que est -Lipschitzienne. On suppose également que .
12. a) Montrer que pour tous
Indication : considérer un développement limité de (1) lorsque .
b) Montrer que pour tous
c) Etablir que pour tout
En déduire que la suite est décroissante.
Dans les questions suivantes, on montre que l'algorithme du gradient converge en valeur, c'est à dire que la suite tend vers le minimum de la fonction .
13. Montrer que pour tout .
14. Montrer que pour tout , en supposant ,
Indication : utiliser 2.c)
15. Soit , et soit une suite de nombres réels positifs telle que pour tout . Montrer pour tout .
Indication : adapter le raisonnement de la question 10.c)
16. Etablir une majoration de la suite de terme général . Conclure que lorsque .
On cherche maintenant à établir que la suite tend vers un minimiseur de . On rappelle qu'on a noté un tel minimiseur, que l'on suppose exister, mais que celui-ci n'est pas forcément unique comme le montre l'exemple introductif.
17. Montrer que pour tout . En déduire que lorsque .
18. a) Montrer que la suite admet une sous suite convergente. On note l'extractrice et la limite correspondante, de sorte que lorsque . Indication. On pourra utiliser sans démonstration le théorème de Bolzano-Weierstrass : de toute suite dans bornée, on peut extraire une sous-suite convergente.
b) Montrer que .
c) En déduire que est un minimiseur de , puis que lorsque .

Partie IV: Descente de gradient proximale

Une limitation de l'algorithme de descente de gradient est que la fonction à minimiser doit être (continûment) dérivable. Dans cette partie on considère une généralisation de cet algorithme, qui se passe de cette hypothèse. Le lien avec la descente de gradient, dans sa variante implicite, est fait dans la question 21.
Hypothèses : On considère une fonction convexe , admettant un minimiseur . Soit également .
19. Montrer que la fonction admet un unique minimiseur sur , que l'on notera .
Indication: On pourra considérer des minimiseurs et de , et remarquer que
  1. Montrer que est un minimiseur de si et seulement si .
Indication : considérer la quantité lorsque .
21. Dans cette question seulement, on suppose que . Montrer que satisfait
Dans toute la suite, étant donné , on définit la suite récurrente par
Illustrons le comportement de cette suite sur un exemple.
22. Dans cette question seulement, on pose pour tout .
a) Montrer que
b) En déduire que lorsque , quels que soient et .
Les questions suivantes étudient les différences entre les termes successifs de la suite , désormais définie par (5). (Attention : (2) n'a plus cours.)
23. Montrer que . En déduire que pour tous entiers
En déduire que lorsque .
24. Montrer que pout tous
Montrons maintenant que la fonction définissant notre suite récurrente est 1-Lipschitzienne.
25. Soient , et . Montrer que pour tous et
Soient également , et . En déduire que
  1. Montrer que le membre de droite dans l'inégalité (6) admet le développement limité lorsque .
  2. On choisit dans l'inégalité (6). Montrer que le membre de gauche est positif pour tout . En déduire que
  1. Montrer que pour tous . En déduire que la suite est décroissante.
On obtient comme dans la question 18.a) l'existence d'une sous-suite convergente lorsque , où est strictement croissante et .
29. Montrer que lorsque , puis en déduire que .
30. Conclure que est un minimiseur de , et que lorsque .

Partie V: Optimisation sur la boule unité

Dans cette partie, on étudie la variante dite projetée de l'algorithme descente de gradient, qui vise à minimiser une fonction de plusieurs variables, restreinte à la boule unité. On fixe un entier , et on munit du produit scalaire usuel noté et de la norme euclidienne associée . On note la boule unité fermée de , et on se donne .
31. Montrer que admet un minimiseur sur , que l'on note dans les questions suivantes.
32. On suppose dans cette question que . Montrer que .
33. On suppose dans cette question que . L'objectif est de montrer que
a) Soient tels que et . Montrer que et , où .
b) On suppose par l'absurde que (7) n'est pas satisfaite. Montrer qu'il existe tel que et . En déduire une contradiction et conclure.
Indication : considérer les quantités et , dans la limite .
Dans la suite de cette section, désigne une matrice réelle symétrique de taille non nulle telle que
(Les vecteurs de sont ici considérés comme des vecteurs colonnes.)
On définit la fonction de dans par
  1. Montrer que , pour tout .
  2. Décrire l'ensemble des minimiseurs de sur .
Etant donné , on définit une suite récurrente par
Cette suite correspond à l'algorithme de la descente de gradient projetée.
36. On suppose dans cette question que .
a) Montrer que
b) Calculer .
Indication. Décomposer dans une base orthonormée de vecteurs propres , associés aux valeurs propres de . Introduire l'ensemble d'indices , la valeur propre , et le vecteur où .
37. Comment la suite se comporte-t-elle lorsque ?
38. Montrer qu'il existe un hyperplan tel que, pour tout , on a .

Fin du sujet

X ENS Mathématiques PSI 2025 - Version Web LaTeX | WikiPrépa | WikiPrépa