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}.

1. a) Montrer que {K=\{x\in\mathbb R:f(x)\leq f(0)\}} est fermé et borné.
1. b) En déduire l’existence de {x^*\in\mathbb R} tel que {f(x^*)=\min_{x\in\mathbb R}f(x)}.

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

2. a) Montrer que {|f'(x)-f'(y)|^2\leq L(x-y)(f'(x)-f'(y))}.
2. b) Posons {\widetilde x=x-\tau f'(x)} et {\widetilde y=y-\tau f'(y)}. Montrer que {|\widetilde x-\widetilde y|^2\leq|x-y|^2-\tau(2-\tau L)(x-y)(f'(x)-f'(y)).}
2. c) Si {f} admet un minimiseur {x^*} et {0\lt \tau\leq2/L}, montrer que {(|x_n-x^*|)} est décroissante.

Partie II — Convergence rapide sous des hypothèses fortes

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

3. a) Montrer que {x_{n+1}=(1-\tau L)x_n}, puis exprimer {x_n} à l’aide de {x_0,n}.
3. b) Si {x_0\ne0}, justifier que {x_n\to0} si et seulement si {0\lt \tau\lt 2/L}.

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.

4. Justifier que {f'(x)-\alpha x} est croissante et en déduire {\alpha\leq L}.
5. Montrer que {f(x)\geq f(0)+f'(0)x+\alpha x^2/2} et en déduire l’existence d’un minimiseur.
6. Montrer que {\alpha|x-y|^2\leq(f'(x)-f'(y))(x-y)}.
7. Avec les notations de Q2.b, montrer que {|\widetilde x-\widetilde y|^2\leq|x-y|^2\bigl(1-\alpha\tau(2-L\tau)\bigr).}
8. Si {0\lt \tau\lt 2/L}, montrer que {|x_n-x^*|\leq\rho^n|x_0-x^*|}, pour une constante {0\leq\rho\lt 1} à préciser.

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}.

9. Justifier que {f\in\mathcal C^1(\mathbb R)} est convexe et donner l’ensemble de ses minimiseurs.

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

10. a) Montrer que {(x_n)} est décroissante, strictement positive, et que {x_{n+1}=x_n(1-\tau x_n)}.
10. b) Justifier que {x_n\to0}.
10. c) Montrer que {1/x_{n+1}=1/x_n+\tau/(1-\tau x_n)}, puis que {x_n\leq x_0/(1+n\tau x_0)}.
11. Pour tout {\tau>0} et tout {x_0\in\mathbb R}, montrer que la suite converge vers un minimiseur de {f}.

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}.

12. a) Montrer que {f(y)\geq f(x)+f'(x)(y-x)}. Indication : développer l’inégalité de convexité lorsque {t\to0^+}.
12. b) Montrer que {f(y)\leq f(x)+f'(x)(y-x)+L(y-x)^2/2}.
12. c) Établir {f(x_{n+1})\leq f(x_n)-\frac\tau2(2-\tau L)|f'(x_n)|^2}, puis la décroissance de {(f(x_n))}.

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

13. Montrer que {0\leq f(x)-f(x^*)\leq|x-x^*|\,|f'(x)|}.
14. Si {x_0\ne x^*}, montrer que {f(x_{n+1})\leq f(x_n)-\frac\tau2(2-\tau L)\frac{|f(x_n)-f(x^*)|^2}{|x_0-x^*|^2}.}
15. Soit {c>0} et {(a_n)} une suite de réels positifs ou nuls telle que {a_{n+1}\leq a_n-ca_n^2}.

Montrer que {a_n\leq a_0/(1+nca_0)}.

16. Majorer {a_n=f(x_n)-f(x^*)} et conclure que {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}.

17. Montrer que {\frac\tau2(2-\tau L)\sum_{i=0}^{n-1}|f'(x_i)|^2\leq f(x_0)-f(x_n),}puis en déduire {f'(x_n)\to0}.
18. a) Montrer que {(x_n)} admet une sous-suite convergente, notée {x_{\varphi(n)}\to x^{**}}.
18. b) Montrer que {f'(x^{**})=0}.
18. c) En déduire que {x^{**}} est un minimiseur et que {|x_n-x^{**}|\to0}.

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)}.

19. Montrer que {F_{x_0}} admet un unique minimiseur sur {\mathbb R}, noté {p_f(x_0)}.
20. Montrer que {x_0} minimise {f} si et seulement si {p_f(x_0)=x_0}.
21. Si {f\in\mathcal C^1(\mathbb R)}, montrer que {x_1=p_f(x_0)} satisfait {x_1=x_0-\tau f'(x_1)}.

À 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|}.

22. a) Montrer que {p_f(x)=\begin{cases}x-\tau&\text{si }x\geq\tau,\\[8pt]x+\tau&\text{si }x\leq-\tau,\\[8pt]0&\text{sinon}.\end{cases}}
22. b) En déduire {x_n\to0} pour tous {x_0\in\mathbb R} et {\tau>0}.
23. Montrer que {|x_1-x_0|^2/2+\tau f(x_1)\leq\tau f(x_0)}, puis que, pour {N>M\geq0}, {\frac12\sum_{M\lt n\leq N}|x_n-x_{n-1}|^2\leq\tau(f(x_M)-f(x_N)).}En déduire {|x_{n+1}-x_n|\to0}.
24. Montrer que {|x_N-x_M|\leq\sqrt{2\tau|N-M|}\sqrt{|f(x_M)-f(x_N)|}}pour tous {M,N\in\mathbb N}.

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

25. Montrer, pour {v,t\in\mathbb R}, que {\tau f(\widetilde x)+\frac12|\widetilde x-x|^2\leq\tau f(\widetilde x+tv)+\frac12|\widetilde x+tv-x|^2.}En déduire {\begin{array}{l}2\tau\bigl(f(\widetilde x)+f(\widetilde y)-f(\widetilde x+tv)-f(\widetilde y-tv)\bigr)\\[8pt]\displaystyle\leq|\widetilde x+tv-x|^2+|\widetilde y-tv-y|^2-|\widetilde x-x|^2-|\widetilde y-y|^2.\end{array}\tag{6}}
26. Montrer que le membre de droite de (6) vaut {2tv(\widetilde x-x+y-\widetilde y)+o(t)} lorsque {t\to0}.
27. Choisir {v=\widetilde y-\widetilde x} dans (6). Montrer que le membre de gauche est positif ou nul pour {t\in[0,1]}, puis que {|\widetilde x-\widetilde y|^2\leq(x-y)(\widetilde x-\widetilde y)}.
28. Montrer que {|p_f(x)-p_f(y)|\leq|x-y|}, puis que {(|x_n-x^*|)} est décroissante.

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

29. Montrer que {x_{\varphi(n)+1}\to x^{**}}, puis que {p_f(x^{**})=x^{**}}.
30. Conclure que {x^{**}} minimise {f} et que {x_n\to x^{**}}.

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)}.

31. Montrer que {f} admet un minimiseur sur {C}, noté {x^*}.
32. Si {\|x^*\|\lt 1}, montrer que {\nabla f(x^*)=0}.

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

33. a) Si {x\ne y} et {\|x\|=\|y\|=1}, montrer que {\langle x,v\rangle>0} et {\langle y,v\rangle\lt 0}, où {v=x-y}.
33. b) Si la relation {\nabla f(x^*)=-\lambda x^*} avec {\lambda\geq0} échoue, montrer qu’il existe {v} tel que {\langle v,\nabla f(x^*)\rangle>0} et {\langle v,x^*\rangle>0}, puis obtenir une contradiction.

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}.

34. Montrer que {\nabla f(x)=-Mx}.
35. Décrire l’ensemble des minimiseurs de {f} sur {C}.

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}.

36. a) Montrer que, pour {n\geq1}, {x_n=\frac{(I_d+\tau M)^nx_0}{\|(I_d+\tau M)^nx_0\|}.}
36. b) Calculer {\lim\limits_{n\to+\infty}x_n}. On pourra décomposer {x_0=\sum\limits_i\alpha_ie_i}, poser {I=\{i:\alpha_i\ne0\}}, {\lambda=\max_{i\in I}\lambda_i} et {x_0'=\sum\limits_{i\in I,\lambda_i=\lambda}\alpha_ie_i}.
37. Comment la suite se comporte-t-elle lorsque {\|x_0\|\lt 1} ?
38. Montrer qu’il existe un hyperplan {H} tel que, pour tout {x_0\notin H}, {f(x_n)\to\min_{x\in C}f(x)}.