Travaux dirigés.
Optimisation & Analyse convexe
Séance 4 : Algorithmes pour l’optimisation sans contrainte
Dans tous les exercices suivants, A désigne une matrice symétrique définie positive
N × N, de valeurs propres 0 < λ1 ≤ . . . ≤ λN , et b ∈ IRN . Pour v ∈ IRN , on pose
1
J(v) = (Av, v) − (b, v).
2
Notons u le point de minimum de J sur IRN .
Exercice 1 (Algorithme de gradient à pas fixe).
1. Montrer que l’algorithme de gradient à pas fixe
un+1 = un − ρ∇J (un )
converge pour 0 < ρ < 2/λN .
2. Montrer que la vitesse maximale de convergence est obtenue pour ρ = 2/(λ1 + λN )
et préciser sa valeur.
Exercice 2 (Algorithme de gradient à pas optimal).
On considère l’algorithme du gradient à pas optimal :
un+1 = un + ρn dn ,
où dn = −∇J (un ) et ρn réalise le minimum de inf J(un + ρdn ).
ρ∈IR
1. Montrer que pour tout n, (dn+1 , dn ) = 0. Calculer ρn .
2. On pose en = un − u. Montrer que
(dn , dn )2
ken+1 k2A = 1− ken k2A ,
(Adn , dn ) (A−1 dn , dn )
où kvk2A = (Av, v). En déduire que :
n+1 λN − λ1
ke kA ≤ ken kA . (1)
λN + λ1
Ind. On pourra utiliser le résultat suivant (admis) :
(x, x)2 4λ1 λN
(Inégalité de Kantorovich) min = .
x∈IR (Ax, x)(A x, x)
N −1 (λ1 + λN )2
2 Travaux dirigés.
Exercice 3 (Algorithme du gradient conjugué).
Il s’agit de l’algorithme de descente à pas optimal :
un+1 = un + ρn dn (2)
avec
k∇J(un )k2 n−1 (−∇J (un ), dn )
d0 = −∇J (u0 ), dn = −∇J (un ) + d , ρn = .
k∇J(un−1 )k2 (Adn , dn )
Rappelons que le principe de cette méthode est le suivant :
partant de u0 ∈ IRn , une suite (un ) est construite telle que :
un+1 ∈ un + Gn et J(un+1 ) = inf J(v) (3)
v∈un +Gn
avec Gn = vect(∇J (u0), . . . , ∇J(un )).
Dans tout l’exercice, on note kvk2A = (Av, v) pour v ∈ IRN .
1. Vérifier que
1
J(v) − J(u) = kv − uk2A ∀v ∈ IRN . (4)
2
2. Montrer que l’espace Gn est engendré par {∇J(u0 ), A∇J(u0 ), . . . , An ∇J(u0 )}.
3. Pour k ≥ 0, on pose ek = uk − u.
(a) Soit v ∈ un + Gn . Montrer qu’il existe un polynôme Q de degré n tel que :
v = u0 + Q(A)∇J(u0 ).
(b) En utilisant (3) et (4), montrer que :
ken+1 kA = min{kP (A)e0 kA , P ∈ Pn+1 } (5)
où et Pn désigne l’ensemble des polynômes P de degré n tels que P (0) = 1.
4. Montrer que
kP (A)e0 k2A ≤ ke0 k2A max P 2 (λi ) ∀P ∈ Pk .
i
En déduire que
√ n
κ−1 λN
n
ke kA ≤ 2 √ ke0 kA avec κ = .
κ+1 λ1
b+a
(Ind. min{kpkL∞ ([a,b]) : p ∈ Pk } = 1/Tk b−a , où Tk désigne le polynôme de Tchebychev
de degré k. De plus on a :
q k
! b
b+a
b
+1 1 a
+1
a
Tk = Tk b
> q , pour b > a.
b−a a
−1 2 b
−1
a
Travaux dirigés. 3
Exercice 4 (Comparaison avec les méthodes itératives) . On suppose maintenant
que la matrice A et le vecteur b sont donnés par :
2 −1 0 . . . 0
.. .. f (x1 )
−1 2 −1 . .
1 f (x2 )
.. .. .. . ,
A= 2 . . . .. b = .. .
h 0 .
..
. . . . −1 2 −1 f (xn )
0 . . . 0 −1 2
où h = 1/(N + 1), xi = ih et f est une fonction continue sur IR. Le but de cet exercice est
de comparer les méthodes de descente gradient et gradient conjugué avec les méthodes
itératives Jacobi et Gauss-Seidel.
1. Donner une interprétation physique au problème de minimisation.
2. Montrer que les valeurs propres de la matrice A sont les :
4 kπh
λk = 2
sin2 ( ) 1 ≤ k ≤ N,
h 2
associées aux vecteurs propres ϕk
T
ϕk = sin(kπh)
sin(2kπh) ... sin((N − 1)kπh) sin(Nkπh) .
3. Evaluer les vitesses de convergence du gradient et gradient conjugué pour h petit.
4. Calculer le rayon spectral ρ(J ) de la matrice de Jacobi utilisée pour la résolution
du système d’optimalité. Evaluer ρ(J ) et la vitesse de convergence de la méthode
pour h petit. Que peut-on en déduire ?
5. Calculer le rayon spectral ρ(G) de la matrice de Gauss-Seidel. Evaluer la vitesse de
convergence pour h petit. Que peut-on en déduire ?
6. Estimer le nombre d’itérations nécessaires pour obtenir la convergence à une précision
ε donnée pour l’une quelconque de ces méthodes.
Application : n = 99, ε = 10−3 .