Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU GRADIENT. PROFESSEUR BENZINE RACHID .pdf



Nom original: CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU GRADIENT. PROFESSEUR BENZINE RACHID.pdf

Ce document au format PDF 1.4 a été généré par TeX / pdfTeX-1.11a, et a été envoyé sur fichier-pdf.fr le 07/04/2016 à 14:17, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 667 fois.
Taille du document: 160 Ko (23 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


CONVERGENCE ET VITESSE DE
CONVERGENCE DE LA METHODE DU
GRADIENT
PROFESSEUR BENZINE RACHID.

CHAPTER 1

Etude de la convergence et de la vitesse de
convergence de la méthode du gradient pour les
fonctions quadratiques strictement convexes
1. Rappel sur quelques propriétés des matrices symétriques
dé…ni-positives
Dans toute cette partie, on considère une matrice carrée d’ordre n; Q = [qij ]
symetrique et dé…nie positive, c’est à dire qu’on a QT = Q et
8x 2 Rn ; x 6= 0; alors xT Qx > 0:
Notons par
1

3

n

1;

= q11 ;
2
=

=

2 ; :::
2

= det

q11
det 4 q21
q31
2

i ; :::

q11
6 q21
det 6
4
qn1

q12
q22
q32

n

q11
q21

les détérminants suivants

q12
q22
3

(q12 = q21 );

q13
q23 5 (q12 = q21 ; q13 = q31 ; q23 = q32
q33
3
q1n
q2n 7
7 (qij = qji )
5
qnn

q12
q22
qn2

Ceci étant, on a le théorème suivant qui caractérise la dé…ni-positivité de Q
Théorème5 (Critère de Sylvestère)
Soit Q une matrice (n,n) symétrique. Q est dé…nie positive si et seulement si
les détérminants i sont strictement positifs i.e.
i

> 0; i = 1; 2:::; n

Remarque3
Si Q n’est pas symétrique, alors le critère de Sylvestere n’implique pas la dé…nie
positivité de Q: L’exercice suivant le prouve.
Exercice1
Considérons la matrice
Q=

1
4

0
1

a) Calculez 1 et 2
b) Montrez que Q n’est pas dé…nie positive.
c) Que peut on conclure?
iii

iv
1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F

Solution Exercice1
a) On a 1 = 1 > 0 et 2 = 1 > 0
b) Q n’est pas dé…nie positive, car si on prend xT = (1; 1);on a xT 6= (0; 0) et
xT Qx =

1

1
4

1

0
1

1
1

=

2<0

c) On ne peut pas appliquer le théorème précédent. Ce qui manquait dans cet
1 0
exemple est le fait que Q =
n’est pas symétrique.
4 1
Pour la semi dé…nie positivité, on a seulement la condition nécessaire comme
le montre le théorème suivant et l’exercice1
Théorème 6
Soit Q une matrice (n,n) symétrique. Si Q est sem-dé…nie positive alors les
détérminants i sont positifs i.e.
i

0; i = 1; 2:::; n

Remarque4
L’utilité du théorème précédent c’est pour démontrer que Q n’est pas semi
dé…nie positive. Il su¢ t de trouver i < 0:
Exercice2
Considérons la matrice Q suivante
2

2
Q=4 2
2

2
2
2

3
2
2 5
0

a) Calculez 1 ; 2 ; 3
b) Montrez que Q n’est pas semi-dé…nie positive.
c) Conclusion
Un autre critère nous permet en calculant les valeurs propres, de reconnaître si
une matrice Q est dé…nie positive. On a le théorème suivant:
Théorème 7
Soit Q une matrice symétrique d’ordre n. Alors Q est dé…nie positive (semidé…nie positive), si et seulement si toutes les valeurs propres de Q sont strictement
positives (positves).
Rappelons maintenant l’important théorème suivant appélé aussi inégalité de
Raileigh, qu’on utilisera par la suite
Théorème 8 (Inégalité de Raileigh)
Soit Q une matrice d’odre n, symétrique et dé…nie positive. Notons par min (Q) et
max (Q) la plus petite et la plus grande valeur propre de la matrice Q respectivement. Alors on a
2
min (Q) kxk

xT :Q:x

2
max (Q) kxk

2. OPTIM ISATION QUADRATIQUE SANS CONTRAINTES

v

2. Optimisation quadratique sans contraintes
2.1. De…nition et théorèmes fondamentaux. Dé…nition3
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn . On
appelle probleme de minimisation quadratique sans contraintes, le problème noté
(PQSC) suivant:
(PQSC)

minn

x2R

1 T
x Qx
2

bT x

Théorème 9 Le probleme (PQSC) a une solution unique
système linéaire Qx = b, c’est à dire que x
bveri…e

(1)

Preuve deThéorème 9
Considerons f (x) = 21 xT Qx
point x: On a

x
b=Q

1

x
b, solution du

b

bT x: notons H(x) la matrice Htssienne de f au

H(x) = Q; 8x 2 Rn
Rappelons le théorème de l’Analyse convexe. Soit f : S ! R; S Rn convexe.
Alors f est convexe sur S si et seulement si H(x) est semi dé…nie positive pour tout
x 2 S: De plus si f est quadratique de la forme f (x) = 21 xT Qx bT x: Alors f est
strictement convexe si et seulement si H(x) est de…nie positive pour tout x 2 Rn :
Pour f (x) = 12 xT Qx bT x; on a H(x) = Q; 8x 2 Rn : Par hypothèse Q est
dé…nie positive, donc f (x) = 21 xT Qx bT x est strictement convexe dans Rn :
Rappelons maintenant ce deuxième résultat de l’optimisation convexe. Soit
S Rn convexe et ouvert et f : S ! R; strictement convexe et (P C) le problème
d’optimisation convexe suivant
(PC)

minf (x)
x2S

Alors x
b 2 S est solution optimale de (P C) si et seulement si on a
(2)

rf (b
x) = 0

De plus si x
b existe, alors elle est unique.
Appliquons ce résultat à notre problème. f (x) = 21 xT Qx bT x est strictement
convexe. S = Rn est convexe et ouvert. x 2 Rn est solution optimale de (PQSC)
si et seulement si rf (x) = 0: Or rf (x) = Qx b: Donc
(3)

rf (x) = 0 () Qx

b = 0 () Qx = b

Donc x
b solution optimale de (PQSC) si et seulement x
b véri…e
(4)

Qb
x = b:

Q étant dé…nie positive, alors Q est inversible. Par conséquent x
b solution de (4)
est donnée par
(5)

x
b=Q

1

b:

1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F
vi

2.2. Calcul du pas obtenu par une recherche lineaire exacte. Soit Q
est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) = 12 xT Qx
bT x: Considérons le problème (PQSC)
1 T
x Qx
2

min f (x) = minn

x2Rn

x2R

bT x

(P QSC)

Les méthodes à directions de recherches linéaires générent des suites fxk gk=1;2;:::
de la manière suivante. On démarre par x1 2 Rn : A litération k si on a xk 2 Rn : Le
successeur xk+1 de xk est donné par la relation suivante
(6)

xk+1 = xk +

k dk

où dk 2 Rn est une direction de recherche et k 2 R+ est le pas de recherche obtenu
par une recherche linéaire exacte ou inexacte. Dans le cas d’une recherche linéaire
exacte k véri…e
(7)

f (xk +

k dk )

= minf (xk + dk )
>0

Notons
(8)

gk = rf (xk ) = Qxk

b

Théorème 10
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
1 T
bT x: Considérons le problème (PQSC)
2 x Qx
1 T
x Qx
2

minn f (x) = minn

x2R

x2R

bT x

(P QSC)

Supposons qu’à l’iteration k on a une direction dk de descente, c’est à dire que dk
véri…e
gkT dk = (Qxk

(9)
soit

k

b)T dk < 0

> 0 obtenu par une recherche lineaire exacte cad que
f (xk +

k dk )

k

veri…e

= minf (xk + dk )
>0

Alors
(10)

k

=

gkT dk
dTk Qdk

Preuve du théorème 10
Considérons
(11)
Donc
(12)

'( ) = f (xk + dk )
k

est la solution optimale du problème unidimensionnel suivant
'(

k)

= min'( )
>0

1 T
2 x Qx

Q de…nie positive. Alors f (x) =
bT x est strictement convexe sur
R : Par conséquent '( ) = f (xk + dk ) est strictement convexe sur ]0; +1[ qui est
n

3. ETUDE DE LA CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES FONCTIONS QUADRATIQUES STRICTEM E

un ouvert convexe. Donc
'0 ( k ) = 0: Or
'0 ( )

k

solution optimale de (12) si et seulement si

= rf (xk + dk )T dk = [Q(xk + dk )

=

k

veri…e

b]T dk

b + Qdk ]T dk = [gk + Qdk ]T dk

[Qxk

= gkT dk + dTk Qdk :
Donc
'0 ( ) = 0 () dTk Qdk =

gkT dk

ou encore

(13)

k

=

=

gkT dk
:
dTk Qdk

Remarque 5
Si Q n’est pas de…nie positive mais seulement semi dé…nie positive, alors f
n’est pas strictement convexe, et dTk Qdk peut être égale à zéro. Par conséquent k
ne sera plus de…nie par (10).
3. Etude de la convergence de la méthode du gradient pour les
fonctions quadratiques strictement convexes
Dans cette partie, on va étudier et analyser la convergence de la méthode du
gradient dans le cas particulier où la fonction objectif f est quadratique strictement
convexe. On analysera surtout le cas où le pas k est obtenu par une recherche
gkT :rf (xk )
et dans le cas où le pas k
linéaire exacte de la forme k =
rf (xk )T :Q:rf (xk )
est …xe pour tout k: Des théorèmes de caractérisation seront donnés. Avant celà,
donnons quelques notations.
Dé…nition4
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
1 T
bT x et x
b = Q 1 b; la solution optimale du problème (P QSC) suivant:
2 x Qx
1 T
T
min 2 x Qx b x : x 2 Rn : Notons par V (x) la fonction suivante
(14)

V (x) = f (x) +

1 T
1
x
b :Q:b
x = xT Qx
2
2

bT x +

1 T
x
b :Q:b
x
2

Proposition 1
a) Les fonctions V (x) et f (x) di¤èrent seulement par une constante.
b) On a
(15)

V (x) =

1
(x
2

x
b)T :Q:(x

x
b)

Preuve
a) En e¤et. On a
(16)

V (x)

f (x) =

1 T
x
b :Q:b
x = Cte
2

1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F
viii

b) On a
1
(x
2

1 T
1 T
1 T
1 T
x :Q:x + x
b :Q:b
x
b :Q:x
x :Q:b
x
x
2
2
2
2
1 T
1 T
x :Q:x + x
b :Q:b
x xT :Q:b
x
=
2
2
1 T
1 T
=
x :Q:x bT x + x
b :Q:b
x = V (x)
2
2
Ceci étant, on obtient le théorème suivant:
x
b)T :Q:(x

x
b)

=

Théorème 11
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
1 T
T
n
2 x Qx b x: Soit x0 2 R et fxk gk2N la suite générée par la méthode du gradient
à pas k quelconque, i.e.
xk+1 = xk
k gk
avec
(17)

gk = rf (xk ) = Q:xk

b:

Supposons que pour tout k, on a gk 6= 0: Alors on a
(18)


V (xk+1 ) = (1
k

k )V

(xk )

véri…e

(19)

k

=

gkT :Q:gk
k: T
gk :Q 1 :gk

2

gkT :gk
gkT :Q:gk

k

Preuve du théorème 11
(18) est équivalente à
(20)

V (xk ) V (xk+1 )
=
V (xk )

k

=

gkT :Q:gk
k: T
gk :Q 1 :gk

Montrons donc la relation (20). Evaluons
les calculs, notons:
(21)

(23)

V (xk ) =

gkT :gk
T
gk :Q:gk

V (xk ) V (xk+1 )
:
V (xk )

yk = (xk

On a d’après (15) et (21)

2

k

Avant celà et pour faciliter

x
b)

1 T
y :Q:yk
2 k

et
V (xk+1 )

=
=
=

1
(xk+1 x
b)T :Q:(xk+1 x
b)
2
1
T
(xk x
b
x
b
k gk ) :Q: (xk
k gk )
2
1 T
1 2 T
T
yk :Q:y
g :Q:gk
k gk :Q:yk +
2
2 k k

Donc
(25)

2
V (xk ) V (xk+1 )
=
V (xk )

T
2 T
k gk :Q:yk
k gk :Q:gk
:
T
yk :Q:yk

(24)

3. ETUDE DE LA CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES FONCTIONS QUADRATIQUES STRICTEM E

Remarquons que
(26)

gk = Q:xk

b = Q:xk

Q:b
x = Q(xk

Par conséquent
(27)

yk = Q

1

:gk

x
b) = Q:yk

(26) et (27) impliquent
ykT :Q:yk = gkT :Q

(28)

1

:gk

et
gkT :Q:yk = gkT :gk

(29)

On obtient donc d’après (25), (26), (27), (28) et (29)
V (xk ) V (xk+1 )
V (xk )

T
2 T
k gk :gk
k gk :Q:gk
T
1
gk :Q :gk
T
2 k gkT :gk gkT :Q:gk
2 gk :Q:gk
:
k
gkT :Q 1 :gk gkT :Q:gk
gkT :Q 1 :gk
T
T
g :gk
gk :Q:gk
2 Tk
= k:
k
k T
1
gk :Q :gk
gk :Q:gk

2

=
=
=

Théorème 12
Si gk = rf (xk ) = Q:xk

(30)

b = 0; alors

(31)

8i

et
(32)

8i

k : xi = x
b

k : V (xi ) = 0

La relation (18) peut se généraliser comme suit
(33)

8i

k : V (xi+1 ) = (1

i )V

(xi ) avec

i

=1

Preuve du théorème 12
Puisque f est strictement convexe dans Rn : Donc si gk = rf (xk ) = Q:xk
0; alors xk = x
b: D’autre part
xk+1 = xk

k gk

et ainsi de suite, on btient (31).
On a pour i k

= xk = x
b

1
(xi x
b)T :Q:(xi x
b) = 0
2
d’où (32). La relation (33) est une conséquence de (31) et (32).
V (xi ) =

Donnons d’autres détails sur les constantes k
Théorème 13
Considérons les constantes k véri…ant (18) et (19). Alors on a
(34)

8k :
Preuve du théorème 13

k

1

b=

1 . ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F
x

(18) implique
(35)

1

=

k

V (xk+1 )
=)
V (xk )

k

=1

V (xk+1 )
V (xk )

D’autre part, et puisque Q est dé…nie positive, donc si gk 6= 0; alors
1
(36)
V (xk ) = (xk x
b)T :Q:(xk x
b) > 0
2
Par conséquent et d’après (35) et (36), on a
(37)

k

Si gk = 0; alors

k

V (xk+1 )
<1
V (xk )

=1

= 1: Donc on a
8k :

1:

k

Nous arrivons maintenant au théorème suivant qui nous donne une caractérisation pour avoir la convergence de la suite fxk gk2N vers la solution optimale x
b: La
condition porte sur les k :
Théorème 14
Soit fxk gk2N la suite générée par la méthode du gradient, c’est à dire que
fxk gk2N est obtenue par x0 initial quelconque et

(38)

xk+1 = xk

k rf (xk )

= xk

k gk

= xk

k

(Q:xk

b)

k étant obtenue par une recherche linéaire exacte ou inexacte ou k =
pour tout k: Considérons k dé…ni par (18) et (19) et supposons que

(39)

est …xe

> 0 pour tout k:

k

Alors pour tout point initial x0 ; la suite fxk gk2N converge vers la solution
optimale x
b si et seulement si
1
X
(40)
k =1
k=0

Preuve du Théorème 14
D’après le théorème11, on a
V (xk )

= (1
= (1
= (1
=

kY1
i=0

(42)

(xk 1 ) = (1
k 1 )(1
k 2 )V (xk
k 1 )(1
k 2 )(1
k 3 )V (xk 3 )
0 )(1
1 )(1
2 ):::(1
k 1 )V (x0 )
!

(1

i)

2)

(41)

V (x0 )

Supposons que gk 6= 0 pour tout k (Sinon il existe k0 2 N tel que xk0 = x
b): Donc

Il est clair maintenant que
(43)
si et seulement si
(44)

k 1 )V

8k 2 N : 0 <

k

xk ! x
b
k!1

V (xk ) ! 0
k!1

<1

3. ETUDE DE LA CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES FONCTIONS QUADRATIQUES STRICTEM E

soit en tenant compte de (41), on obtient que (43) est équivalente à
!
1
Y
(45)
(1
=0
i)
i=0

Maintenant

kY1

ln

!

(1

i)

i=0

et par conséquent
kY1

lim

k!1

lim

k!1

(1

i=0

k
X1

ln (1

i=0

!

i)

!

i)

=

1
Y

=

k
X1

!

(1

i)

i=0

=

1 () lim

k!1

ou encore que

1
X

(46)

ln (1

!

ln (1

i)

i=0

i)

i=0

= 0 ()
k
X1

ln (1

!

i)

i=0

= +1

= +1

Pour …nir, il n’est pas di¢ cile de démontrer que
!
1
1
X
X
(47)
ln (1
= +1 ()
i)
i=0

i=0

Exercice
Démontrez l’équivalence (47), c’est à dire
!
1
X
ln (1
= +1 ()
i)
i=0

1
X
i=0

i

!

i

= +1:

!

= +1:

Avant de donner les deux principaux résultats de convergence de ce chapitre,
rappellons (voir théorème8), le résultat suivant dit " Lemme de Rayleight"
2
min (Q) kxk

(48)

2
max (Q) kxk

xT :Q:x

Nous avons aussi
(49)

min (Q

1

(49bis)

max (Q

1

1

)=

max (Q)

1

)=

min (Q)

ceci étant, nous avons
Théorème 15
Soit Q une matrice d’ordre n; symétrique et dé…nie positive. Alors on a pour
tout x 2 Rn
(50)

min (Q)
max (Q)

2

xT x
T
(x :Q:x) (xT :Q

Preuve du théorème 15

max (Q)
1 :x)

min (Q)

1.
xii ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F

D’après la relation (48), (49), (49bis) on a
min (Q) kxk

2

xT :Q

1

:x

max (Q

1

) kxk

2

ou encore
1

2

max (Q)

xT :Q

kxk

1

1
2
kxk
(Q)
min

:x

donc
1

min (Q)
2

(51)

max (Q)
2

(xT :Q 1 :x)

kxk

kxk

D’autre part, on a
1

(52)

1
xT :Q:x

2

max (Q) kxk

1
2

min (Q) kxk

(51) et (52) impliquent
2

kxk

2

min (Q)
2

kxk

2

1
2

max (Q) kxk

xT x
T
(x :Q:x) (xT :Q

1 :x)

max (Q)
2

kxk

1
2

min (Q) kxk

kxk

Ce qui donne …nalement
min (Q)
max (Q)

2

xT x
(xT :Q:x) (xT :Q

max (Q)
1 :x)

min (Q)

:

3.1. Convergence de la méthode du gradient pour les fonctions quadratiques strictement convexes à pas optimal. Le théorème suivant est le résultat
de convergence de la méthode du gradient pour les fonctions quadratiques strictement convexes à pas optimal.
Théorème 16 (convergence de la méthode du gradient pour les fonctions quadratiques strictement convexes à pas optimal)
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
1 T
x
Qx bT x: Soit x0 2 Rn quelconque et fxk gk2N la suite générée par la méthode
2
du gradient à pas k optimal, c’est à dire
(53)

xk+1 = xk

k gk

avec
(54)

gk = Q:xk

b

et
(55)

k

=

gkT gk
gkT Qgk

Alors
(56)

xk ! x
b
k!1

Preuve du théorème 16
Remarquons d’abord que s’il existe k0 2 N tel que gk0 = 0; alors xk0 = x
b:

2

2

3. ETUDE DE LA CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES FONCTIONS QUADRATIQUES STRICTEM E

Donc suppososons que pour tout k 2 N; gk 6= 0: Substituons la valeur de
dé…nie par (55) dans l’expression (19) de k : On obtient
k

gkT :Q:gk
gkT :gk
2
k: T
k
gk :Q 1 :gk
gkT :Q:gk
g T :gk
gkT gk gkT :Q:gk
2 Tk
T
T
1
gk Qgk gk :Q :gk
gk :Q:gk

=
=

gkT gk
gkT Qgk
2

gkT gk
T
1 :g
k : gk :Q

gkT gk
gkT gk
= T
T
1
gk :Q :gk gkT Qgk
gk :Q

=

k

1 :g
k

>0

Donc
(57)

k

>0

Considérons maintenant la relation (50) (dans laquelle on prend x = gk ); on obtient
(58)

min (Q)
max (Q)

2

gkT gk
gkT :Q 1 :gk : gkT :Q

max (Q)
1 :g
k

min (Q)

ou encore
max (Q)

min (Q)

(59)

k

max (Q)

min (Q)

(59) implique que
(60)

min (Q)
k

max (Q)

> 0 (car Q est dé…nie positive)

(60) implique que
1
X

k=0

k

= 1:

Finalement et d’après le théorème 14, on a
xk ! x
b:
k!1

3.2. Convergence de la méthode du gradient pour les fonctions quadratiques strictement convexes à pas …xe. Dans cette partie, on va établir un
résultat de convergence de la méthode du gradient pour les fonctions quadratiques
strictement convexes à pas …xe. La suite fxk gk2N générée par la méthode du gradient à pas k = …xe est de la forme suivante:
(61)

xk+1 = xk

gk

avec
(62)

gk = Q:xk

b

Puisque est …xe pour tout k; le calcul devient plus simple dans ce cas. On
n’a pas besoin dans cette méthode d’e¤ectuer à chaque itération
une recherche linéaire. Cependant, la méthode du gradient ne converge pas
pour tout > 0: Des conditions seront exigées sur pour avoir la convergence.
C’est ce que nous verrons dans ce théorème.
Théorème 17 (convergence de la méthode du gradient pour les fonctions quadratiques strictement convexes à pas …xe)

1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F
xiv

Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
bT x: Soit x0 2 Rn quelconque et fxk gk2N la suite générée par la méthode
du gradient à pas k = …xe pour tout k, c’est à dire
1 T
2 x Qx

(63)

xk+1 = xk

gk

avec
(64)

gk = Q:xk

b

Alors
xk ! x
b

(65)

k!1

si et seulement si on a
(66)

0<

2

<

max (Q)

Preuve du théorème 17
Montrons que
(67)

0<

2

<

xk ! x
b

=)

max (Q)

k!1

En e¤et. Considérons l’inégalité de Rayleight ( Théorème 8 en posant x = gk )
(68)

min (Q) kgk k

et

gkT :Q

(69)

1

:gk

Dans ce cas l’expression de

k

2
max (Q) kgk k

gkT :Q:gk

max (Q

= :

k

2

1

2

) kgk k =

1
2
kgk k
min (Q)

est
gkT :Q:gk
gkT :Q 1 :gk

2

gkT :gk
gkT :Q:gk

(68) et (69) impliquent
(70)

k

2

2
min (Q) kgk k : min (Q)
2
kgk k

kgk k

2

2
max (Q) kgk k

(70) donne
(71)

k

(

2

2
min (Q))

max (Q)

Rappelons la condition (66) du théorème
(72)

0<

<

2
max (Q)

=)

2
max (Q)

et par conséquent
(73)

k

> 0 pour tout k

La relation (71) implique que
1
X

k=0

k

= 1:

Finalement et d’après le théorème 14, on a
xk ! x
b:
k!1

>0

!

4. ETUDE DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES FONCTIONS QUADRATIQUES

La réciproque de ce théorème est laissée à titre d’exercice.
Exercice
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
1 T
bT x: Soit x0 2 Rn quelconque et fxk gk2N la suite générée par la méthode
2 x Qx
du gradient à pas k = …xe pour tout k, c’est à dire
xk+1 = xk

gk

avec
gk = Q:xk b
Notons par x
b la solution minimale globale du problème (P QSC) suivant
(PQSC)

min

1 T
x Qx
2

bT x : x 2 R n

Montrez l’implication suivante:
xk ! x
b =)

(74)

k!1

0<

2

<

max (Q)

4. Etude de la vitesse de convergence de la méthode du gradient pour
les fonctions quadratiques strictement convexes
On considère dans cette partie la méthode du gradient à pas optimal. Etudions
la vitesse de convergence de la suite fxk gk2N vers la solution optimale globale
optimale x
b: Le théorème suivant résume ce résultat
Théorème 18
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
1 T
T
n
2 x Qx b x: Soit x0 2 R et fxk gk2N la suite générée par la méthode du gradient
à pas optimal k i.e.
xk+1 = xk
k gk
avec
gk = rf (xk ) = Q:xk b:
et
gkT :gk
(75)
k = T
gk :Q:gk
Supposons que pour tout k, on a gk 6= 0: Alors on a
(76)

V (xk+1 )

1

min (Q)

max (Q)

V (xk )

Preuve du Théorème18
On a établi dans le théorème16 (formule (60), et la relation (30) que
(77)

V (xk ) V (xk+1 )
=
V (xk )

min (Q)
k

max (Q)

>0

(77) implique
V (xk )

V (xk+1 )

min (Q)
max (Q)

V (xk )

ou encore
V (xk+1 )

V (xk )

min (Q)
max (Q)

1

xvi
1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F

ou en…n
V (xk+1 )

min (Q)

V (xk ) 1

max (Q)

:

Analyse de la relation (76)
Posons
(78)

r=

max (Q)
min (Q)

= kQk Q

1

(76) donne
(79)

V (xk+1 )

(1

1
)V (xk )
r

Proposition
Sous les conditions du théorème 18, on a
1
<1
(80)
0 1
r
Preuve
Elle est évident en remarquant que Q est dé…nie positive et par conséquent on
a
min (Q)
0 < min (Q)
1
max (Q) =) 0 <
max (Q)
Donc
1
0 <
1
r
1
1
1
< 0 =) 0 1
< 1:
r
r
Conclusion
La suite fV (xk g tend vers 0: Puisque V (xk+1 ) est égale à moins (1 1r )V (xk ); donc,
plus 1 1r est proche de 0; plus la vitesse de convergence est meilleure. Ceci est
réalisable si 1r est proche de 1 ou encore que max (Q) est assez proche de min (Q).
Au contraire si max (Q) est trés grande relativement à min (Q); la vitesse de convergence devient trés lente. A la limite si max (Q) = min (Q); la convergence se
fait en une itération. Les lignes de niveau sont dans ce cas des cercles.
5. PROBLEME ET TP
PROBLEME ET TP
Considérons la fonction f dé…nie par
f : Rn ! R
n

f (x1 ; x2 ; :::; xn ) =
et (PSC) le problème
(PSC)

min

(

n

1X 2
ix
2 i=1 i

!

1X 2
ix
2 i=1 i

!

xn

xn : x 2 Rn

)

Première Partie: Problème. Faire tous les calculs pour n=2

5. PROBLEM E ET TP

xvii

a) Ecrire f sous la forme
1 T
x Qx bT x : x 2 Rn
2
avec Q matrice symétrique dé…nie positive d’ordre n:
b) Montrez que f est strictement convexe sur Rn :
c) Montrez que le problème (PSC) admet une solution minimale globale unique
d) On applique la méthode du gradient à pas optimal au problème (PSC).
Calculez le pas optimal k et xk+1 en fonction de xk
Deuxième Partie: Problème. Faire tous les calculs pour n 2 N quelconque
Troisiéme Partie: TP: n 2 N quelconque
e) Ecrire un programme en Matlab qui calcule le minimum global de la fonction
f avec les données suivantes:
n = nombre de variables
" = 10 6 = critère d’arrêt. L’Algorithme s’arrête à l’itération k quand
krf (xk )k < " = 10

6

La suite fxk gk2N est calculée en partant du point initial x0 = (1; 1; ::::; 1) 2
Rn et
xk+1 = xk

k gk

avec
gk = rf (xk ) = Q:xk

et

k

=

ou

gkT :gk
T
gk :Q:gk
k

=

b:

(pas optimal)

(pas f ixe)

Que peut on conclure?
SOLUTION
Première Partie: Problème n=2
Pour n = 2; la fonction quadratique QF1 est dé…nie par
f : R2 ! R
f (x; y) =

1 2
x + 2y 2
2

y

avec le point de démarrage
(x0 ; y0 ) = (1; 1)
Ecrivons (f (x; y) sous la forme matricielle suivante
1
f (x; y) = (x; y):Q:(x; y)T bT (x; y)T
2
On obtient
1 0
Q=
0 2

xviii
1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F

et
bT = (b1 ; b2 ) = (0; 1)
Calcul du Gradient: rf (x; y)

rf (x; y) = Q:(x; y)

ou en remplaçant

(b1 ; b2 )

rf (x; y)T = (x; 2y

1)
2

Calcul de la norme du Gradient: krf (x; y)k
On a
2
krf (x; y)k = x2 + (2y 1)2 = x2 + 4y 2
et
rf (x; y)T :Q:rf (x; y)
1 0
x 2y 1
=
0 2
2

= x + (2y
2

= x + 8y
Calcul de

1) (4y

2

4y + 1

x
2y

1

2)

8y + 2

k
2

krf (x1 ; y)k
rf (x1 ; y)T :Q:rf (x1 ; y)
x2 + 4y 2 4y + 1
x2 + 8y 2 8y + 2

=

k

=

Calcul de (u; v); successeur de (x; y)
On a
(u; v)

=

(x; y)

=

(x; y)

k rf (x; y)
2
2

x + 4y
x2 + 8y 2
2

y

2

+4y
x xx2 +8y
2

x

=

(2y
2

1)

4y+1
8y+2
x2 +4y 2 4y+1
x2 +8y 2 8y+2

4xy 4xy+x
x2 +8y 2 8y+2
2
x y+x2 +4y 2 4y+1
x2 +8y 2 8y+2

=

Donc
u
v

=

4y + 1
8y + 2

!

4xy 2 4xy+x
x2 +8y 2 8y+2
x2 y+x2 +4y 2 4y+1
x2 +8y 2 8y+2

(x; 2y
!

!

et
u

=

v

=

4xy 2 4xy + x
x2 + 8y 2 8y + 2
x2 y + x2 + 4y 2 4y + 1
x2 + 8y 2 8y + 2

Deuxième Partie: Problème. n 2 N quelconque

1)

5. PROBLEM E ET TP

xix

La fonction quadratique QF1 est dé…nie par
f : Rn ! R
n

f (x1 ; x2 ; :::; xn )

1X 2
ix
2 i=1 i

=

!

xn

1 2
x + 2x22 :::: + ix2i + :::: + nx2n
2 1

=

xn

avec le point de démarrage
x0 = (x01 ; x02 ; :::; x0n ) = (1; 1; :::; 1)
Ecrivons (f (x1 ; x2 ; :::; xn ) sous la forme matricielle suivante
f (x1 ; x2 ; :::; xn ) =
On obtient

1
(x1 ; x2 ; :::; xn ):Q:(x1 ; x2 ; :::; xn )T
2

0

1
B 0
B
B
B
B 0
Q=B
B 0
B
B
B
@ 0
0

et

0
2

0
0

0
0
i
0

0
0
0

bT (x1 ; x2 ; :::; xn )T

0
0
0
i+1

0

0

0
0

0

n

1
0

1
0
0 C
C
C
C
0 C
C
0 C
C
C
C
0 A
n

bT = (b1 ; :::; bn ) = (0; 0; ::::; 0; 1)
Calcul du Gradient: rf (x1 ; x2 ; :::; xn )
rf (x1 ; x2 ; :::; xn ) = Q:(x1 ; x2 ; :::; xn )

(b1 ; b2 ; :::; bn )

ou en remplaçant
rf (x1 ; x2 ; :::; xn )T
= (x1 ; 2x2 ; 3x3 ; :::; ixi ; :::; (n

1)xn

1 ; nxn

1)

Calcul de la norme du Gradient: krf (x1 ; x2 ; :::; xn )k
On a

2

2

krf (x1 ; x2 ; :::; xn )k

= x21 + 22 x22 + 32 x23 + ::: + i2 x2i + ::: + (n

1)2 x2n

1

+ (nxn

et
=

rf (x1 ; x2 ; :::; xn )T :Q:rf (x1 ; x2 ; :::; xn )
(x1 ; 22 x2 ; 32 x3 ; :::; i2 xi ; :::; (n
(x1 ; 2x2 ; 3x3 ; :::; ixi ; :::; (n

=

x21

+

+(n

23 x22 + 33 x23 + ::: + i3 x2i
1)3 x2n 1 + n2 xn n

1)2 xn

1)xn

1; n

1 ; nxn

+ :::
(nxn

2

1)

xn

n)
T

1)

1)2

xx
1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F

Calcul de

k
2

k

=
=

krf ((xk1 ; xk2 ; :::; xkn )k
rf (xk1 ; xk2 ; :::; xkn )T :Q:rf ((xk1 ; xk2 ; :::; xkn )
x21 + 22 x22 + 32 x23 + ::: + i2 x2i + ::: + (n 1)2 x2n 1 + (nxn 1)2
x21 + 23 x22 + 33 x23 + ::: + i3 x2i + ::: + (n 1)3 x2n 1 + (n2 xn n) (nxn

1)

Calcul de (xk+1;1 ; xk+1;2 ; :::; xk+1;n )
On a
(xk+1;1 ; xk+1;2 ; :::; xk+1;n ) = (xk1 ; xk2 ; :::; xkn )

k rf (xk1 ; xk2 ; :::; xkn )

Troisiéme Partie: TP:
Dans le programme Matlab qui suit, on a pris n = 1000: L’utilisateur pourra
changer n
Le critère d’arrêt est " = stop = 10 6
P rogramme de calcul de la solution optimale en M atlab; n 2 N quelconque; pas optimal
n=1000;
stop = 10^-6;
Q=zeros(n) ;
b=zeros(n,1) ;
X=ones(1,n);
gradient=ones(1,n);
k=0;
‡ag=true;
b(n)=1
for l=1:1:n
Q(l,l)=l;
end
time=cputime ;
while ‡ag
k=k+1
y=0.5*X*Q*X’-b’*X’
gradient=Q*X’-b ;
normGradient=gradient’*gradient
alpha=normGradient/(gradient’*Q*gradient) ;
X=X-alpha*gradient’;
if stop>normGradient
‡ag=false;
end
end
time = cputime - time

5. PROBLEM E ET TP

xxi

RESULTATS NUMERIQUES
Tableau1:Méthode du gradient avec pas optimal,
n=2,10,100,200,400,600,1000,
n = nbre var
2
10
100
200
400
600
1000
2000

k = nbre iter
8
38
362
722
1440
2158
3592
7180

krf (xk )k
4:18 10 7
8:27 10 7
9:85 10 7
9:74 10 7
9:85 10 7
9:87 10 7
9:97 10 7
9:97 10 7

temps sec
0:062
0:031
0:202
0:812
4:77
4
22:82
4
183:31
4
2472
Programme de calcul de la solution optimale en Matlab, n 2 N

quelconque, pas …xe

n=1000;
alpha=0.001 ;
stop = 10^-4;
Q=zeros(n) ;
b=zeros(n,1) ;
X=ones(1,n);
gradient=ones(1,n);
k=0;
‡ag=true;
b(n)=1
for l=1:1:n
Q(l,l)=l;
end
time=cputime ;
while ‡ag
k=k+1
y=0.5*X*Q*X’-b’*X’
gradient=Q*X’-b ;
normGradient=gradient’*gradient
X=X-alpha*gradient’;
if stop>normGradient
‡ag=false;
end
end
time = cputime - time

f (xk )
0:25
0:05
0:005
0:0025
0:0012
8:3 10
4:99 10
2:49 10

1. ETUDE DE LA CONVERGENCE ET DE LA VITESSE DE CONVERGENCE DE LA M ÉTHODE DU GRADIENT POUR LES F
xxii

RESULTATS NUMERIQUES
Tableau2: Méthode du gradient avec pas …xe
= 0:001; n = 2; 10; 100; :::; 1000
n = nbre var k = nbre iter krf (xk )k
f (xk )
temps sec
2
6906
9:86 10 7
0:25
2:73
10
6906
9:86 10 7
0:05
2:23
100
6906
9:86 10 7
0:005
2:49
200
6906
9:86 10 7
0:0025
17:34
400
6906
9:86 10 7
:0012
110:49
600
6906
9:87 10 7
8 10 4
251:24
7
1000
6906
9:98 10
4:9 10 4
482:23
CONCLUSIONS ET COMMENTAIRES SUR LES RESULTATS NUMERIQUES
1) Dans cet exemple on
0
1
B 0
B
B
B
B 0
Q=B
B 0
B
B
B
@ 0
0

a
0
2

0
0

i
0

0
0
0

0
0

0
0
0
i+1

0

0

0
0

0

n

1
0

Donc

min (Q)

Donc
r=
et

= 1;

max (Q)

max (Q)
min (Q)

1
0
0 C
C
C
C
0 C
C
0 C
C
C
C
0 A
n

=n

=n

1
1
=
r
n

et

1
1
=1
r
n
On remarque que la plus grande valeur de 1 1r est atteinte lorsque n ! 1 et la
plus petite valeur est attinte lorsque n = 1: Ceci est très clair dans les résultats
numériques (voir les temps de calculs qui croissent lorsque n croit).
Par exemple n = 2 ! temps de calcul: 0.062secondes
n = 2000 !temps de calcul: 2472 secondes
Les résultats numériques confortent bien les résultats théoriques (voir Théorème
18) et commentaires.
1

2) Dans le Tableau2: Méthode du gradient avec pas …xe
On a pris
= 0:001: On a aussi respecté la théorie (Théorème17). POur qu’il
y’ait convergence, il faut que véri…e
0<

<

2
max (Q)

5. PROBLEM E ET TP

c’est à dire
0<
Dans tous les cas, il faut que

<

xxiii

2
n

véri…e:
(0 <

< 1)

et si on choisit
1
la suite fxk gk2N ne converge pas vers la solution minimale globale.
Les tests numériques donnent pour n = 2 et
et

=1

krf (xk )k = 1 : k = 2; 3; :::
f (xk ) = 0 : k = 2; 3; :::

alors que
f (b
x) =

0:25

et
krf (b
x)k = 0:


Documents similaires


convergence et vitesse convergence methode du gradient
convergence et vitesse de convergence de la methode du gradient professeur benzine rachid
micro master optimisation s1 2015 2016
gradient conjugue cas quadratique et non quadratique
14 problemes ouverts sur le gradient conjugue sujets de theses de doctorat
examen s1 optimisation 2015 2016


Sur le même sujet..