WikiPrépaLivrets

X ENS Mathématiques PSI 2012Sujet et corrigé

Pas encore noté
Logo concours X-ENS

Explorer les annales

BanqueX-ENSAnnée2012FilièrePSIMatièreMathématiques
Annales X-ENS PSI MathématiquesX-ENS PSI 2012PSI MathématiquesMathématiques 2012

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Corrigé 2
Lire en ligneLaTeXWord
  • Rapport du jury : non disponible

Présentation du sujet

Fonctions coercives, minimum global et méthodes de descente par gradient
Afficher ou masquer la section

Le problème étudie les fonctions coercives sur R^n, montre qu'elles admettent toujours un minimum global, et analyse des méthodes de descente par gradient pour l'approcher. Après un préambule établissant l'existence d'un minimum global, la première partie étudie le cas d'une forme quadratique et la convergence de l'algorithme de gradient à pas constant. La deuxième partie exhibe, sur la fonction carrée, des suites de descente par gradient mal choisies qui ne convergent pas vers le minimum.

  1. 1Préambule : existence d'un minimum globalMontrer qu'une fonction coercive sur R^n admet toujours un minimum global, atteint en un point où le gradient s'annule si la fonction est de classe C1.
  2. 2Partie 1 : cas d'une forme quadratique et algorithme de gradient à pas constantMontrer la coercivité d'une forme quadratique associée à une matrice symétrique définie positive, et étudier la convergence de la suite construite par l'algorithme de gradient à pas constant vers l'unique minimum.
  3. 3Partie 2 : exemples de suites de descente par gradient non convergentesConstruire, pour la fonction carrée, des suites de descente par gradient qui décroissent en valeur mais ne convergent pas vers le minimum global.
  4. 4Partie 3 : définition générale des suites de descente par gradientFormaliser la notion de suite de descente par gradient pour une fonction générale de classe C1, et montrer que pour une fonction coercive la suite des valeurs converge et la suite des points reste bornée.
  5. 5Partie 4 : convergence du gradient et du minimum sous conditions supplémentairesÉtablir, sous des conditions de décroissance suffisante et de minoration du pas, la convergence du gradient vers zéro le long de la suite, puis montrer la convergence de la suite vers l'unique minimum dans le cas d'une fonction coercive strictement convexe d'une variable.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

Banque commune École Polytechnique - ENS de Cachan
PSI

Session 2012

Épreuve de Mathématiques

Durée : 4 heures

Aucun document n'est autorisé

L'usage de calculatrice électronique de poche à alimentation autonome, non imprimante et sans document d'accompagnement, est autorisé selon la circulaire n^∘99018 du 1^(er) février 1999. De plus, une seule calculatrice est admise sur la table, et aucun échange n'est autorisé entre les candidats.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Dans tout le problème, on dit qu'une fonction f définie sur R^n et à valeurs dans R est coercive si et seulement si elle est continue et vérifie
lim_(‖x‖ → + ∞)f(x) = + ∞
où la norme de x correspond à la norme euclidienne sur R^n.
L'objectif du problème est d'étudier certains exemples de fonctions coercives, de montrer en particulier qu'elles possèdent toujours un ou plusieurs minimum global et d'en étudier des méthodes d'approximation. Le préambule contient un résultat utilisé tout au long du problème. Les quatre parties sont assez largement indépendantes.
On note (.,.) le produit scalaire euclidien sur R^n et pour toute fonction f de classe C^1 de R^n dans R, ∇f(x) le vecteur gradient de f au point x formé des dérivées partielles (∂f)/(∂x_i)(x).

PREAMBULE

  1. Soit f une fonction coercive de R^n dans R. Montrer qu'il existe un réel M > 0 tel que si ‖x‖ > M, alors
f(x) ≥ |f(0)| + 1
  1. En déduire qu'il existe un élément x^∗ ∈ R^n tel que
∀x ∈ R^n, f(x^∗) ≤ f(x).
On dit alors que x^∗ est un minimum global de f sur R^n.
3. On suppose de plus que f est de classe C^1 sur R^n. Que peut-on dire de ∇f(x^∗) ?

PARTIE 1

Dans cette partie, on considère la fonction g de R^3 dans R telle que
∀x ∈ R^3, g(x) = 1/2(Ax, x) − (b, x)
où b ∈ R^3 et A ∈ M_3(R) est une matrice symétrique telle que
∃C > 0, ∀x ∈ R^3, (Ax, x) ≥ C‖x‖^2.
  1. Montrer que g est coercive.
  2. Montrer que g est de classe C^1 de R^3 dans R et que
∇g(x) = Ax − b
En déduire que g possède un unique minimum global noté x^∗.
6. On considère la suite (u_k)_(k ∈ N) d'éléments de R^3 telle que u_0 ∈ R^3 quelconque et
∀k ∈ N, u_(k + 1) = u_k − α∇g(u_k)
où α est un réel positif fixé. Montrer que
u_(k + 1) − x^∗ = (I_3 − αA)(u_k − x^∗)
où I_3 désigne la matrice identité de taille 3 .
7. On note L la plus grande valeur propre de A (en valeur absolue). Montrer que si α ∈ ]0, 2/L[, alors la suite (u_k)_(k ∈ N) est convergente vers x^∗.

PARTIE 2

Dans cette partie, on considère la fonction h de R dans R telle que
∀x ∈ R, h(x) = x^2.
On s'intéresse aux suite réelles (x_k)_(k ∈ N), appelées suites de descente par gradient de h, définies de la manière suivante :
x_0 ∈ R et ∀k ∈ N, x_(k + 1) = x_k + ε_k t_k
avec
ε_k = {1 si x_k < 0; − 1 si x_k > 0; 0 si x_k = 0
et où t_k est un réel choisi dans l'intervalle ]0, 2|x_k|[ si x_k ≠ 0 et t_k = 0 si x_k = 0.
8. Montrer que si (x_k)_(k ∈ N) est une suite de descente par gradient de h, alors
∀k ∈ N, h(x_(k + 1)) ≤ h(x_k).
  1. On considère la suite (v_k)_(k ∈ N) telle que v_0 = 2 et
v_(k + 1) = v_k − 1/(2^(k + 1))
Montrer que (v_k)_(k ∈ N) est une suite de descente par gradient pour la fonction h qui ne converge pas vers le minimum global de h.
10. On considère la suite (w_k)_(k ∈ N) telle que w_0 = 2 et
w_(k + 1) = w_k + (− 1)^(k + 1)(2 + 3/(2^(k + 1)))
Montrer que (w_k)_(k ∈ N) est une suite de descente par gradient pour la fonction h non convergente.

PARTIE 3.

Soit x ∈ R^n et f une fonction de classe C^1 de R^n dans R. On note
D_x = {d ∈ R^n, ‖d‖ = 1 et (d, ∇f(x)) < 0}.
  1. Montrer que D_x est non vide si ∇f(x) ≠ 0 et que si d ∈ D_x, alors
T_(d, x) = {t ∈ R_+^∗, f(x + td) < f(x)}
est également non vide.
On considère une suite (x_k)_(k ∈ N) à valeurs dans R^n telle que
x_0 ∈ R^n et ∀k ∈ N, x_(k + 1) = x_k + t_k d_k
avec
{d_k ∈ D_(x_k) et t_k ∈ T_(d_k, x_k) si ∇f(x_k) ≠ 0; d_k = 0 et t_k = 0 si ∇f(x_k) = 0
On dit alors que (x_k)_(k ∈ N) est une suite de descente par gradient pour la fonction f.
12. Vérifier que la définition précédente coïncide bien avec la définition des suites de descente par gradient donnée dans la partie 2 pour la fonction particulière h.
13. Dans le cas général, montrer que si f est de plus une fonction coercive, alors la suite (f(x_k))_(k ∈ N) est convergente et la suite (x_k)_(k ∈ N) est bornée.
14. On reprend dans cette questions les notations et définitions de la partie 1. Montrer que lorsque α appartient à un intervalle de R_+^∗ qu'on déterminera, la suite (u_k)_(k ∈ N) est une suite de descente par gradient pour la fonction g. On pourra commencer par montrer que
g(u_(k + 1)) − g(u_k) = − α‖r_k‖^2 + 1/2α^2(Ar_k, r_k)
avec r_k = ∇g(u_k).

PARTIE 4.

Dans toute cette partie, f désigne une fonction de classe C^1, coercive de R^n dans R et (x_k)_(k ∈ N) une suite de descente par gradient pour la fonction f (c'est à dire définie par la relation (1) de la partie 3).
15. On suppose que la suite (x_k)_(k ∈ N) vérifie de plus la condition suivante:
∀k ∈ N, f(x_(k + 1)) ≤ f(x_k) + m_1 t_k(d_k, ∇f(x_k))
où m_1 est un réel fixé dans ]0, 1[
Montrer que pour toute suite de descente par gradient vérifiant la condition (2), la série de terme général (t_k(d_k, ∇f(x_k)))_(k ∈ N) est minorée puis que
lim_(k → + ∞)t_k(d_k, ∇f(x_k)) = 0
  1. On suppose que la suite (x_k)_(k ∈ N) de descente par gradient de f vérifie la condition (2) et la condition supplémentaire suivante :
∀k ∈ N, t_k ≥ min(C_1, C_2|(d_k, ∇f(x_k))|)
où C_1 et C_2 sont deux réels strictement positifs. Montrer que
lim_(k → + ∞)(d_k, ∇f(x_k)) = 0
  1. On suppose que la suite (x_k)_(k ∈ N) de descente par gradient de f vérifie les conditions (2), (3) et que si ∇f(x_k) ≠ 0,
d_k = − (B∇f(x_k))/(‖B∇f(x_k)‖)
où B est une matrice symétrique de taille n dont les valeurs propres sont strictement positives. Montrer que
lim_(k → + ∞)∇f(x_k) = 0
  1. On suppose dans cette question et la suivante que n = 1 et de plus que f est coercive, de classe C^2 et strictement convexe, c'est à dire :
    ∀(x_1, x_2) ∈ R^2, ∀λ ∈ ]0, 1[, x_1 ≠ x_2 ⟹ f(λx_1 + (1 − λ)x_2) < λf(x_1) + (1 − λ)f(x_2).
    Montrer que f possède un unique minimum global x^∗ sur R.
  2. Les hypothèses de la question précédente sont conservées. A partir d'un réel x_0 quelconque, proposer un algorithme de construction d'une suite (x_k)_(k ∈ N) de descente par gradient pour la fonction f qui vérifie les conditions (2) et (3). En déduire qu'une telle suite est convergente vers l'unique minimum global de f (on admettra que de toute suite réelle bornée on peut extraire une sous suite convergente et que si toutes ces sous-suites convergentes possèdent une même limite, alors la suite est convergente).

Questions fréquentes

4 questions
Sur quels chapitres porte ce sujet de maths X-ENS PSI 2012 ?
Afficher ou masquer la section

Sur quels chapitres porte ce sujet de maths X-ENS PSI 2012 ?

Il porte sur les fonctions de plusieurs variables (gradient, coercivité), les formes quadratiques associées à des matrices symétriques, les suites récurrentes et la convexité, dans le cadre des méthodes de descente par gradient.

Les parties de ce sujet sont-elles indépendantes ?

L'énoncé précise que les quatre parties sont assez largement indépendantes, même si elles s'appuient toutes sur le préambule et que la partie 4 réutilise la définition générale posée en partie 3.

Ce sujet demande-t-il de connaître les algorithmes d'optimisation ?

Oui, le sujet étudie en détail la méthode de descente par gradient, à pas constant puis à pas variable, et les conditions garantissant sa convergence vers un minimum global.

Pourquoi certaines suites de descente par gradient ne convergent-elles pas dans ce sujet ?

La partie 2 construit, sur la fonction carrée, des exemples de suites qui font décroître la valeur de la fonction à chaque étape mais dont les points eux-mêmes ne convergent pas vers le minimum global, faute de condition supplémentaire sur le choix du pas.

Pas de description pour le moment