Calcul Différentiel 2 et Optimisation Numérique (2025)
Feuille de TD n°6
Exercice 1 (régression polynomiale). Soit (xi )1≤i≤I et (yi )1≤i≤I deux familles de réels. On
cherche a ∈ Rn+1 solution du problème d’optimisation
I
X
min
n+1
E(a), E(a) := |a1 + a2 xi + · · · + an+1 xni − yi |2 .
a∈R
i=1
1. Donner une interprétation de ce problème.
2. Montrer qu’il existe une matrice M ∈ Sn+1 , un vecteur b ∈ Rn+1 et un réel c ∈ R tels que
E(a) = 12 ⟨a, M a⟩ − ⟨b, a⟩ + c. Calculer M , b et c.
3. Montrer que M est semidéfinie positive.
On suppose pour la suite que I ≥ n + 1 et qu’au moins n + 1 des points x1 , . . ., xI sont deux à
deux distincts.
4. Montrer qu’alors M est définie positive.
5. Que peut-on dire de l’ordre de convergence de la méthode de descente de gradient à pas
fixe appliquée à la minimisation de la fonction E ? Et de celui de la méthode de descente
de gradient à pas optimal ?
Exercice 2. Soient A ∈ Sd++ , b ∈ Rd , et (xk )k≥0 une suite d’itérées de la méthode de descente
de gradient à pas fixe τ ∈]0, 2/λd (A)[ appliquée à la minimisation de la fonction f : x 7→
1 −1
2 ⟨x, Ax⟩ − ⟨b, x⟩. Soit x∗ := A b.
1. Montrer que xk − x∗ = (Id − τ A)k (xk − x∗ ).
2. En déduire qu’il existe une matrice P ∈ SO(d), ne dépendant pas de τ , telle que xk − x∗ =
P (D(τ ))k P ⊤ (x0 − x∗ ) avec D(τ ) = diag(1 − τ λ1 (A), . . . , 1 − τ λd (A)).
Pd
3. En déduire que xk − x∗ = i=1 (1 − τ λi (A))k ⟨x0 − x∗ , pi ⟩pi , où les (pi )1≤i≤d sont les
colonnes de P .
4. À quelle condition sur la matrice A existe-t-il x0 = ̸ x∗ pour lequel la méthode de descente
de gradient à pas fixe converge linéairement à un taux strictement inférieur à max(τ λd (A)−
1, 1 − τ λ1 (A)) ?
5. Donner une condition sur x0 pour que la méthode de descente de gradient à pas fixe ne
converge linéairement à aucun taux strictement inférieur à max(τ λd (A) − 1, 1 − τ λ1 (A)).
On suppose que ⟨x0 − x∗ , pi ⟩ ≠ 0 pour tout i ∈ {1 . . . , d}.
6. Montrer qu’il existe un unique τ∗ ∈]0, 2/λd (A)[ pour lequel la méthode de descente de
gradient à pas fixe τ∗ converge linéairement à taux (Cond(A) − 1)/(Cond(A) + 1). Donner
la valeur de τ∗ .
7. Étudier le comportement de sgn(⟨xk − x∗ , pi ⟩), pour tout i ∈ {1, . . . , d}, en fonction de τ .
Que peut-on dire si τ < τ∗ ? Si τ > τ∗ ?
1
Exercice 3. Soit D := diag(µ, ν) avec 0 < µ ≤ ν. Soit (Xk )k≥0 la suite des itérées de la méthode
de descente de gradient à pas optimal appliquée à la fonction f : R2 → R, X 7→ 12 ⟨X, DX⟩. On
note (xk , yx ) les coefficients de Xk .
1. Calculer xk+1 et yk+1
2. Que se passe-t-il si x0 = 0 ou y0 = 0 ? Que se passe-t-il si µ = ν ?
On suppose maintenant que x0 > 0, y0 > 0 et ν > µ. Pour tout k ∈ N, soit rk := yk /xk .
3. Montrer que la suite (rk )k≥0 est périodique de période 2.
4. Calculer xk+2 en fonction de xk et yk+2 en fonction de yk . Qu’en déduit-on sur la conver-
gence de la suite (Xk )k≥0 ?
5. Que se passe-t-il lorsque r0 = µ/ν ? Lorsque r0 est proche de 0 ? Lorsque r0 est très grand ?
Exercice 4. On dit qu’un ensemble X ⊂ Rd est convexe si, pour tous points x, y ∈ X et pour
tout t ∈ [0, 1], le point (1 − t)x + ty appartient à X. Si X ⊂ Rd est un ensemble convexe, on dit
qu’une fonction f : X → R est convexe si pour tous points x, y ∈ X et pour tout t ∈ [0, 1], on a
f ((1 − t)x + ty) ≤ (1 − t)f (x) + tf (y) ; on dit qu’une fonction f : R2 → R est convexe sur X si sa
restriction à X est convexe.
Soit f ∈ C 2 (Rd ) une fonction admettant un minimum local en un point x∗ ∈ Rd . On suppose
qu’il n’existe aucun δ > 0 tel que f soit convexe sur B(x∗ , δ). Montrer que ∇2 f (x∗ ) est semidéfinie
positive, mais pas définie positive. Le résultat du cours sur la convergence de la méthode de
descente de gradient à pas fixe s’applique-t-il ?
Exercice 5. Soit f ∈ C 2 (Rd ) une fonction strictement convexe. Soit x∗ ∈ R2 le point auquel
f admet son minimum. On suppose que f (x∗ ) = 0. Soit φ ∈ C 2 (R+ ) une fonction convexe
strictement croissante telle que φ′ (0) = 0. On considère la fonction g : x 7→ φ(f (x)).
1. Montrer que g est strictement convexe et atteint son unique minimum (local et global)
en x∗ .
2. Calculer ∇g(x) et ∇2 g(x) en tout point x ∈ R2 . Que peut-on dire de ∇2 g(x∗ ) ?
3. Soit (xk )k≥0 une suite d’itérées de la méthode de descente de gradient à pas fixe τ > 0
appliquée à la minimisation de g. On suppose que (xk )k≥0 converge vers x∗ .
(a) Montrer que pour tout ε > 0, il existe δ > 0 tel que si xk ∈ B(x∗ , δ), alors
∥xk+1 − x∗ ∥ ≥ (1 − τ ε)∥xk − x∗ ∥.
(b) Qu’en déduit-on sur la convergence de la suite (xk )k≥0 ?
4. Comparer le comportement la méthode de descente de gradient à pas optimal lorsqu’elle
est appliquée à la fonction f et lorsqu’elle est appliquée à la fonction g.
5. Soit A ∈ Sd++ . Que peut-on dire de la méthode de descente de gradient à pas fixe et
de la méthode de descente de gradient à pas optimal lorsqu’elles sont appliquées à la
minimisation de la fonction f : x 7→ 14 ⟨x, Ax⟩2 ?
Espaces vectoriels euclidiens, projections orthogonales et mi-
nimisation
Exercice 6. Soit H un espace vectoriel et soit ⟨·, ·⟩ un produit scalaire sur H, de norme associée
∥ · ∥.
2
1. (Identité du parallélogramme). Montrer que
∀x, y ∈ H, 2∥x∥2 + 2∥y∥2 = ∥x + y∥2 + ∥x − y∥2 ,
2. Montrer que ∥ · ∥2 est une fonction strictement convexe.
3. (Cauchy-Schwarz) Montrer que ⟨x, y⟩ ≤ ∥x∥ · ∥y∥.
4. (Projection orthogonale) Soit E ⊂ H un sous-espace vectoriel de dimension finie et soit
x ∈ H. Montrer que la fonction Nx : E → R définie par Nx (v) := ∥v − x∥2 est continue et
coercive sur E.
5. En déduire que Nx admet un minimiseur sur E. Montrer que ce minimiseur est unique.
On appelle ce minimiseur la projection orthogonale de x sur E, et on la note PE (x).
6. Montrer que pour tout v ∈ E, on a ⟨x, v − PE (x)⟩ = 0.
Exercice 7. Soit H un espace euclidien de dimension n. On veut déterminer certains propriétés
des hyperplans E de H (i.e. des sous-espaces vectoriels de dimension n − 1 de H).
1. Montrer que si x ∈ H\{0}, alors Ex := {v ∈ H , ⟨x, v⟩ = 0} est un hyperplan de H.
2. (Théorème de représentation de Riesz ) Montrer que pour toute forme linéaire φ ∈ L(H, R)
il existe x = xφ ∈ H tel que
∀y ∈ H, φ(y) = ⟨xφ , y⟩.
3. Montrer que pour tout n ∈ N il existe un polynôme qn de degré n à coefficients réels tel
que, pour tout polynôme Pn de degré n on ait
Z 1
qn Pn = 2Pn′′ (6) − 3Pn (1) + Pn (−5).
0
4. Montrer que pour tout hyperplan E de H il existe x = xE ∈ H tel que
E = {y ∈ H , ⟨xE , y⟩ = 0}.
