Université de Maine – Master 2 - Big Data – 2015-2016. Page n˚1.
Feuille de TP 1 – Algorithme de descente de gradient
1 Algorithme à pas fixe
1.1 En dimension 1
Exercice 1.1. On veut minimiser la fonction suivante :
f (x) = (x − 1)(x − 2)(x − 3)(x − 5).
1. Tracer cette fonction sur l’intervalle [0, 6].
2. Écrire l’algorithme de descente du gradient à pas fixe en R. On arrêtera l’algorithme quand l’écart
entre deux valeurs successives est inférieur à 0,001.
3. Si x0 désigne le point de départ de l’algorithme et η le pas (fixe), tester avec les valeurs suivantes :
– x0 = 5, η = 0, 001.
– x0 = 5, η = 0, 01.
– x0 = 5, η = 0, 1.
– x0 = 5, η = 0, 17.
– x0 = 5, η = 1.
– x0 = 0, η = 0, 01.
On fera tourner un compteur calculant le nombre d’itérations avant l’arrêt de la boucle. Que
remarque-t-on ?
1.2 En dimension 2
Exercice 1.2. On considère d’abord la fonction
f (x, y) = x2 + 0, 25xy + y 2 .
Observez l’algorithme de descente de gradient quand le point initial est (x0 = −0, 9, y0 = 1) et quand il
vaut (x0 = −1, y0 = 1) avec un pas η = 0, 01.
Exercice 1.3. La fonction de Rosenbrock est la suivante :
1
f (x, y) = (1 − x)2 + (y − x2 )2 .
100
Elle est connue pour être difficile à minimiser. Son minimum vaut 0 et est atteint au point (1, 1). Program-
mer l’algorithme de descente de gradient à partir du point initial est (x0 = −1, y0 = 0). Qu’observe-t-on ?
1.3 En dimension supérieure
On considère la matrice
3 −1 0 0 0
−1 12 −1 0 0
A=
0 −1 24 −1 0
0 0 −1 48 −1
0 0 0 −1 96
Semestre 2. Copyright c A. Brouste, A. Popier apopier@[Link]. GNU FDL Copyleft. Page n˚1.
Université de Maine – Master 2 - Big Data – 2015-2016. Page n˚2.
et le vecteur
1
2
b=
3 .
4
5
Sur R5 , on veut minimiser la fonction
1
J(x) = hx, Axi − hb, xi.
2
Exercice 1.4.
1. Vérifier que A est symétrique définie positive. On calculera ses valeurs propres via la fonction eigen.
Donner également ρ1 et ρ5 la plus petite et la plus grande valeur propre.
J admet donc un unique minimum sur R5 . L’algorithme du gradient à pas fixe défini par
xk+1 = xk − ηdk , dk = Axk − b,
converge vers x pour toute initialisation x0 si η est choisi tel que 0 < η < 2ρ1 /(ρ5 )2 (cf. cours). Pour ce
problème, on peut montrer qu’il suffit de prendre ρ < 2/ρ5 et que la vitesse maximale de convergence est
obtenue pour le choix η = 2/(ρ1 + ρ5 ).
2. L’implémenter sous R. On le testera avec x0 = (0, 0, 0, 0, 0) et η = 1/(ρ1 + ρ5 ) et η = 2/(ρ1 + ρ5 ).
On arrêtera l’algorithme quand l’écart entre deux valeurs successives est inférieur à 10−5 .
2 Algorithme à pas variable
Exercice 2.1. On reprend la fonction de l’exercice 1.2.
1. Montrer que cette fonction se met sous la forme
1 x
f (x, y) = h(x, y), M i
2 y
où M est une matrice de dimension 2 × 2 à expliciter.
2. On considère l’algorithme de gradient qui suit :
hdk , dk i
xk+1 = xk − ηk dk , dk = M xk , ηk = .
hdk , M dk i
Implémenter cet algorithme en initialisant x0 = (−1, 1), et comparer avec les résultats obtenus dans
l’exercice 1.2.
Exercice 2.2. On considère le même problème que dans l’exercice 1.4. Mais au lieu de prendre un pas
η, on va l’optimiser en choisissant :
hdk , dk i
xk+1 = xk − ηk dk , dk = Axk − b, ηk = .
hdk , Adk i
Implémenter cet algorithme et comparer avec les résultats obtenus dans l’exercice 1.4.
Semestre 2. Copyright c A. Brouste, A. Popier apopier@[Link]. GNU FDL Copyleft. Page n˚2.