Scribd
Importer
7 vues2 pages

TD4EPT

Ce document présente un exercice sur l'optimisation, axé sur les algorithmes de gradient à pas fixe et optimal, ainsi que sur l'algorithme du gradient conjugué. Il aborde la convergence de ces algorithmes pour une matrice symétrique définie positive et fournit des démonstrations mathématiques pour chaque méthode. Les exercices incluent des calculs de convergence et des inégalités liées aux valeurs propres de la matrice.

Transféré par

Batman
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
7 vues2 pages

TD4EPT

Ce document présente un exercice sur l'optimisation, axé sur les algorithmes de gradient à pas fixe et optimal, ainsi que sur l'algorithme du gradient conjugué. Il aborde la convergence de ces algorithmes pour une matrice symétrique définie positive et fournit des démonstrations mathématiques pour chaque méthode. Les exercices incluent des calculs de convergence et des inégalités liées aux valeurs propres de la matrice.

Transféré par

Batman
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Ecole Polytechnique de Tunisie 2022/2023

Optimisation: TD 4
Classe : 1ère année M. Moakher

Dans tous les exercices suivants, A désigne une matrice N × N symétrique définie positive de valeurs
propres 0 < λ1 ≤ · · · ≤ λN , et b ∈ RN . Pour v ∈ RN , on pose

J(v) = 12 ⟨Av, v⟩ − ⟨b, v⟩.

Notons u le point de minimum de J sur RN .

Exercice 1. (Algorithme de gradient à pas fixe)


1. Montrer que l’algorithme de gradient à pas fixe

u(n+1) = u(n) − ρ∇J(u(n) )

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 :

u(n+1) = u(n) + ρn d(n) ,

où d(n) = −∇J(u(n) ) et ρn réalise le minimum de

inf J(u(n) + ρd(n) ).


ρ∈R

1. Montrer que pour tout n, ⟨d(n+1) , d(n) ⟩ = 0. Calculer ρn .

2. On pose e(n) = u(n) − u. Montrer que


⟨d(n) , d(n) ⟩2
 
(n+1) 2
∥e ∥A = 1 − ∥e(n) ∥2A ,
⟨Ad(n) , d(n) ⟩⟨A−1 d(n) , d(n) ⟩
où ∥v∥2A = ⟨Av, v⟩. En déduire que :
 
(n+1) λN − λ1
∥e ∥A ≤ ∥e(n) ∥A .
λN + λ1

Indication : On pourra utiliser l’inégalité de Kantorovich


⟨x, x⟩2 4λ1 λN
≥ .
(Ax, x)(A−1 x, x) (λ1 + λN )2

1
Exercice 3. (Algorithme du gradient conjugué)
Il s’agit de l’algorithme de descente à pas optimal :

u(n+1) = u(n) + ρn d(n)

avec
∥∇J(u(n) )∥2 (n−1) ⟨−∇J(u(n) ), d(n) ⟩
d(0) = −∇J(u(0) ), d(n) = −∇J(u(n) ) + d , ρn = .
∥∇J(u(n−1) )∥2 ⟨Ad(n) , d(n) ⟩

Rappelons que le principe de cette méthode est le suivant :


Partant de u(0) ∈ Rn , une suite (u(n) ) est construite telle que

u(n+1) ∈ u(n) + Gn et J(u(n+1) ) = inf J(v) (1)


v∈u(n) +Gn

avec Gn = vect(∇J(u(0) ), . . . , ∇J(u(n) )).


Dans tout l’exercice, on note ∥v∥2A = ⟨Av, v⟩ pour v ∈ RN .

1. Vérifier que
J(v) − J(u) = 21 ∥v − u∥2A , ∀v ∈ RN . (2)

2. Montrer que l’espace Gn est engendré par {∇J(u(0) ), A∇J(u(0) ), . . . , An ∇J(u(0) )}.

3. Pour n ≥ 0, on pose e(n) = u(n) − u.


(a) Soit v ∈ u(n) + Gn . Montrer qu’il existe un polynôme Q de degré n tel que :

v = u(0) + Q(A)∇J(u(0) ).

(b) En utilisant (1) et (2), montrer que :

∥e(n+1) ∥A = min{∥P (A)e(0) ∥A , P ∈ Pn+1 },

où et Pn désigne l’ensemble des polynômes P de degré n tels que P (0) = 1.

4. Montrer que
∥P (A)e(0) ∥2A ≤ ∥e(0) ∥2A max P 2 (λi ), ∀ P ∈ Pn .
i

En déduire que √ n
(n) κ−1 λN
∥e ∥A ≤ √ ∥e(0) ∥A avec κ = .
κ+1 λ1
b+a

(Ind. min{∥p∥L∞ ([a,b]) : p ∈ Pn } = 1/Tn b−a , où Tn désigne le polynôme de Tchebychev de degré n.
De plus on a :
q n
! b

b+a
 b
+1 1 a
+1
a
Tn = Tn b
> q  , pour b > a.
b−a a
−1 2 b
−1
a

Vous aimerez peut-être aussi