2025-X-Ens-Psi-Corrigé

École polytechnique et ENS — PSI — 2025 — Mathématiques

On note {\mathcal C(\mathbb R)} et {\mathcal C^1(\mathbb R)} les fonctions réelles continues et continûment dérivables. Une fonction {g} est {L}-lipschitzienne si {|g(x)-g(y)|\leq L|x-y|} pour tous {x,y\in\mathbb R}.

Une fonction {f} est convexe si {f((1-t)x+ty)\leq(1-t)f(x)+tf(y)\quad(0\leq t\leq1).\tag{1}}On admet qu’une fonction de classe {\mathcal C^1} est convexe si et seulement si sa dérivée est croissante.

Dans les parties I, II et III, les itérées de la descente de gradient sont définies, pour un pas {\tau>0} et un point initial {x_0\in\mathbb R}, par {x_{n+1}=x_n-\tau f'(x_n).\tag{2}}On étudie leur convergence, puis une variante proximale et une variante projetée sur la boule unité. Hormis les préliminaires, les parties sont indépendantes.

Partie I — Préliminaires

1. Soit {f\in\mathcal C(\mathbb R)} telle que {f(x)\to+\infty} lorsque {x\to-\infty} ou {x\to+\infty}.

2. On suppose {f\in\mathcal C^1(\mathbb R)} convexe et {f'} {L}-lipschitzienne, avec {L>0}.

Partie II — Convergence rapide sous des hypothèses fortes

3. Dans cette question, {f(x)=Lx^2/2}, avec {L>0}.

Dans la suite de cette partie, {f\in\mathcal C^1(\mathbb R)}, {f'} est {L}-lipschitzienne et {0\lt \tau\leq2/L}. On suppose en outre {f} {\alpha}-convexe, avec {\alpha>0} : la fonction {g(x)=f(x)-\alpha x^2/2} est convexe.

Partie III — Convergence lente sous des hypothèses faibles

On commence par l’exemple {f(x)=x^3/3} pour {x\geq0}, et {f(x)=0} pour {x\lt 0}.

10. On suppose {0\lt x_0\lt 1/\tau}.

Dans la suite de cette partie, {f\in\mathcal C^1(\mathbb R)} est convexe, admet un minimiseur {x^*}, et {f'} est {L}-lipschitzienne. On suppose {0\lt \tau\lt 2/L}.

On cherche d’abord la convergence en valeur : {f(x_n)\to f(x^*)}.

On veut maintenant montrer que les itérées elles-mêmes convergent vers un minimiseur, qui n’est pas nécessairement l’unique minimiseur de {f}.

Partie IV — Descente de gradient proximale

On suppose désormais {f\in\mathcal C(\mathbb R)} convexe, admettant un minimiseur {x^*}, et {\tau>0}. Aucune dérivabilité n’est imposée. On pose {F_{x_0}(x)=|x-x_0|^2/2+\tau f(x)}.

À partir de maintenant, la suite est définie par {x_{n+1}=p_f(x_n)} ; la relation (2) n’est plus utilisée.

22. Dans cette question seulement, {f(x)=|x|}.

On montre maintenant que {p_f} est {1}-lipschitzienne. On notera {\widetilde x=p_f(x)} et {\widetilde y=p_f(y)}.

Comme en Q18.a, on en déduit une sous-suite convergente {x_{\varphi(n)}\to x^{**}}, avec une extractrice strictement croissante {\varphi}.

Partie V — Optimisation sur la boule unité

On fixe {d\geq1}. L’espace {\mathbb R^d} est muni de son produit scalaire usuel {\langle\cdot,\cdot\rangle} et de sa norme euclidienne. On note {C=\{x\in\mathbb R^d:\|x\|\leq1\}} et l’on considère {f\in\mathcal C^1(\mathbb R^d)}.

33. On suppose {\|x^*\|=1}. On veut montrer qu’il existe {\lambda\geq0} tel que {\nabla f(x^*)=-\lambda x^*}.

Dans la suite, {M} est une matrice symétrique réelle non nulle de taille {d}, telle que {\langle x,Mx\rangle\geq0} pour tout {x}. On pose {f(x)=-\langle x,Mx\rangle/2}.

Pour {\tau>0} et {x_0\in\mathbb R^d}, on définit désormais {x_{n+1}=P_C(x_n-\tau\nabla f(x_n)),\quad P_C(x)=\begin{cases}x&\text{si }\|x\|\leq1,\\[8pt]x/\|x\|&\text{sinon}.\end{cases}}Il s’agit de la descente de gradient projetée.

36. On suppose dans cette question {\|x_0\|\geq1}.