Optimisation (MML1E31) (M1 MM, 2017-2018)

Examen du vendredi 12 janvier 2018

Corrigé
Les documents suivants sont autorisés :
— Polycopiés distribués en cours et notes de cours manuscrites correspondantes,
— Sujets de TP imprimés et notes manuscrites correspondantes.
La consultation de tout autre document (livres, etc.) et l’utilisation de tout appareil élec-
tronique sont interdites.

Exercice 1. (sur environ 14 points)

On rappelle que l’algorithme de Newton correspond au pseudo-code suivant :
Algorithme 1 : Algorithme de descente de Newton
Données : Un point initial x(0) ∈ Rn , un seuil de tolérance ε > 0, des paramètres
α ∈]0, 12 [ et β ∈]0, 1[ pour la méthode de rebroussement
Résultat : Un point x ∈ Rn proche de x?
Initialiser x :
x ← x(0) ;
k ← 0;
Calculer la première direction de descente :
d(0) = −∇2 f (x(0) )−1 ∇f (x(0) ) ;
Λ(0) = −hd(0) , ∇f (x(0) )i ;
tant que Λ(k) > ε2 faire
1. Déterminer un pas de descente t(k) > 0 au point x(k) selon la direction d(k)
par la méthode de rebroussement avec les paramètres α et β.
2. Mettre à jour x :
x ← x(k+1) = x(k) + t(k) d(k) ;
k ← k + 1;
3. Calculer la nouvelle direction de descente :
d(k) = −∇2 f (x(k) )−1 ∇f (x(k) ) ;
Λ(k) = −hd(k) , ∇f (x(k) )i ;
fin
On rappelle également le théorème de convergence pour la méthode de Newton.

Théorème 1 (Convergence de la méthode de Newton). Soit f : Rn → R une fonction fortement

convexe telle que
∀x, h ∈ Rn , mkhk2 6 h∇2 f (x)h, hi 6 M khk2
avec 0 < m 6 M et dont la matrice hessienne est lipschitzienne pour la constante L > 0

∀x, y ∈ Rn , k∇2 f (x) − ∇2 f (y)kMn (R) 6 Lkx − yk.

1
Soit x(0) un point quelconque de Rn . On pose
m2 m
η = min(1, 3(1 − 2α)) et γ = αβη 2 .
L M2
Alors on a :
— Si k∇f (x(k) )k > η, alors

f (x(k+1) ) − f (x(k) ) 6 −γ.

— Si k∇f (x(k) )k < η, alors la méthode de rebroussement retourne le pas t(k) = 1 et

 2
L (k+1) L (k)
k∇f (x )k 6 k∇f (x )k .
2m2 2m2
En particulier, l’algorithme de Newton converge et atteint un régime de convergence quadra-
tique au bout d’un nombre fini d’itérations.
Le but de cet exercice est d’implémenter la méthode de Newton et de prouver la première
partie du théorème de convergence. Dans toute la suite de l’exercice on considère une fonc-
tion f vérifiant les hypothèses du Théorème 1.

Partie I : Implémentation de l’Algorithme 1 (sur environ 5 points)

1. Rappeler le pseudo-code de la méthode de rebroussement appliquée à une fonction f en
un point x selon une direction de descente d et les paramètres α ∈]0, 12 [ et β ∈]0, 1[.
2. Exprimer le critère de sortie de la méthode de rebroussement pour la direction de descente
de Newton en fonction de x(k) , d(k) , α et Λ(k) .
3. On suppose que les fonctions f = @(x), gradf = @(x) et hessf = @(x) qui
évaluent respectivement f (x), ∇f (x) et ∇2 f (x) sont définies dans Octave. Implémenter
une fonction
function [Xk, FXk] = desc_newton(x0,eps,alph,bet,f,gradf,hessf)
qui applique la méthode de Newton en appelant les trois fonctions f, gradf, et hessf.
Cette fonction renvoie la matrice Xk (de taille n par nombre d’itérations) contenant la
liste des vecteurs x(k) ainsi que la liste des valeurs Fxk de la fonctionnelle f aux points
x(k) .

Partie II : Quelques inégalités (sur environ 3 points)

4. Justifier qu’en tout point x la matrice hessienne ∇2 f (x) est inversible et vérifie
1 1
∀h ∈ Rn , khk2 6 h∇2 f (x)−1 h, hi 6 khk2 .
M m
5. Soit x(k) un point de Rn , et d(k) = −∇2 f (x(k) )−1 ∇f (x(k) ) et Λ(k) = −hd(k) , ∇f (x(k) )i
les quantités associées. Montrer que
1 (k)
kd(k) k2 6 Λ
m
et que
1
k∇f (x(k) )k2 6 Λ(k) .
M

2
Partie III : Phase compensée (sur environ 6 points)
On suppose dans cette partie que l’algorithme a atteint l’itération k et on pose

d(k) = −∇2 f (x(k) )−1 ∇f (x(k) ) et Λ(k) = −hd(k) , ∇f (x(k) )i.

6. Montrer que pour tout t ∈ R,

M 2 (k)
f (x(k) + td(k) ) 6 f (x(k) ) − tΛ(k) + tΛ .
2m
m
7. En déduire que pour tout t tel que 0 < t 6 , on a
M
f (x(k) + td(k) ) 6 f (x(k) ) − αΛ(k) .

8. Soit t(k) le pas renvoyé par la méthode de rebroussement permettant de définir x(k+1) =
m
x(k) + t(k) d(k) . Montrer que t(k) > β M et que

f (x(k+1) ) 6 f (x(k) ) − αt(k) Λ(k) .

9. En déduire que
m
f (x(k+1) ) − f (x(k) ) 6 −αβ k∇f (x(k) )k2 .
M2
10. Conclure.

Solution de l’exercice 1.
Algorithme 2 : Algorithme de calcul du pas de descente par méthode de rebroussement
Données : Un point x ∈ Rn , une direction de descente associée d ∈ Rn , deux réels
α ∈]0, 12 [ et β ∈]0, 1[
Résultat : Un pas de descente t > 0
Initialiser t :
1.
t ← 1;
tant que f (x + td) > f (x) + αth∇f (x), di faire
Réduire t d’un facteur β :
t ← βt ;
fin

2. f (x + td) 6 f (x) + αth∇f (x), di est ici

f (x(k) + td(k) ) 6 f (x(k) ) + αth∇f (x(k) ), d(k) i = f (x(k) ) − αtΛ(k) .

3.

% Descente de Newton
function [Xk, FXk] = desc_newton(x0, eps, alph, bet, f, gradf, hessf)
% Initialisation
x=x0;
k=0;
fx = f(x);
gfx = gradf(x);

3
 d = -hessf(x)\gfx;
lambda = -d’*gfx;
Xk = x;
FXk = fx;
while(lambda>eps^2 && k < 100)
t = 1;
xk = x;
fxk = fx;
x = xk + t*d;
fx = f(x);
disp([k, t])
while(fx > fxk - alph*t*lambda)
t = bet*t;
x = xk + t*d;
fx = f(x);
disp([k, t])
end
k = k+1;
Xk = [Xk, x];
FXk = [FXk, fx];
gfx = gradf(x);
d = -hessf(x)\gfx;
lambda = -d’*gfx;
end
ned

4. Comme f est fortement convexe, ∇f 2 (x) est définie positive et donc inversible en tout x.
Les valeurs propres de ∇f 2 (x) sont comprises entre m et M , et donc les valeurs propres
de ∇2 f (x)−1 sont comprises entre M1 et m1 , d’où l’encadrement annoncé.
5. En utilisant la forte convexité,

Λ(k) = −hd(k) , ∇f (x(k) )i = hd(k) , ∇2 f (x(k) )d(k) i > mkd(k) k2 ,

d’où l’inégalité annoncée.

Par ailleurs,
1
Λ(k) = −hd(k) , ∇f (x(k) )i = h∇2 f (x(k) )−1 ∇f (x(k) ), ∇f (x(k) )i > k∇f (x(k) )k2
M
en utilisant la question précédente.
6. Soit t ∈ R. Par l’égalité de Taylor Maclaurin d’ordre 2, il existe z ∈]x(k) , x(k) + td(k) [ tel
que
t2
f (x(k) + td(k) ) = f (x(k) ) + th∇f (x(k) ), d(k) i + h∇2 f (z)d(k) , d(k) i.
2
2 2
Par l’inégalité h∇ f (z)h, hi 6 M khk on a

(k) (k) (k) (k) (k)t2 (k) 2

f (x + td ) 6 f (x ) + th∇f (x ), d i + M kd k .
2

4
 1 (k)
Enfin, h∇f (x(k) ), d(k) i = −Λ(k) et on a montré que kd(k) k2 6 m
Λ . On obtient donc
M 2 (k)
f (x(k) + td(k) ) 6 f (x(k) ) − tΛ(k) + tΛ .
2m
m
7. Pour tout t tel que 0 < t 6 M
,
M 2 M m 1
t 6 t = t.
2m 2m M 2
Ainsi,
1
f (x(k) + td(k) ) 6 f (x(k) ) − tΛ(k) 6 f (x(k) ) − αΛ(k) .
2
8. Comme vu à la question 2. le critère d’arrêt de la méthode de rebroussement est

f (x(k) + td(k) ) 6 f (x(k) ) + αth∇f (x(k) ), d(k) i = f (x(k) ) − αtΛ(k) .

m
Donc d’après la question précédente, tous les pas t de l’intervalle ]0, M ] vérifient le critère
d’arrêt de la méthode de rebroussement. Ainsi, la méthode de rebroussement renvoie un
pas t(k) = β n tel que
(a) Le critère d’arrêt est vérifié en t(k) = β p , ce qui implique

f (x(k+1) ) 6 f (x(k) ) − αt(k) Λ(k) .

(b) Le critère d’arrêt n’est pas vérifié en t = β p−1 (pas précédent qui a été refusé), ce
m
qui implique β p−1 > M .
m
On a donc t(k) = β p > β M , et donc l’inégalité large a fortiori.
9. On vient de montrer que

f (x(k+1) ) − f (x(k) ) 6 −αt(k) Λ(k) .

m 1
Grâce aux inégalités t(k) > β M et Λ(k) > M
k∇f (x(k) )k2 on obtient
m
f (x(k+1) ) − f (x(k) ) 6 −αβ k∇f (x(k) )k2 .
M2
10. Si on a k∇f (x(k) )k > η, alors
m 2
f (x(k+1) ) − f (x(k) ) 6 −αβ η = γ,
M2
ce qui prouve la première partie du théorème.

Exercice 2. (sur environ 8 points)

Dans cet exercice on considère f : Rn → R une fonctionnelle quadratique
1
f (x) = hAx, xi − hb, xi + c,
2
où A ∈ Mn (R) est une matrice carrée symétrique définie positive, b ∈ Rn et c ∈ R. On rappelle
que f est de classe C ∞ sur Rn et que pour tout x ∈ Rn ,

∇f (x) = Ax − b et ∇2 f (x) = A.

5
 1. Démontrer que f admet un unique minimum global x? donné par x? = A−1 b.
Dans la suite de l’exercice on étudie la convergence de l’algorithme de descente de gra-
dient à pas fixe appliqué à cette fonctionnelle quadratique. Pour une fonction quelconque, cet
algorithme est décrit par le pseudo-code suivant :
Algorithme 3 : Algorithme de descente de gradient à pas fixe
Données : Un point initial x(0) ∈ Rn , un seuil de tolérance ε > 0, un pas fixe t > 0
Résultat : Un point x ∈ Rn proche de x?
Initialiser x :
x ← x(0) ;
k ← 0;
tant que k∇f (x)k > ε faire
1. Mettre à jour x avec le pas fixe t dans la direction de descente −∇f (x(k) ) :
x ← x(k+1) = x(k) − t∇f (x(k) ) ;
k ← k + 1;
fin

2. Soit k ∈ N. Montrer que

x(k+1) − x? = (In − tA)(x(k) − x? ).

En déduire une expression de x(k) − x? en fonction A, t, et x(0) − x? .

3. Soit 0 < λ1 6 λ2 6 · · · 6 λn les valeurs propres de A et u1 , u2 , . . . , un des vecteurs
propres associés formant une base orthonormée de Rn . En introduisant la décomposition
du vecteur x(0) − x? dans la base (u1 , u2 , . . . , un ), montrer que la suite (x(k) )k∈N converge
vers x? quelque soit la valeur de x(0) si et seulement si

∀i ∈ {1, . . . , n}, |1 − tλi | < 1.

4. Montrer que

∀i ∈ {1, . . . , n}, |1 − tλi | 6 max(|1 − tλ1 |, |1 − tλn |).

5. En déduire l’intervalle des valeurs de t pour lesquelles l’Algorithme 3 converge et montrer

que
kx(k) − x? k 6 max(|1 − tλ1 |, |1 − tλn |)k kx(0) − x? k.
6. Tracer l’allure des graphiques des fonctions t 7→ |1 − tλ1 | et t 7→ |1 − tλn |. Pour quelle
valeur de t le membre de droite de l’inégalité précédente tend-il le plus vite vers 0 ?

Solution de l’exercice 2.
1. Pour tout x ∈ Rn , ∇2 f (x) = A est définie positive, donc f est strictement convexe. Ainsi
f admet au plus un minimum global x? et il est caractérisé par l’équation ∇f (x) = 0. Or
comme A est inversible,

∇f (x) = 0 ⇔ Ax = b ⇔ x = A−1 b.

Et donc f admet un unique minimum global x? égal à A−1 b.

6
2. On peut (par exemple) partir du terme de droite.

(In − tA)(x(k) − x? ) = x(k) − t(Ax(k) − Ax? ) − x? .

Or Ax? = b, et donc Ax(k) − Ax? = Ax(k) − b = ∇f (x(k) ). Ainsi,

(In − tA)(x(k) − x? ) = x(k) − t∇f (x(k) ) − x? = x(k+1) − x? .

On peut aussi écrire les équations

x(k+1) = x(k) − t∇f (x(k) ) et x? = x? − t∇f (x? )

et les soustraire pour obtenir l’équation demandée. Par récurrence immédiate on obtient

x(k) − x? = (In − tA)k (x(0) − x? ).

3. Les vecteurs propres (u1 , u2 , . . . , un ) de A sont aussi des vecteurs propres de la matrice
In − tA dont les valeurs propres sont 1 − tλi . Si on note
n
X
x(0) − x? = αi ui
i=1

la décomposition de x(0) − x? dans la base (u1 , u2 , . . . , un ), on a alors

n
! n n
X X X
(k) ? k k
x − x = (In − tA) αi ui = αi (In − tA) ui = αi (1 − tλi )k ui .
i=1 i=1 i=1

Alors x(k) −
x? tend vers 0 quelque soit x(0) si et seulement si pour tout i la suite
(1 − tλi )k k∈N tend vers 0. On en déduit que x(k) − x? tend vers 0 quelque soit x(0)
si et seulement si
∀i ∈ {1, . . . , n}, |1 − tλi | < 1.
4. Montrer que

∀i ∈ {1, . . . , n}, |1 − tλi | 6 max(|1 − tλ1 |, |1 − tλn |).

Soit i ∈ {1, . . . , n}. On a λ1 6 λi 6 λn et donc

1 − tλn 6 1 − tλi 6 1 − tλ1 .

Si 1 − tλi > 0, alors on en déduit que

0 6 1 − tλi = |1 − tλi | 6 1 − tλ1 = |1 − tλ1 |.

Si 1 − tλi 6 0, alors on en déduit que

0 6 −(1 − tλi ) = |1 − tλi | 6 −(1 − tλn ) = |1 − tλn |.

Dans les deux cas on a bien

|1 − tλi | 6 max(|1 − tλ1 |, |1 − tλn |).

7
5. Finalement, il suffit que la condition |1 − tλi | < 1 soit vérifiée pour i = 1 et i = n. Or
2
|1 − tλ1 | < 1 ⇔ −1 < 1 − tλ1 < 1 ⇔ 0 < t <
λ1

et de même, |1 − tλn | < 1 équivaut à 0 < t < λ2n . Comme λ1 6 λn , t < λ2n implique
t < λ21 . Au final, l’algorithme converge pour t tel que t ∈]0, λ2n [.
On vient de montrer que kIn − tAkMn (R) = max(|1 − tλ1 |, |1 − tλn |). Or on a

kx(k) − x? k = k(In − tA)k (x(0) − x? )k 6 kIn − tAkkMn (R) k(x(0) − x? )k,

d’où l’inégalité annoncée.

6. En traçant le graphe des deux fonctions, on voit que la fonction

t 7→ max(|1 − tλ1 |, |1 − tλn |)

est minimale lorsque les deux courbes se croisent, soit au point pour lequel

tλn − 1 = 1 − tλ1
2
ce qui donne t = λ1 +λn
.