Fichier PDF

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

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



GRADIENT CONJUGUE. CAS QUADRATIQUE ET NON QUADRATIQUE .pdf



Nom original: GRADIENT CONJUGUE. CAS QUADRATIQUE ET NON QUADRATIQUE.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 16/04/2016 à 06:38, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 2033 fois.
Taille du document: 2.1 Mo (62 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


OPTIMISATION SANS CONTRAINTES
TOME2 : METHODES DU GRADIENT
CONJUGUE.

*********************
PROFESSEUR BENZINE RACHID
16 avril 2016

Table des matières
1 GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES STRICTEMENT CONVEXES
4
1.1 Optimisation quadratique sans contraintes . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 De…nition et théorèmes fondamentaux . . . . . . . . . . . . . . . . . . . 4
1.1.2 Calcul du pas obtenu par une recherche lineaire exacte . . . . . . . . . . 5
1.2 Méthode des directions conjugueés . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Dé…nitions et propriétés générales . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 L’Algorithme des directions conjuguées . . . . . . . . . . . . . . . . . . . 8
1.3 Méthode du gratient conjugué. Cas quadratique . . . . . . . . . . . . . . . . . . 14
1.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.2 Algorithme du gradient conjugué. Cas quadratique . . . . . . . . . . . . 15
1.3.3 Propriétés du gradient conjugué quadratique . . . . . . . . . . . . . . . . 15
1.3.4 Convergence de l’Algorithme du gradient conjugué quadratique . . . . . 18
2 GRADIENT CONJUGUE. CAS DES FONCTIONS NON QUADRATIQUES 24
2.1 Introduction et di¤érentes formes du gradient conjugué . . . . . . . . . . . . . . 24
2.1.1 Algorithme du gradient conjugué non quadratique . . . . . . . . . . . . . 27
2.1.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.3 Algorithme du Gradient conjugué non quadratique . . . . . . . . . . . . 29
3 SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE
3.1 Hypothèses C1 et C2 et théorème de Zoutendijk . . . . . . . . . . . . . . . . . .
3.1.1 Hypothèses C1 et C2 (de Lipschitz et de bornetude) . . . . . . . . . . . .
3.1.2 Théorème de Zoutendijk . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Utilisation du théorème de Zoutendijk pour démontrer la convergence
globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Role joué par la direction de recherche initiale . . . . . . . . . . . . . . . . . . .
3.3 Les méthodes dans lesquelles le terme kgk+1 k2 …gure dans le numérateur de k .
3.3.1 Méthode de Fletcher-Reeves . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Méthode de descente conjuguée . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Méthode de Dai-Yuan . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2

35
36
36
36
36
38
38
39
44
46

TABLE DES MATIÈRES
3.3.4 Méthode de Dai-Yuan généralisée . . . . . . . . . . . . . .
T
yk …gure dans le numérateur de k . . . . .
3.4 Les méthodes où gk+1
3.4.1 Méthode de Polak-Ribière-Polyak . . . . . . . . . . . . . .
3.4.2 Méthode de Hestenes et Stiefel HS . . . . . . . . . . . . .
3.4.3 Méthode de Liu et Storey LS . . . . . . . . . . . . . . . .
3.5 Méthodes hybrides et familles paramétriques du gradient conjugué
3.5.1 Les méthodes hybrides . . . . . . . . . . . . . . . . . . . .
3.5.2 Les méthodes uni…ées . . . . . . . . . . . . . . . . . . . . .

3

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

49
50
50
53
53
54
54
55

Chapitre 1
GRADIENT CONJUGUE. CAS DES
FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
1.1
1.1.1

Optimisation quadratique sans contraintes
De…nition et théorèmes fondamentaux

Dé…nition1
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 :
minn

x2R

1 T
x Qx
2

bT x

(PQSC)

Théorème1 Le probleme (PQSC) a une solution unique x
b, solution du système linéaire

Qx = b, c’est à dire que x
bveri…e
Preuve deThéorème1
Considerons f (x) = 12 xT Qx

x
b = Q 1b

(1)

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

a
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 :
4

1.1. OPTIMISATION QUADRATIQUE SANS CONTRAINTES
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
rf (b
x) = 0

(2)

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
rf (x) = 0 () Qx

b = 0 () Qx = b

(3)

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

1.1.2

x
b = Q 1 b:

(5)

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) =
b x: Considérons le problème (PQSC)
T

minn f (x) = min
n

x2R

x2R

1 T
x Qx
2

bT x

1 T
x Qx
2

(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
xk+1 = xk +

(6)

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
f (xk +

k dk )

= minf (xk + dk )
>0

(7)

Notons
gk = rf (xk ) = Qxk

5

b

(8)

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
Théorème2
Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) =
bT x: Considérons le problème (PQSC)
1 T
x Qx
2

minn f (x) = min
n

x2R

x2R

bT x

1 T
x Qx
2

(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
soit

k

b)T dk < 0

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

k dk )

k

veri…e

= minf (xk + dk )
>0

Alors
k

(9)

=

gkT dk
dTk Qdk

(10)

Preuve du théorème2
Considérons
(11)

'( ) = f (xk + dk )
Donc

k

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

k)

(12)

= min'( )
>0

Q de…nie positive. Alors f (x) = 21 xT Qx bT x est strictement convexe sur Rn : Par conséquent
'( ) = f (xk + dk ) est strictement convexe sur ]0; +1[ qui est un ouvert convexe. Donc k
solution optimale de (12) si et seulement si k veri…e '0 ( k ) = 0: Or
'0 ( ) = rf (xk + dk )T dk = [Q(xk + dk ) b]T dk
= [Qxk b + Qdk ]T dk = [gk + Qdk ]T dk
= gkT dk + dTk Qdk :
Donc
'0 ( ) = 0 () dTk Qdk =

gkT dk

ou encore
=

gkT dk
:
dTk Qdk

Remarque 1
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).
6

1.2. MÉTHODE DES DIRECTIONS CONJUGUEÉS

1.2
1.2.1

Méthode des directions conjugueés
Dé…nitions et propriétés générales

Dé…nition2
Soit Q une matrice (n; n) symétrique. Les directions d0 ; d1; :::::dk sont dites Q conjuguées
si on a
dTi Qdj = 0; 0 i; j k
(13)
Théorème3
Soit Q une matrice (n; n) symétrique et dé…nie positive. Si les directions d0 ; d1; :::::dk ; avec
k n 1; sont non nuls et Q conjuguées, alors ils sont linéairement indépendants.
Preuve du théorème3
Supposons que
(14)
0 d0 + 1 d1 + ::: + k dk = 0
Multiplions l’égalité (14) par dTj Q; 0
0=

k
X

k , on obtient

j

T
i dj Qdi

=

T
j dj Qdj

(15)

i=1

Or
T
j dj Qdj

= 0 =)

j

=0

car Q est dé…nie positive et par conséquent dTj Qdj > 0: Donc le système fd0 ; d1; :::::dk g est libre.
Exercice1
Considerons
la3 matrice Q (3,3) suivante
2
3 0 1
Q = 40 4 25
1 2 3
a) Montez queQ est de…nie positive
b) Construire d0 ; d1 ; d2 Q Conjugués.
Corrigé Exercice1
a) Calcullons les détérminants des mineurs principaux de Q .
3
0
= 12 > 0;
1 = 3 > 0;
2 = det
0
4
2
3
3 0 1
43 = det Q = det 40 4 25 = 20 > 0
1 2 3
Donc Q est de…nie positive .
b) Commençons par dT0 = (1; 0; 0) et constriusons dT1 = (d1:1; d1:2; d1:3 ) et dT2 = (d2:1 ; d2:2 ; d2:3 )
tels que
dT0 Qd1 = 0; dT0 Qd2 = 0; dT1 Qd2 = 0:
Calcul de d1
7

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
d1 doit véri…er dT0 Q d1 = 02
32
3
3 0 1
d11
dT0 Q d1 = 0 () (1; 0; 0) 40 4 25 4 d12 5 = 3d1:1 + d1:3 = 0
1 2 3
d13
Prenons d1:1 = 1 et d1:2 = 0: L’équation précédente implique que d13 =
dT1 = (1; 0; 3): On peut véri…er facilement que
2
32
3
3 0 1
1
dT0 Qd1 = (1; 0; 0) 40 4 25 4 0 5 = 0
1 2 3
3

3d1:1 =

3: Donc

Calcul de d2
d2 doit véri…er dT0 Q d2 = 0 et dT1 Q d2 = 0
dT0 Q d2 = 0 () 3d21 + d23 = 0
dT1 Q d2 = 0 () 6d22 8d23 = 0
Autrement dit dT2 = (d2:1 ; d2:2 ; d2:3 ) doit véri…er le système d’inconnues d2:1 ; d2:2 ; d2:3 suivant
3d21 + d23 = 0
6d22 8d23 = 0

Il s’agit d’un système de deux équations à trois inconnues. Il faut donner à une variable une
valeur particulière à 2 et en déduire les deux autres. Prenons par exemple d21 = 1: Le système
précédent devient
3 + d23 = 0
()
6d22 8d23 = 0

d23 = 3
()
6d22 = 24

d23 = 3
d22 = 4

Par conséquent dT2 = (1; 4; 3):
Remarque2
On n’a pas unicité des vecteurs d0 ; d1 ; d2 Q Conjugués.

1.2.2

L’Algorithme des directions conjuguées

Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn . Considérons le
problème de minimisation quadratique sans contraintes, (PQSC), suivant :
min

x2Rn

1 T
x Qx
2

bT x

Algorithme des directions conjuguées
a) Initialisation
On se donne x0 2 RN quelconque et d0 ; d1; :::::dn
Etape principale
8

(P QSC)

1

Q conjugueés. Poser k = 0 et allez à b)

1.2. MÉTHODE DES DIRECTIONS CONJUGUEÉS
b) Etape principale
Pour k 0
Calculez
gk = rf (xk ) = Qxk
Si gk = 0: Stop.
Sinon calculez
k

b

gkT dk
dTk Qdk

=

et
xk+1 = xk +

k dk

Poser k = k + 1 et allez à b) Etape principale.
Théorème3
Partant d’un point initial x0 2 Rn quelconque, l’algorithme des directions conjuguées précédent converge vers la solution optimale unique x
b du probleme (PQSC) dans n iterations, c’est
à dire qu’on a
xn = x
b et Qxn = Qb
x=b
(16)

Preuve du théorème3
Considérons le vecteur x
b x0 2 Rn : D’autre part fd0 ; :::::dn 1 g est un système libre et
contient n vecteurs. Donc fd0 ; :::::dn 1 g est une base de Rn : Par conséquent il existe 0;:::; n 1
scalaires réels tels que
x
b x0 = 0 d0 + ::::::: + n 1 dn 1
(17)
Multiplions les 2 membres de (17) par dTk Q; 0
dTk Q(b
x

Donc
k

x0 ) =

k

n

1; on obtient

T
k dk Qdk

dTk Q(b
x x0 )
=
T
dk Qdk

(19)

Montrons maintenant que le numérateur de (19) est égal à
rithme des directions conjuguées
xk =
=
=
=

(18)

xk 1 + k 1 dk 1
xk 2 + k 2 dk 2 + k 1 dk
::::::::
x0 + 0 d0 + ::: + k 1 dk 1

dTk gk : En e¤et, d’après l’algo-

1

Par conséquent
xk

x0 =

Ecrivons maintenant : x
b

0 d0

+ ::: +

k 1 dk 1 ;

k = 1; 2; :::::n

1

(20)

x0 sous la forme
x
b

x0 = (b
x

xk ) + (xk
9

x0 )

(21)

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
Multiplions (21) par dTk Q; on obtient
x
x0 ) = dTk Q(b

x
dTk Q(b

(22)

xk )

car
dTk Q(xk
x
Calculons maintenant dTk Q(b

T
k 1 dk Qdk 1

=0

xk ): On a

x
xk ) = dTk [Qb

x
dTk Q(b

T
0 dk Qd0+::::::+

x0 ) =

Qxk ] = dTk [b

Qxk ] =

dTk (Qxk

b) =

dTk gk

(23)

(23) et (19) impliquent donc
=

dTk gk
=
dk Qdk

x0 =

0 d0

+ ::::::::::::: +

n 1 dn 1

x0 =

0 d0

+ ::::::::::::: +

n 1 dn 1 :

k

(24)

k

En conclusion on a
x
b

et

xn
Or

k

=

k

k = 0; ::::::::n

1:

Donc
x
b

Ce qui implique

x0 = xn

x0 :

x
b = xn

Remarque3
Si on démarre du point x1 , alors la solution optimale est atteinte au point xn+1 ; c’est à dire
qu’on aura
x
b = xn+1
Exercice2
Trouvez la solution optimale de la fonction
1
f (x) = xT
2

4
2

2
2

x

1
; x 2 R2 : xT = (x1 ; x2 )
1

xT

en utilisant la méthode des directions conjuguée avec xT0 = (0; 0) et dT0 = (1; 0); dT1 = (
Solution de l’Exercice2
a) Remarquon d’abort que Q =
4
2

4
2

2
2

est dé…nie postive car

2
= 4 > 0:
2
10

1

= 4 > 0 et

3 3
; ):
8 4

2

=

1.2. MÉTHODE DES DIRECTIONS CONJUGUEÉS
b) d0 et d1 sont Q conjugués. En e¤et,
dt0 Qd1 = (1; 0)

4
2

3
8
3
4

2
2

3
8
3
4

= (4; 2)

12 6
+ =0
8
4

=

c)Puisque n = 2 et le point initial est x0 ; alors la solution optimale x sera donc x2 .
Calcul de x1
x1 = x0 +

0 d0 ;

0

Donc
0

dT0 g0
; g0 = Qx0
dT0 Qd0

=

(1; 0) 11
4 2 1
(1; 0)
2 2 0

=

0
0

1 1
4 0

=

b=

1
4

=

Donc
x1 =

b=

1
4

0

Calcul de x2
x2 = x1 +
g1 = Qx1

1

=

1 d1 ;

1 d1

Conclusion la solution optimale x
b est

1
4

4 2
2 2

b=

1
1

0

3
8
1
4

=

+2

0

x
b = x2 =

0

=

3
2

3
8
3
4

=2

3
8
3
4

4 2
2 2

3
4

b

3
8
3
4

3
2

0

g1T d1
=
dT1 Qd1

x2 = x1 +

dT1 g1
; g1 = Qx1
dT1 Qd1

=

1

1

=

3
2

1
3
2

Remarque4
g2 = Q x2

b=

4
2

2
2

et x2 est solution du système linéaire
Qx = b
11

1
3
2

1
1

=

0
0

1
1

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
car
Q x2

b=

0
0

=) Q x2 = b

Théorème4
Soit Q une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) = 12 xT Qx bT x:
Considérons la suite fxk gk=1;2;::: de la manière suivante. On démarre par x1 2 Rn : A litération
k, Le successeur xk+1 de xk est donné par la relation suivante
xk+1 = xk +
où dk 2 Rn est une direction de recherche et
recherche linéaire exacte, k véri…e
f (xk +

k dk )

k dk

2 R+ est le pas de recherche obtenu par une

k

(25)

= minf (xk + dk )
>0

Notons
gk+1 = rf (xk+1 ) = Qxk+1

(26)

b

Alors
gk+1 = gk +

(26bis)

k Qdk

et
gk+1 dk = 0; k = 0; 1; :::; n

(27)

1

Preuve du Théorème4
En e¤et. On a
Q(xk+1

xk ) = (Qxk+1

b)

(Qxk

b) = gk+1

gk

(27bis)

D’un autre côté, on a
xk+1 = xk +

k dk :

Donc
(xk+1

xk ) =

k dk

(27tris)

(27bis) et (27tris) impliquent
gk+1

gk =

k Qdk :

D’autre part et comme on l’a vu dans la preuve du théorème2, considérons la fonction
suivante
' : ]0; +1[ ! R :
! '( ) = f (xk + dk )
(28)
et le problème d’optimisation unidimensionnel suivant
'(

k)

= min f'( ) :
12

2 ]0; +1[g :

(29)

1.2. MÉTHODE DES DIRECTIONS CONJUGUEÉS
Q est de…nie positive. Alors f (x) = 21 xT Qx bT x est strictement convexe sur Rn : Par
conséquent '( ) = f (xk + dk ) est strictement convexe sur ]0; +1[ qui est un ouvert convexe.
Donc k solution optimale de (29) si et seulement si k veri…e '0 ( k ) = 0: Or
'0 ( ) = rf (xk + dk )T dk :

(30)

Donc
'0 (

k)

= rf (xk +

T
k dk ) dk

T
= rf (xk+1 )T dk = gk+1
dk :

(31)

Par conséquent
'0 (

k)

T
dk = 0:
= 0 () gk+1

Une des propriétés fondamentales de la methode des direction conjuguées est théoreme
suivant :
Théorème5
Dans la méthode des direction conjuguées, on a
T
gk+1
di = 0;

k = 0; 1::::::::; n

(32)

1; i = 0; ::::::k

Preuve du théorème5
Remarquons d’abord que pour k …xé, la relation (32) contient les k + 1 égalités suivantes
8 T
d0 = 0
>
> gk+1
<
T
gk+1 d1 = 0
(33)
::::::::::
>
>
: T
gk+1 dk = 0
8
k = 0 (1 relation) : g1 d0 = 0
>
>
>
>
k = 1 (2 relations) : g2 d0 = 0 ; g2 d1 = 0
>
>
>
>
>
<
k = 2 (3 relations) : g3 d0 = 0 ; g3 d1 = 0; g3 d2 = 0
(34)
>
>
>
>
:::::::::::::::::::::::::::::::::::::::::::
>
>
>
>
k
=
n
1
(n
relations)
: gn d0 = 0 ; gn d1 = 0; :::; gn dn 1 = 0
>
:

La preuve se fait par récurence. Pour k = 0; la relation (32) est vraie. En e¤et, d’après le
théorème4 et en prenant k = 0 dans la relation(27), on obtient
(35)

g1 d0 = 0
Supposons que la relation (32) soit vraie à l’ordre k
gkT di = 0 i = 0; 1; ::::::k

1; c’est à dire que nous avons

Montrons que la relation (32) reste vraie à l’ordre k , c’est à dire, montrons que
13

(36)

1
;

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES

T
di = 0; i = 0; 1; :::::k
gk+1

(37)

En e¤et. On a en utilisant la relation (26bis)
T
di = (gk +
gk+1

T
k Qdk ) di

= gkT di +

T
k dk Qdi ;

(38)

i = 0; :::; k:

a) 0 i k 1
La relation (36) implique que
gkT di = 0:

(39)

D’autre part, et d’après la Q conjugaison des vecteurs d0 ; d1 ; :::; dn 1 ; on a
dTk Qdi = 0
(39) et (40) impliquent (38) pour 0

i

k

(40)

1:

b) i = k
Reste a prouver la relation (32) pour i = k; c’est à dire montrons que
T
gk+1
dk = 0:

Cette relation a été prouvée dans le théorème 4 (voir relation (27)): En conclusion la relation
(32) a été démontrée pour tout k n 1:

1.3

Méthode du gratient conjugué. Cas quadratique

Soit Q une matrice (n; n), symétrique et dé…nie positive. On considére dans ce paragraphe
le probléme (PQSC) suivant
min ff (x) : x 2 Rn g = min

1.3.1

1 T
x Qx
2

b T x : x 2 Rn

(PQSC)

Introduction

Dans la methode des directions conjugués, les directions d0 ; :::::dn 1 sont données à l’avance.
Dans la methode du gradient conjugué, On démarre d’un point x0 2 Rn ; d0 = g0 =
rf (x0 ) = Qx0 b: les directions dk ; k = 1; :::n 1 sont calculés à chaque itération.
A l’iteration k ,dk = gk + k 1 dk 1
dk =

gk +

k 1 dk 1

k 1 est obtenu de sorte que dk soit Q conjugué avec les autres vecteurs di , i = 0; :::; k
d’autres termes on doit avoir

dTk Qdi = 0 i = 0; :::::k

1:

1: En
(41)

Dans l’appelation gradient conjugué, on trouve les deux mots : gradient et conjugué.
a) Le mot gradient est utilisé car dk est calculé à partir du gratient au point xk :
b) Le mot conjugué est aussi justi…é, car et comme on le verra plus loin, les directions
fdk gnk=01 sont Q cojugués.
14

1.3. MÉTHODE DU GRATIENT CONJUGUÉ. CAS QUADRATIQUE

1.3.2

Algorithme du gradient conjugué. Cas quadratique

Principe de l’Algorithme
On démarre d’un point quelconque x0 2 Rn .
g0T d0
Calculez d0 = g0 = b Qx0 ; 0 =
dT0 Qd0
Supposons qu’à l’itération k on ait : xk et dk : Ceci nous permettra de calculer
gk = Qxk
k

b;

k

=

gkT dk
;
dTk Qdk

xk+1 = xk +

k dk ;

gk+1 = Qxk+1

b; dk+1 =

gk+1 +

k dk

(42)

est choisi de sorte que
dTk+1 Qdk = 0

Puisque dk+1 =

gk+1 +

k dk ;

(43)

alors (43) donne
T
k dk ) Qdk

( gk+1 +

=0

ou encore
T
k dk Qdk

et …nalement
k

=

T
= gk+1
Qdk

T
gk+1
Qdk
T
dk Qdk

(44)
(45)

Algorithme
Algorithme du gradient conjugué. Cas quadratique
1.choisir x0 2 Rn :
2. Calculez g0 = Qx0 b: Si g0 = 0 stop. Sinon poser d0 = g0 : Poser k = 0
gkT dk
:
3.Calculez k =
dTk Qdk
4. Calculez xk+1 = xk + k dk :
5. Calculez gk+1 = Qxk+1 b: si gk+1 = 0 stop.
g T Qdk
6. Calculez k = k+1
:
dTk Qdk
7. Calculez dk+1 = gk+1 + k dk :
8.Poser k = k + 1 et allez à 3 .

1.3.3

Propriétés du gradient conjugué quadratique

La propriété fondamentale du gradient conjugué cas quadratique est que les directions
fdk gnk=01 sont Q cojugués. Ces directions véri…ent comme on l’a vu dans l’algotithme
dk+1 =

gk+1 +
15

k dk ;

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
avec

T
Qdk
gk+1
= T
dk Qdk

k

D’après le théorème3, l’algorithme du gradient conjugué, version quadratique converge vers
la solution optimale en n itérations.
Avant d’enoncer et de démontrer ce résultat, démontrons les lemmes suivants :
Lemme1
Notons par
gk = rf (xk ) = Qxk
où xk ; k = 0; :::; n
on a

b

1 sont obtenus par l’algorithme du gradient conjugué quadratique. Alors
T
gk+1
gj = 0;

k = 0; 1; ::::n

1;

j = 0; 1; :::::k

Preuve du Lemme1
D’après le théorème4 (relation 24bis) et le théorèmes 5 (relation 32), on a
T
gk+1
dj = 0;

k = 0; 1::::::::; n

1; j = 0; ::::::k

(46)

et
gk+1 = gk +
Fixons k : 0
conjugué, on a

k

n

k Qdk ;

k = 0; :::; n

1 et considérons j : 0
dj =

gj +

j 1 dj 1 ;

1

(47)

j

k: D’après l’Algorithme du gradient

0

j

k

(48)

T
j 1 gk+1 dj 1

(49)

(46) implique
T
0 = gk+1
( gj +

j 1 dj 1 )

=

T
gk+1
dj

1

T
gk+1
gj +

Or
(50)

=0

Par conséquent
T
gk+1
gj = 0; 0

k

n

1;

0

j

k:

(51)

Théorème6
Les directions fd0 ; d1 ; :::; dn 1 g engendrées par l’algorithme du gradient conjugué quadratique
sont Q conjuguées.
Preuve du théorème6
La preuve du théorème6 se fait par récurence.
a)Montrons que la Q conjugaison est vraie pour k = 1; i.e. dT0 Qd1 = 0
16

1.3. MÉTHODE DU GRATIENT CONJUGUÉ. CAS QUADRATIQUE
En e¤et. Puisque
0

=

g1T Qd0
dT0 Qd0

et d1 =

g1 +

0 d0

donc
dT0 Qd1 = dT0 Q( g1 +

dT0 Qg1 +
g1T Qd0
T
T
d0 Qg1 + (d0 Qd0 ) T
=
(d0 Qd0 )

=

0 d0 )

=

T
0 d0 Qd0

(52)

dT0 Qg1 + g1T Qd0 = 0

b) Supposons que fd0 ; :::; dk g ; k < n 1 sont Q conjugués
c) Montrons que fd0 ; :::; dk+1 g ; k < n 1 sont Q conjugués
On doit montrer que
dTk+1 Qdj = 0; j 2 f0; :::; kg
En e¤et, f0; :::; kg = f0; :::; k 1g [ fkg
c1) La relation (53) est vraie pour j = k
En e¤et. Puisque
T
gk+1
Qdk
et dk+1 =
k =
dTk Qdk

gk+1 +

(1.1)

(53)

k dk

donc
dTk Qdk+1 = dTk Q( gk+1 + k dk ) = dTk Qgk+1 + k dTk Qdk
g T Qdk T
T
(d Qdk ) = dTk Qgk+1 + gk+1
=
dTk Qgk+1 + k+1
Qdk = 0
(dTk Qdk ) k
c2) La relation (53) est vraie pour j 2 f0; :::; k
En e¤et. Soit j 2 f0; :::; k 1g
T
k dk )

dTk+1 Qdj = ( gk+1 +

Qdj =

(54)

1g
T
gk+1
Qdj +

T
k dk Qdj

(55)

Si on prend en considération la proposition d’induction b) qui est vraie à l’ordre k, on a
dTk Qdj = 0; j 2 f0; :::; k

(56)

1g

Par conséquent (55) devient
dTk+1 Qdj =

T
gk+1
Qdj ; j 2 f0; :::; k

1g

(57)

Or et d’après la relation (47)
gj+1

gj =

j Qdj ;

j = 0; :::; k

par conséquent
Qdj =

1

(gj+1

j

17

gj )

1

(58)

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
et (57) donne
dTk+1 Qdj =

1
j

T
gk+1
(gj+1

1

gj ) =

j

T
gk+1
gj+1

T
gk+1
gj

(59)

Or
0

j

k

1 =) 1

j+1

k:

D’après le Lemme1, on a
T
T
gk+1
gj+1 = 0 et gk+1
gj = 0

(60)

Par conséquent La relation (53) est vraie pour j 2 f0; :::; k 1g :
c1) et c2) impliquent que la relation (53) est vraie pour j 2 f0; :::; kg : Par conséquent
fd0 ; :::; dn 1 g ; sont Q conjugués.

1.3.4

Convergence de l’Algorithme du gradient conjugué quadratique

Théorème7
Soit Q une matrice ( n; n), symétrique et dé…nie positive et (PQSC) le problème de minimisation sans contraintes quadratique suivant
1 T
x Qx
2

min ff (x) : x 2 Rn g = min

b T x : x 2 Rn

(PQSC)

Démarrant d’un point x0 2 Rn quelconque, considérons la suite fxk g générée par l’algorithme
du gradient conjugué quadratique dé…nie par
gk = rf (xk ) = Qxk
k

dk =

=

b; k = 0; 1:::

T
gk+1
Qdk
; k = 0; 1; ::
T
dk Qdk

g0 si k = 0
gk + k 1 dk 1 si k
k

=

gkT dk
dTk Qdk

(61)

1

(62)
(63)

et
xk+1 = xk +

k dk ;

(64)

Alors la suite fxk g converge en n itérations vers la solution optimale x
b du problème (PQSC),
c’est à dire que xn véri…e xn = x
b et
Qb
x = Qxn = b

Preuve du théorème7
18

(65)

1.3. MÉTHODE DU GRATIENT CONJUGUÉ. CAS QUADRATIQUE
D’après le théorème6, les directions fd0 ; d1 ; :::; dn 1 g engendrées par l’algorithme du gradient
conjugué quadratique, sont Q conjuguées. L’algorithme du gradient conjugué est une donc une
méthode à directions conjuguées. D’autre part la fonction f (x) = 21 xT Qx bT x est strictement
convexe et Rn est un convexe ouvert. Donc d’après le théorème3, la suite fxk g converge en n
itérations vers la solution optimale x
b du problème (PQSC), c’est à dire que xn véri…e xn = x
b et
Qb
x = Qxn = b:

Exercice3
Considérons la fonction f : R3 ! R dé…nie par
3
3
f (x1 ; x2 ; x3 ) = x21 + 2x22 + x23 + x1 x3 + 2x2 x3
2
2
2
3
x1
4
3.1 Notons x = x2 5 : Mettre f sous la forme suivante
x3
1
f (x) = xT Qx
2

3x1

x3

bT x

3.2 On considère le problème (1) suivant
3 2
3
x1 + 2x22 + x23 + x1 x3 + 2x2 x3 3x1 x3 : (x1 ; x2 ; x3 ) 2 R3
(1)
2
2
2 (0) 3
2 3
x1
0
7
6
4
0 5 ; et en appliquant la méthode du
=
En démarrant du point initial x(0) = 4 x(0)
5
2
(0)
0
x3
3
2
x
b1
b2 5 du problème (1)
gradient conjugué quadratique, trouver la solution optimale x
b=4 x
x
b3
Solution de l’Exercice3
3.1
min

1
(3x21 + 4x22 + 3x23 ) + x1 x3 + 2x2 x3 3x1 x3
2
2
32
3
2 3
x1
3 0 1
3
1
4
5
4
5
4
x2
=
(x1 ; x2 ; x3 ) 0 4 2
(x1 ; x2 ; x3 ) 0 5
2
1 2 3
x3
1
1 T
x Qx bT x;
=
2

f (x1 ; x2 ; x3 ) =

avec
xT = (x1 ; x2 ; x3 );

2

3
2 3
3 0 1
3
Q = 4 0 4 2 5; b = 4 0 5
1 2 3
1
19

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
3.2

2

3
3 0 1
Remarquons que la matrice Q = 4 0 4 2 5 est symetrique dé…nie positive. En e¤et
1 2 3
2
3
3 0 1
3 0
41 = 3 > 0; 42 = det
= 12 > 0; 43 = det 4 0 4 2 5 = 20 > 0
0 4
1 2 3

Donc le problème (1) est un problème de minimisation quadratique sans contraintes strictement convexe. Le problème (1) admet et une seule solution x
b solution du système
2
32
3 2 3
3 0 1
x1
3
4 0 4 2 5 4 x2 5 = 4 0 5 :
1 2 3
x3
1
2 (3) 3
x1
6 (3) 7
(3)
Si on applique la méthode du gradient conjugué quadratique, x
b = x = 4 x2 5 : Calculons
(3)
x3
2 (0) 3 2 3
x1
0
6 (0) 7 4 5
(0)
donc x3 en partant du point initial x = 4 x2 5 = 0 :
(0)
0
x3
2 (1) 3
x1
6 (1) 7
(1)
Etape1 : Calcul de x = 4 x2 5
(1)
x3
Calcul de g0 ; et d0
On a

Donc

g(x) = rf (x) = Qx
2
32
3 0 1
= 4 0 4 2 54
1 2 3

Calcul de

0

b
3
x1
x2 5
x3

2

3 2
3
3
3x1 + x3 3
4 0 5=4
5
4x2 + 2x3
1
x1 + 2x2 + 3x3 1

3
3
g0 = g(x(0) ) = b = 4 0 5
1
2 3
3
4
d0 = g0 = b = 0 5
1
0

=

2

10
g0T d0
=
= 0:2778
d0 Qd0
36
20

1.3. MÉTHODE DU GRATIENT CONJUGUÉ. CAS QUADRATIQUE
Calcul de x(1)

2

Etape2 : Calcul de x(2)
Calcul de g1 ;

0

et d1

3
0:833 4
5
0
x(1) = x(0) + 0 d0 = 4
0:277 8
2 (2) 3
x1
6 (2) 7
= 4 x2 5
(2)
x3

g1 = rf (x(1) ) = Qx(1) b
2
32
3
3 0 1
0:833 4
5
0
= 4 0 4 2 54
1 2 3
0:277 8
0

g1T Qd0
dT0 Qd0

=

0:222 0:5556 0:6668
2

=

3 0
4
3 0 1
0 4
1 2

Maintenant on est cappable de calculer d1
d1 =

Calcul de

1

1

=

3 2
3
3
0:222
4 0 5 = 4 0:555 6 5
1
0:666 8

2

32 3
3 0 1
3
4 0 4 2 54 0 5
1 2 3
1
2: 892
32 3
= 0:08025
=
36
1
3
2 54 0 5
3
1

g1 + 0 d0
3
2 3 2
3
0:222
3
0:462 75
= 4 0:555 6 5 + 0:08025 4 0 5 = 4 0:555 6 5
0:666 8
1
0:586 55
2

g1T d1
dT1 Qd1

=
0:46275
=

2

2

3
0:462 75
0:222 0:5556 0:6668 4 0:555 6 5
0:586 55
2
32
3
3 0 1
0:462 75
0:5556
0:58655 4 0 4 2 5 4 0:555 6 5
1 2 3
0:586 55

0:802 533 4
= 0:218 674 098 1
3: 669 997 53
21

CHAPITRE 1. GRADIENT CONJUGUE. CAS DES FONCTIONS QUADRATIQUES
STRICTEMENT CONVEXES
Calcul de x(2)

2

3
2
3 2
3
0:833 4
0:462 75
0:934 591 438 9
5 + 0:218 674 098 1 4 0:555 6 5 = 4 0:121 495 328 9 5
0
x(2) = x(1) + 1 d1 = 4
0:277 8
0:586 55
0:149 536 707 8
2 (3) 3
x1
6 (3) 7
(3)
Etape3 : Calcul de x = 4 x2 5
(3)
x3
Calcul de g2 ; 1 et d2
g2 = rf (x(2) ) = Qx(2) b
2
32
3
3 0 1
0:934 591 438 9
= 4 0 4 2 5 4 0:121 495 328 9 5
1 2 3
0:149 536 707 8
=

1

g2T Qd1
dT1 Qd1

32
3
3 0 1
0:462 75
0:186907 0:140210 4 0 4 2 5 4 0:555 6 5
1 2 3
0:586 55
0:259 579 6
2
32
3 =
= 0:070 73
3: 669 997
3 0 1
0:462 75
0:5556
0:58655 4 0 4 2 5 4 0:555 6 5
1 2 3
0:586 55

=
0:46275

2

3
2
3 2
3
0:046 688 975 5
0:462 75
0:079 419 283
5 + 0:070 73 4 0:555 6 5 = 4 0:147 610 312 5
0:186 907 9
g2 + 1 d1 = 4
0:140 210 904 5
0:586 55
0:181 697 586

Calcul de
2

=

2

g2T d2
dT2 Qd2
0:046689

=

5: 677 355 533
0:068 977

10

2

0:186908 0:140211 4

0:079 419 283 0:147 610 312
=

3 2
3
3
0:046 688 975 5
4 0 5=4
0:186 907 9 5
1
0:140 210 904 5

2

0:046 68

d2 =

2

2

= 0:8231

2

3
4
0:181 697 586
0
1

22

3
0:079 419 283
0:147 610 312 5
0:181 697 586
32
3
0 1
0:079 419 283
4 2 5 4 0:147 610 312 5
2 3
0:181 697 586

1.3. MÉTHODE DU GRATIENT CONJUGUÉ. CAS QUADRATIQUE
Calcul de x(3)

x(3)

2

3
2
3 2
0:934 591 438 9
0:079 419 283
= x(2) + 2 d2 = 4 0:121 495 328 9 5+0:8231 4 0:147 610 312 5 = 4
0:149 536 707 8
0:181 697 586

3
0:999 961 450 7
2: 718 907 2 10 6 5
1: 857 523 66 10 5

Puisque ces calculs ont été e¤ectués avec des arrondis, on peut supposer que la solution est
2 3
1
(3)
4
x = 0 5
0

En e¤et

g3 = rf (x(3) ) = Qx(3)

2

32 3
3 0 1
1
4
5
4
0 5
b= 0 4 2
1 2 3
0

23

2

3 2 3
3
0
4 0 5=4 0 5
1
0

Chapitre 2
GRADIENT CONJUGUE. CAS DES
FONCTIONS NON QUADRATIQUES
2.1

Introduction et di¤érentes formes du gradient conjugué

Soit f : Rn ! R non quadratique. On cherche à résoudre le problème non quadratique sans
contraintes (PNQSC) suivant :
min ff (x) : x 2 Rn g
(PNQSC)
Parmi les plus anciennes méthodes utilisées pour résoudre les problèmes du type (PNQSC),
on peut citer la méthode du Gradient conjugué. Cette méthode est surtout utilisée pour les
problèmes de grande taille.
Cette méthode a été découverte en 1952 par Hestenes et Steifel ([1]), pour la minimisation
des fonctions quadratiques strictement convexes.
Plusieurs mathématiciens ont étendu cette méthode pour le cas non quadratique. Ceci a été
réalisé pour la première fois, en 1964 par Fletcher et Reeves ([2]) (méthode de Fletcher-Reeves)
puis en 1969 par Polak, Ribière ([3]) et Ployak ([3bis]) (méthode de Polak-Ribière-Ployak).
D’autres variantes ont été étudiées plus tard ([4],[5],[6],[7],[8],[9],[10])Une autre variante a été
étudiée en 1987 par Fletcher ([4]) (Méthode de la descente conjuguée).
Toutes ces méthodes génèrent une suite fxk gk2N de la façon suivante :
xk+1 = xk +

(1)

k dk

Le pas k 2 R est déterminé par une optimisation unidimensionnelle ou recherche linéaire
exacte ou inexacte du type Armijo, Goldstein ou Wolfe.
Les directions dk sont calculées de façon récurrente par les formules suivantes :
dk =
avec gk = rf (xk ) et

k

g0
gk +

k

2 R:
24

si k = 0
1 dk 1 si k

1

(2)

2.1. INTRODUCTION ET DIFFÉRENTES FORMES DU GRADIENT CONJUGUÉ
Les di¤érentes valeurs attribuées à
gué.
Si on note
yk 1 = gk

dé…nissent les di¤érentes formes du gradient conju-

k

gk 1 ; sk = xk+1

xk

(3)

on obtient les variantes suivantes :
1952 ([1])- Gradient conjugué variante Hestenes - Stiefel(HS)
HS
k

T
gk+1
yk
T
dk yk

=

(4)

1964 ([2])-Gradient conjugué variante Fletcher Reeves(FR)
FR
k

=

kgk+1 k2
kgk k2

(5)

1969 ([3],([3bis]))- Gradient conjugué variante Polak-Ribière-Polyak(PRP)
P RP
k

=

T
gk+1
yk

(6)

kgk k2

1987 ([4])- Gradient conjugué variante descente conjuguée –Fletcher (CD)
CD
k

kgk k2
dTk 1 gk

=

(7)
1

1991 ([5])- Gradient conjugué variante Liu - Storey(LS)
LS
k

=

T
yk
gk+1
T
dk gk

(8)

1999 ([6])- Gradient conjugué variante de Dai-Yuan(DY)
DY
k

kgk k2
= T
dk 1 yk

(9)
1

2005([7])- Gradient conjugué variante Hager-Zhang(HZ)
HZ
k

=

kyk k2
2dk T
dk yk

yk

!T

gk+1
dTk yk

(10)

2012([8])- Gradient conjugué variante Rivaie-Mustafa-Ismail-Leong(RMIL)[60]
RM IL
k 1

=

gkT (gk gk 1 )
kdk 1 k2
25

(12)

CHAPITRE 2. GRADIENT CONJUGUE. CAS DES FONCTIONS NON QUADRATIQUES
Remarque1
Dans le cas où f n’est pas quadratique on a
HS
k

FR
k

6=

6=

P RP
k

CD
k

6=

LS
k

6=

DY
k

6=

6=

HZ
k

6=

RM IL
k

(13)

Par conséquent, en appliquant l’algorithme du gradient conjugué non quadratique, en utilisant
les coé¢ cients k …gurant dans (13), on obtient des suites fxk gk2N di¤érentes.
Que se passe t’il si f est quadratique strictement convexe et si k est obtenue par une
recherche linéaire exacte. La réponse à cette question se trouve dans le théorème suivant.
Théorème1
Si f (x) = 21 xT Qx bT x; avec Q symétrique dé…nie positive, x 2 Rn ; b 2 Rn et si
obtenue par une recherche linéaire exacte. Notons
k

k

est

T
gk+1
Qdk
= T
;
dk Qdk

alors on a
k

=

HS
k

=

FR
k

=

P RP
k

CD
k

=

LS
k

=

=

DY
k

=

HZ
k

=

RM IL
k

(14)

et l’algorithme du gradient conjugué quadratique génère la même suite fxk gk2N :
Preuve du théorème1
a) Montrons que k = HS
k
En e¤et. Rappellons que si (x) = 21 xT Qx bT x; avec Q symétrique dé…nie positive, x 2
Rn ; b 2 Rn et si k est obtenue par une recherche linéaire exacte, alors on a
k

=

T
gk+1
Qdk
T
dk Qdk

(15)

On va transformer (15) de di¤érentes façons de sorte que la matrice Q disparaisse. D’après
la formule (26bis-Théorème4-Chapitre1) on a
gk+1

gk =

(16)

k Qdk

(16) implique
Qdk =

gk+1

gk

(17)

k

Par conséquent (15) devient

k

b) Montrons que

=

T gk+1 gk
gk+1
k

dTk gk+1k gk

HS
k

=

=

T
T
gk+1
(gk+1 gk )
gk+1
yk
=
=
T
T
dk (gk+1 gk )
dk yk

FR
k

26

HS
k

(18)

2.1. INTRODUCTION ET DIFFÉRENTES FORMES DU GRADIENT CONJUGUÉ
En e¤et. Puisque
dk =

gk +

(19)

k 1 dk 1

alors
HS
k

=

T
gk+1
gk+1

T
gk+1
(gk+1 gk )
=
T
dk (gk+1 gk )

gk +

k
T
gk+1 gk

T
gk+1
gk+1

=

T
gk + gkT gk +
gk+1

1 dk

T
k 1 gk+1 dk 1

T
gk+1
gk
T
1

(gk+1

(20)
gk )
(2.1)

T
k 1 gk dk 1

Or d’après le lemme1-Chapitre1, on a
T
gk+1
gk = 0

(21)

et d’après la relation (32)-Chapitre1-Théorème5 on a
T
gk+1
dk

1

= 0 et gkT dk

1

(22)

= 0:

Par conséquent (20), (21) et (22) donnent
HS
k

c) Montrons que
En e¤et. On a
HS
k

HS
k

=

T
gk+1
gk+1
=
=
gkT gk

FR
k

(23)

P RP
k

T
gk+1
(gk+1 gk )
=
= T
dk (gk+1 gk )

T
gk+1
yk

gk +

T

k 1 dk 1

(gk+1

T
gk+1
yk
=
= T
gk gk
gk )

P RP
k

(24)

Exercice1
Montrez que
k

=

CD
k

=

LS
k

=

DY
k

=

HZ
k

=

RM IL
k

2.1.1

Algorithme du gradient conjugué non quadratique

2.1.2

Introduction

Soit f : Rn ! R non quadratique et (PNQSC) le problème de minimisation non quadratique
sans contraintes suivant :
min ff (x) : x 2 Rn g
(PNQSC)

Pour construire l’algorithme du gradient conjugué cas non quadratique, on peut s’inspirer de
l’algorithme du gradient conjugué quadratique établi au chapitre précédent. Contrairement au
cas quadratique, on n’a pas de matrice Q. Par conséquent on n’a pas de directions Q conjuguées.
Comme dans le cas quadratique, l’algorithme du gradient conjugué cas non quadratique génère
une suite fxk gk2N de la manière suivante :
xk+1 = xk +
27

k dk

CHAPITRE 2. GRADIENT CONJUGUE. CAS DES FONCTIONS NON QUADRATIQUES
L’algorithme démarre d’un point x0 2 Rn quelconque.
A l’itération k
Supposons qu’on ait le vecteur xk 2 Rn et la direction dk 1 : Ceci nous permet de calculer
rf (xk ) au lieu gk = Qxk b dans le cas quadratique. Pour avoir xk+1 , on a besoin de calculer
k et dk :
Calcul de dk :
rf (xk ) +

dk =
On a huit façons pour calculer

k 1

HS
k 1

=

rf (xk )T (rf (xk ) rf (xk 1 ))
dTk 1 (rf (xk ) rf (xk 1 ))

PR
k 1

=

rf (xk )T (rf (xk ) rf (xk 1 ))
k rf (xk 1 ) k2
FR
k 1

DY
k 1

LS
k 1

=

=

(rf (xk )

rf (xk )T (rf (xk ) rf (xk 1 ))
dTk 1 rf (xk 1 )

=

=

krf (xk )k2
dTk 1 rf (xk 1 )

krf (xk ) rf (xk 1 )k2
2dk 1 T
dk 1 (rf (xk ) rf (xk 1 ))

rf (xk 1 ))
RM IL
k 1

=

k dk )

!T

rf (xk )
(rf (xk ) rf (xk 1 ))T yk

(rf (xk ))T (rf (xk ) rf (xk 1 ))
kdk 1 k2

Calcul de k
Ayant obtenu dk , rappelons que
f (xk +

k rf (xk ) k2
=
k rf (xk 1 ) k2

k rf (xk ) k2
dTk 1 (rf (xk ) rf (xk 1 ))

CD
k 1

HZ
k 1

(25)

k 1 dk 1

k

véri…e

= min ff (xk + dk ) :

2]0; +1[g :

Dans le cas où f (x) = 21 xT Qx b; Q symétrique dé…nie positive,
par la relation suivante
gkT dk
:
k =
dTk Qdk

k

(26)

solution de (26), est donnée
(27)

Dans le cas où f n’est pas quadratique, k ne peut pas être calculée par la formule (27). On
calcule dans ce cas k par d’autres méthodes. On utilise par exemple la méthode du nombre
d’or ou la méthode de dichotomie. Comme on le verra plus loin, k peut être calculée par une
recherche linéaire inexacte d’Armijo ou Goldstein ou Wolfe.
28

1

2.1. INTRODUCTION ET DIFFÉRENTES FORMES DU GRADIENT CONJUGUÉ

2.1.3

Algorithme du Gradient conjugué non quadratique

Algorithme
Etape1
Choisir x0 2 Rn Quelconque et " > 0
Etape2
Poser k = 0
Calculez g0 = rf (x0 ): Posez d0 = g0
Etape3
Calculez k en utilisant une rechreche linéaire exacte ou inexacte d’Armijo ou de Goldstein
ou de Wolfe ou de Wolfe Forte
Calculez xk+1 = xk + k dk
Etape4
Si krf (xk+1 )k < "; Stop, x = xk+1 : Sinon allez à Etape5
Etape5
Calculez gk+1 = rf (xk+1 )
Calculez k par l’une des manières suivantes
k

ou

k

=
=

HS
k
LS
k

ou
ou

k
k

=

=

FR
ou
k
DY
ou k
k

k

=

=
HZ
k

P RP
k

ou
ou k =

CD
k = k
RM IL
k

Calculez
dk+1 =

gk+1 +

k dk

Posez k = k + 1 et allez à Etape3
Exercice2
a) On considère la fonction f (x; y) = x2 + y 4 : En partant du point initial (x0 ; y0 ) = (1; 1) et
en appliquant la méthode du gradient conjugué avec la recherche linéaire de Wolfe, calculez
(x1 ; y1 ) :
Paramètres de Wolfe : = 0:1; = 0:3; a0 = 0; b0 = 1099
Projet de TP1
Considérons la fonction f : Rn ! R; dite d’Oren suivante :
" n
#2
X
(x1 ; x2 ; :::; xn ) ! f (x1 ; x2 ; :::; xn ) =
ix2i
i=1

Remarquons d’abord que la solution optimale est x = (0; :::0) et f (x ) = 0:
On applique l’Algorithme du gradient conjugué versions HS, FR et PRP avec la recherche
linéaire inexacte de Wolfe. On démarre du point x0 = (1; 1; :::::; 1). On arrête l’algorithme
lorsque
krf (xk )k < 10 5
Ecrire le programme en Fortran. Donner les résultats numériques pour n = 100; n = 1000; n =
10000: Donner le nombre d’itérations nécessaires pour arriver à de tels résultats (krf (xk )k <
10 5 ). Conclure.
29

CHAPITRE 2. GRADIENT CONJUGUE. CAS DES FONCTIONS NON QUADRATIQUES
Le programme en Fortran 95 pour la fonction de Oren
program CGWP
implicit none
integer, parameter : :n=1000
integer ik,j,k,cont,test
double precision y(n),g(n),gp(n)
double precision d(n),eps
double precision alphd,alph0
double precision b,w,alphg,f0,f1
print*,’ENTRER Y’
do ik=1,n
y(ik)=1
enddo
print*,’ENTRER EPS’
read*,eps
b=0.7 ;w=0.1 ;cont=1 ;test=0
g=df(y) ;f0=f(y) ;d=-g ;j=1 ;k=1
do while(sqrt(dot_product(g,g))>eps)
alphg=0 ;alphd=100 ;alph0=1
gp=g
do
cont=cont+1
f1=f(y+alph0*d)
if(f1<=f0+w*alph0*dot_product(gp,d))then
g=df(y+alph0*d)
if(dot_product(g,d)>=b*dot_product(gp,d))then
exit
else
alphg=alph0 ;alph0=(alphg+alphd)/2.
endif
else
alphd=alph0 ;alph0=(alphg+alphd)/2.
endif
enddo
y=y+alph0*d
k=k+1
if(j<n)then
d=-g+(dot_product(g,g)/dot_product(gp,gp))*d
j=j+1
if(dot_product(g,d)>=0)then
j=1 ;test=test+1
d=-g
endif
30

2.1. INTRODUCTION ET DIFFÉRENTES FORMES DU GRADIENT CONJUGUÉ
else
d=-g
j=1
endif
if(f0-f1<1.e-14)then
print*
print*,’LA NORME DU GRADIENT’
print ’(e20.2)’,sqrt(dot_product(g,g))
g=0
endif
f0=f1
enddo
print*
print*,’LE NOMBRE D ITERATIONS’
print*,k
print*,’LA VALEUR DE LA FUNCTION’
print ’(e20.2)’,f(y)
print*,’NOMBRE D EVALUATIONS FONCTIONNELLES’,cont
contains
function f(u)
double precision f,u(n)
integer i
f=0
do i=1,n
f=f+i*u(i)**2
enddo
f=f**2
endfunction
function df(u)
double precision df(n),u(n),sm
integer i
sm=0
do i=1,n
sm=sm+i*u(i)**2
enddo
do i=1,n
df(i)=4*i*u(i)*sm
enddo
endfunction
end
Résultats numériques
Tableau 1:( =
31

HS

)

CHAPITRE 2. GRADIENT CONJUGUE. CAS DES FONCTIONS NON QUADRATIQUES
n
100
1000
10000

k : nombre iterations
64
183
620
Tableau 2:( =

n
100
1000
10000

k : nombre iterations
64
174
833

f (xk )
0:29 10
0:12 10
0:16 10
FR

8
7
8

)

k : nombre iterations
69
223
746
Tableau 3:( =

n
100
1000
10000

PR

f (xk )
0:80 10
0:18 10
0:85 10

7
7
7

)
f (xk )
0:78 10
0:20 10
0:95 10

8
7
9

Projet de TP2
Même projet que le projet de TP1 en considérant la fonction de Powell généralisée.
Programme en Fortran95
! le programme en fortran 95 des méthodes du gradient conjugué
! avec la recherche linéaire non exacte de Wolf-Powell
! fonction de powell généralisée
program CGWP
implicit none
integer, parameter : :n=10000
! test : nombre des direction engendré par la méthode du GC
! et qui ne sont pas des directions de descente
! cont : nombre des évaluations fonctionnelles
integer ik,j,k,cont,test
! Y : la suite, g : le gradient, d : la direction de déplacement
! eps : epcilon (critère de convergence)
double precision y(n),g(n),gp(n)
double precision d(n),eps
double precision alphd,alph0
double precision b,w,alphg,f0,f1
integer (2) hour,minut,second,hsedt
call gettim(hour,minut,second,hsedt)
print*,hour,minut,second,hsedt
print*,’ENTRER Y’
do ik=1,n/4
y(4*ik-3)=3
32

2.1. INTRODUCTION ET DIFFÉRENTES FORMES DU GRADIENT CONJUGUÉ
y(4*ik-2)=-1
y(4*ik-1)=0
y(4*ik)=1
enddo
print*,’ENTRER EPS’
eps=1.e-10
b=0.9 ;w=0.1 ;cont=1 ;test=0
g=df(y) ;f0=f(y) ;d=-g ;j=1 ;k=1
do while(sqrt(dot_product(g,g))>eps)
! recherche linéaire
alphg=0 ;alphd=100 ;alph0=1
gp=g
do
cont=cont+1
f1=f(y+alph0*d)
if(f1<=f0+w*alph0*dot_product(gp,d))then
g=df(y+alph0*d)
if(dot_product(g,d)>=b*dot_product(gp,d))then
exit
else
alphg=alph0 ;alph0=(alphg+alphd)/2.
endif
else
alphd=alph0 ;alph0=(alphg+alphd)/2.
endif
enddo
! le nouveau point
y=y+alph0*d
k=k+1
if(j<n)then
d=-g+(dot_product(g,g-gp)/dot_product(d,g-gp))*d
j=j+1
if(dot_product(g,d)>=0)then
j=1
d=-g
test=test+1
endif
else
d=-g
j=1
endif
!test de la décroissance négligeable
if(f0-f1<1.e-14)then
33

CHAPITRE 2. GRADIENT CONJUGUE. CAS DES FONCTIONS NON QUADRATIQUES
print*
print*,’THE NORM OF GRADIENT’
print ’(e20.2)’,sqrt(dot_product(g,g))
g=0
endif
f0=f1
enddo
! a¢ chage du temps
call gettim(hour,minut,second,hsedt)
print*,hour,minut,second,hsedt
!a¢ chage des résultats
print*
print*,’THE NUMBER OF ITERATION’
print*,k
print*,’THE FUNCTION VALUE’
print ’(e20.2)’,f(y)
print*,’NOMBRE D EVALUATIONS FONCTIONNELLES’,cont
print*,’test=’,test
! les procédures intérieurs
contains
! la fonction objective
function f(u)
double precision f,u(n)
integer i1
f=0.
do i1=1,n/4
f=f+(u(4*i1-3)+10*u(4*i1-2))**2+5*(u(4*i1-1)-u(4*i1))**2+&
(u(4*i1-2)-2*u(4*i1-1))**4+10*(u(4*i1-3)-u(4*i1))**4
enddo
endfunction
! calcul du gradient
function df(u)
double precision df(n),u(n)
integer i1
do i1=1,n/4
df(4*i1-3)=2*(u(4*i1-3)+10*u(4*i1-2))+40*(u(4*i1-3)-u(4*i1))**3
df(4*i1-2)=20*(u(4*i1-3)+10*u(4*i1-2))+4*(u(4*i1-2)-2*u(4*i1-1))**3
df(4*i1-1)=10*(u(4*i1-1)-u(4*i1))-8*(u(4*i1-2)-2*u(4*i1-1))**3
df(4*i1)=-10*(u(4*i1-1)-u(4*i1))-40*(u(4*i1-3)-u(4*i1))**3
enddo
endfunction
end

34

Chapitre 3
SYNTHESE DES RESULTATS DE
CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON
QUADRATIQUE
Avant tout rappelons que les di¤érentes variantes du gradient conjugué algorithme génèrent
une suite fxk gk2N dans Rn dé…nie par x0 2 Rn quelconque et les itérations
xk+1 = xk +

k dk ;

(GC1)

k = 0; 1; 2; :::

avec k est le résultat d’une recherche linéaire exacte ou inexacte du type Armijo ou Goldstein
ou Wolfe ou Wolfe forte ou Wolfe relaxée. Les directions dk sont calculées itérativement par la
formule
g0 si k = 0
dk =
(GC2)
= gk + k 1 dk 1 ; k 1
avec gk = rf (xk ) et
k

ou

k

=
=

HS
k
LS
k

ou
ou

k
k

=

=

FR
ou
k
DY
ou k
k

k

=

=
HZ
k

P RP
k

ou
ou k =

CD
k = k
RM IL
k

(GC3)

Dans ce chapitre on va essayer de présenter une synthèse sur les di¤érents résultats de convergence des méthodes du gradient conjugué pour la minimisation des fonctions sans contraintes.
Ces méthodes seront utilisées avec une recherche linéaire inexacte. L’analyse couvre quatre
classes de méthodes qui sont globalement convergentes pour des fonctions régulières non nécessairement convexes. Dans la première famille, ce sont certaines propriétés de la méthode de
Fletcher-Reeves qui jouent un rôle crucial, tandis que la seconde famille c’est la méthode de
Polak-Ribière-Polyak qui a une propriété importante. La troisième concerne la méthode de la
descente conjuguée et la dans dernière famille on va présenter quelques propriétés de la nouvelle méthode du gradient conjugué non linéaire dite de Dai-Yuan. On terminera ce chapitre
par Quelques développements récents de la méthode du Gradient conjugué.
35

CHAPITRE 3. SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE

3.1
3.1.1

Hypothèses C1 et C2 et théorème de Zoutendijk
Hypothèses C1 et C2 (de Lipschitz et de bornetude)

Rappelons dans ce qui suit les deux conditions suivantes que toutes les méthodes du gradient conjugué doivent véri…er (ou au moins l’une d’entre elles) pour prouver les résultats de
convergence.
Condition C1
Soit f : Rn ! R: On dit que f véri…e la condition C1 si f est contiuement di¤érentiable
dans un voisinage V ( ) de
= fx 2 Rn : f (x) f (x1 ) : x1 2 Rn point initialg et si rf (x)
véri…e la condition de Lipschitz dans V ( ), c’est à dire, il existe une constante L telle que
krf (x)

rf (y)k

Condition C2
L’ensemble = fx 2 Rn : f (x)
que

L kx

f (x1 )g est borné, i.e., il existe une constante B < 1 telle
kxk

3.1.2

yk : pour tout x; y 2 V ( )

B : 8x 2

Théorème de Zoutendijk

L’outil de base utilisé par les di¤érentes variantes du gradient conjugué avec une recherche
linéaire inexacte est le théorème suivant du à Zoutendijk
Théorème de Zoutendijk ([ ]) Considérons une méthode itérative quelconque générant
une suite fxk gde la forme :
xk+1 = xk + k dk ;
dk étant une direction de descente et k est une recherche linéaire inéxacte de Wolfe. Supposons aussi que f véri…e la Condition C1. Alors on a
1
X
gkT dk
k=0

3.1.3

kdk k2

2

<1

(4.0)

Utilisation du théorème de Zoutendijk pour démontrer la convergence globale

2
P
P1
(gkT dk )
2
2
La condition 1
k=0 kdk k2 < 1 est équivalente à
k=1 cos ( k ) kgk k < 1 où
que fait dk avec gk : Il est évident de voir que si

cos( k )
36

>0

k

est l’angle

3.1. HYPOTHÈSES C1 ET C2 ET THÉORÈME DE ZOUTENDIJK
pour tout k; alors on a
lim kgk k = 0:

k!1

Dans les di¤érentes méthodes du gradient conjugué on n’arrive pas à démontrer le résultat
précédent i.e., lim kgk k = 0; mais seulement
k!1

lim inf kgk k = 0:

(4.0bis)

k!1

La condition (4.0) bis implique qu’il existe une sous suite de fkgk kg qui tend vers zéro.
Conditions su¢ santes associés au théorème de Zoutendijk pour démontrer la
relation(4.0bis)
Pour démontrer (4.0bis) on associe au théorème de Zoutendijk les 2 hypothèses suivantes :
Hypothèse1
La decente su¢ sante est assuréé, i.e., il existe une constante c indépendante de k telle que
c kgk k2

gkT dk
Hypothèse 2
Il existe une constante

telle que
kdk k2

k

On a donc
8
2
P
(gkT dk )
>
< relation de Zoutendijk ( 1
k=0 kdk k2 < 1)
Hypothese1
>
:
Hypothese2

9
>
=
>
;

n
o
=) lim inf kgk k = 0
k!1

Remarque importante
La condition Hypothèse1 est plus forte que la descente. En e¤et
gkT dk

c kgk k2 =) gkT dk < 0:

La condition Hypothèse1 n’est pas nécessaire pour avoir lim inf kgk k = 0: Dai et Yuan ([
k!1

]) ont montré la convergence globale seulement avec la condition de descente : gkT dk < 0:
D’autre part la condition Hypothèse1, i.e. gkT dk
c kgk k2 n’est pas su¢ sante toute seule,
pour avoir la convergence globale.
Dé…nition
Nous dirons qu’une méthode de gradient conjugué converge globalement si l’une des deux
conditions suivantes est véri…ée
a) gk0 = 0; pour un certain k0 2 N
b) lim inf kgk k = 0:
k!1

Une autre version du théorème de Zoutendijk se trouve dans [ ]. Ce sera l’objet du théorème
suivant
37

CHAPITRE 3. SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE
Théorème Zoutendijk bis ([ ]) Considérons une méthode itérative quelconque générant
une suite fxk gde la forme :
xk+1 = xk + k dk ;
dk étant une direction de descente et k est une recherche linéaire inéxacte de Wolfe forte.
Supposons aussi que f véri…e la Condition C1. Alors ou bien
lim inf kgk k = 0:
k!1

ou

1
X
kgk k4
k=0

3.2

kdk k2

<1

Role joué par la direction de recherche initiale

Commençons d’abord par donner un petit aperçu sur le role joué par la direction de recherche
initiale.
Il est essentiel de prendre d0 = g0 dans un algorithme de CG. En 1972, Crowder et Wolfe
[12] ont donné un exemple en 3 dimensions qui montre que le taux de convergence est linéaire si
la direction de la recherche initiale n’est pas la direction de la plus grande pente, même pour une
fonction quadratique fortement convexe. En 1976, Powell [57] a obtenu un résultat encore plus
fort, il a montré que si la fonction objectif est une fonction quadratique convexe et si la direction
de recherche initiale est une direction de descente arbitraire, alors, soit la condition d’optimalité
est obtenue dans n + 1 itérations, ou la vitesse de convergence est seulement linéaire. En outre,
en analysant la relation entre x0 et d0 , il s’ensuit que la convergence linéaire est plus fréquente
que la convergence …nie.
A…n de parvenir à une convergence …nie pour une direction de recherche initiale arbitraire,
Nazareth [52] a proposé un algorithme CG basée sur une récurrence à trois termes :
dk+1 =

yk +

ykT 1 yk
ykT yk
d
+
dk
k
dTk yk
dTk 1 yk 1

1

(4.1)

avec d 1 = 0 et d0 une direction de descente arbitraire. Si f est une fonction quadratique
convexe, alors pour tout k , les directions de recherche générés par (4.1) sont conjugués par
rapport au Hessian de f . Toutefois, cette innovation intéressante n’a pas vu une utilisation
importante dans la pratique.

3.3

Les méthodes dans lesquelles le terme kgk+1k2 …gure
dans le numérateur de k

Les méthodes FR, DY et CD ont toutes comme numérateur commun le terme kgk+1 k2 .
Une di¤érence fondamentale qui caractérise ces méthodes par rapport aux autres méthodes du
38

3.3. LES MÉTHODES DANS LESQUELLES LE TERME kGK+1 k2 FIGURE DANS LE
NUMÉRATEUR DE K
gradient conjugué où k est calculé di¤érement, est que les théorèmes de convergence globale
nécessitent seulement la condition de Lipschitz : Condition C1 et n’ont pas besoin de la
condition de bornétude Condition C2 .

3.3.1

Méthode de Fletcher-Reeves

Cette méthode été découverte en 1964 par Fletcher et Reeves ([35]),
FR
k+1

kgk+1 k2
=
kgk k2

k

est égale à :
(FR)

Synthèse des principaux résultats de convergence pour la méthode de FletcherReeves
Le premier résultat de convergence globale de la méthode de FR a été donnée par Zoutendijk [77] en 1970. Il a prouvé que la méthode Fletcher-Reeves converge globalement quand k
est une recherche linéaire exacte , en d’autres mots. En 1977, Powell [58] a fait remarquer que
la méthode de Fletcher-Reeves, avec une recherche linéaire exacte, était sensible numériquement. Autrement dit, l’algorithme pourrait prendre de nombreuses mesures courtes sans faire
d’importants progrès au minimum. La mauvaise performance de la méthode de FR dans les
applications a été souvent attribuée à ce phénomène de brouillage .
Le premier résultat de convergence globale de la méthode de FR pour une recherche linéaire
inexacte a été donné par Al- Baali [1] en 1985. En utilisant les conditions de Wolfe forte avec
< 21 , il a prouvé que la méthode FR génère des directions de descente su¢ santes. Plus
précisément , il a prouvé que :
1

2 +
1

k+1

gkT dk
kgk k2

k+1

1

;

1

pour tout k 0. Comme conséquence, la convergence globale a été démontrée en utilisant
la condition Zoutendijk. Pour = 1=2, dk est une direction de descente, toutefois, l’analyse
n’a pas établi la descente su¢ sante.
Dans Liu et al. [50], la preuve de la convergence d’Al-Baali est étendue au cas = 1=2. Dai
et Yuan [21] ont montré que dans les versions FR consécutives, au moins une itération satisfait
la propriété de descente su¢ sante. En d’autres termes,
max

gkT dk gkT 1 dk 1
;
kgk k2
kgk 1 k2

1
2

Le théorème de Zoutendijk bis peut également être utilisé pour obtenir un résultat de
convergence globale pour les méthodesFR mis en œuvre avec une recherche inexacte de Wolfe
forte et
1=2; puisque les directions de recherche sont toujours des directions de descente.
Dans [28], Dai et Yuan montrent qu’avec la méthode de FR, les conditions Wolfe fortes
n’engendrent pas en général des directions de descente quand > 1=2, même pour la fonction
f (x) = kxk2 , où > 0 est une constante. Par conséquent, la contrainte
1=2 doit être
39

CHAPITRE 3. SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE
imposée pour assurer la descente. Dans les implémentations typiques des conditions Wolfe, il est
souvent plus e¢ cace de choisir proche de 1. Par conséquent, la contrainte
1=2, nécessaire
pour assurer la descente, représente une restriction importante dans le choix des paramètres
de la recherche linéaire. D’autre part, Dai et Yuan montrent dans [25] que, lorsque > 1=2
et gkT dk > 0, dk peut être utilisé pour une direction de recherche, et si gkT dk = 0, alors la
recherche linéaire peut être ignorée par le choix xk+1 = xk . S’il existe une constante telle que
kgk k
, sous la condition de Lipschitz, la méthode de FR, avec une recherche linéaire de
Wolfe et ces ajustements spéciaux quand gkT dk 0, est globalement convergente.
Dans [21], la recherche linéaire de Wolfe forte est étendue à une recherche linéaire de Wolfe.
La convergence globale est obtenue lorsque 1 + 2 1. Pour une recherche linéaire de Wolfe
forte, 1 = 2 = , dans ce cas, la contrainte 1 + 2 1 implique que
1=2. Par conséquent,
la condition 1 + 2 1 est plus faible que la contrainte de Wolfe forte
1=2. Et il est possible
de prendre 1 proche de 1, en prenant 2 près de 0.
Résultats d’El Baali
Comme on l’a remarqué auparavant le premier et le plus important résultat de convergence
de la méthode Fletcher Reeves (FR), avec une recherche linéaire inexacte est celui d’El Baali
([38]). Nous exposons dans ce qui suit en détail ses résultats.
Théorème 3.3.1 ([38-El Baali]) Supposons que L’hypothèse Condition C1 soit satisfaite.
2
Considérons une méthode du type (GC1), (GC2), (GC3) avec k = Fk R = kgkgk k k2 et le pas k
k 1

satisfaisant à la règle de (Wolfe-forte1) et (Wolfe-forte2) où
dTk gk
kgk k2

1
1

2
1

1

2 0; 12 : Alors on a

(4.2)

; k = 1; :::

Preuve. La démonstration se fait par récurrence
1) Pour k = 1 :
dT1 g1
kg1 k2
=
=
kg1 k2
kg1 k2

1

D’autre part :

0<

<

1

1
)
2

1
2
1

1
1

1

2) Supposons que (4.2) est satisfaite pour k > 1 et démontrons qu’elle le sera pour k + 1 :
Supposons que :
1
dTk gk
2
1
; k = 1; :::
(*)
2
1
1
kgk k
On a :

dTk+1 gk+1
kgk+1 k

2

=

gk+1 +

k+1 dk
kgk+1 k2

40

T

gk+1

=

1+

T
k+1 dk gk+1

3.3. LES MÉTHODES DANS LESQUELLES LE TERME kGK+1 k2 FIGURE DANS LE
NUMÉRATEUR DE K
D’autre part de (4.14) on aura :
kgk k2
=
)
kgk 1 k2

FR
k

d’où :

dTk+1 gk+1
kgk+1 k2

=

1
FR
k+1

kgk k2
=
kgk + 1k2

k+1
FR
k

1+

dTk gk+1
kgk k2

(**)

En utilisant la condition de la recherche linéaire (2.19) on aura :
dTk gk+1

dTk gk )

dTk gk

k+1

T
k+1 dk+1 gk+1

k+1

dTk gk

soit en remplaçant ceci dans (**), on obtient :
T
k+1 dk gk
2
FR
k+1 kgk k

1+

dTk+1 gk+1

T
k+1 dk gk
2
FR
k+1 kgk k

1

kgk+1 k2

De (*) on aura :
dTk+1 gk+1

k+1

1

FR
k+1

(1

)

kgk+1 k

1+

2

k+1
FR
k+1 (1

)

et de (4.17) :
<

1

k+1
FR
k+1

<1

Par conséquent on aura :
dTk+1 gk+1

1

2

1

kgk+1 k

Ce qui achève la démonstration.

2
1

1

Corollaire 3.3.1 Sous les mêmes hypothèses et conditions du Théorème précédent, on a pour
tout k 1; dk est une direction de descente su¢ sante i.e., il existe une constante C > 0 telle
que
gkT dk
C kgk k2
Preuve du Corollaire
On a d’après (4.2)
1
1

dTk gk
kgk k2
) dTk gk

avec C =

2
1
2
1

1
1

kgk k2 =

1 2
1

41

1 2
kgk k2 =
1

C kgk k2 ;

CHAPITRE 3. SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE
Théorème 3.3.2 ([38El Baali]) Supposons que L’hypothèse Condition C1 soit satisfaite.
2
Considérons une méthode du type (GC1), (GC2), (GC3) avec k = Fk R = kgkgk k k2 et le pas k
k 1

2 0; 12 : Alors cette méthode

satisfaisant à la règle de (Wolfe-forte1) et (Wolfe-forte2) où
est globalement convergente, dans le sens suivant :
lim inf kgk k = 0

(4.3)

k!1

Preuve. Puisque les conditions du théorème 4.2 sont satisfaites alors on a :
dTk gk
kgk k2

1
1

2
1

1

dTk 1 gk

)

1

kgk 1 k2

1

D’autre part de (4.10)
dTk gk ) dTk 1 gk

dTk gk+1

dTk 1 gk

1

d’où
dTk 1 gk

dTk 1 gk

1

kgk 1 k2

1

(*)

De (4.2), (4.17) et (*) :
kdk k2 =

Posons ^ =

1+
1

kdk k2

kgk k2

T
k dk 1 gk
T
k dk 1 gk

2

kgk k2 + 2
1+
kgk k2 +
1

+
+

2
2
k kdk 1 k
2
2
k kdk 1 k

FR 2
k

kdk 1 k2

1; on aura :
^ kgk k2 +

FR 2
k
FR 2
k

^ kgk k2 +
:
k
X
4
^ kgk k
kgj k

kdk 1 k2
h
^ kgk 1 k2 +

2

j=2

4

+ ^ kgk k kg1 k

FR 2
k

2

kdk 2 k2
4

= ^ kgk k

i

k
X
j=1

kgj k

2

Supposons que gk est borné en dehors du zéro (limk!1 inf kgk k =
6 0), c’est-à-dire :
kgk k

! > 0; 8k ) kgk k

2

!

2

de (4.5) on a :
kdk k

2

^ kgk k
) kdk k

2

4

k
X

kgj k

^

k

j=1

4

4

!2

42

2

^

!2

k
X
j=1

1

3.3. LES MÉTHODES DANS LESQUELLES LE TERME kGK+1 k2 FIGURE DANS LE
NUMÉRATEUR DE K
d’où

X
k 1

1
kdk k2

!2 X 1
>1
^ 4k 1k

(**)

P
Ce qui veut dire que k 1 kd1k2 est divergente.
k
D’autre part, puisque les conditions du Théorème 4.1, et du théorème 4.2 sont satisfaites,
alors on a :
X
cos2 k kgk k2 < 1
k 1

et

c1
d’où
X

2
2 kgk k
c1
kdk k2
k 1

kgk k
kdk k

cos

k

X

kgk k2

c2

kgk k
kdk k

cos2

kgk k2 < 1

k

k 1

X kgk k4

)

k 1

kdk k2

<1

X !4
2 < 1
kd
k
k
k 1
X 1
)
2 < 1
kd
k
k
k 1
)

Ce qui contredit (**), d’où le résultat. Donc
lim inf kgk k = 0:

k!1

Remarque 3.3.1 La méthode de Fletcher-Reeves avec une recherche linéaire exacte génère des
directions de descente.
En e¤et, à chaque itération k 1, on a :
dTk+1 gk+1 =
=
=

T
FR
gk+1
k+1 dk
FR T
T
gk+1 gk+1 + k+1 dk gk+1
kgk+1 k2

gk+1 +

Puisque
k

= min f (xk + dk ) = min hk ( )
>0

>0

Donc k véri…e la condition nécessaire d’optimalité :h0k (
0; 8k 1
43

k)

= dTk rf (xk +

k dk )

= dTk gk+1 =

CHAPITRE 3. SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE

3.3.2

Méthode de descente conjuguée

Cette méthode été découverte en 1987 par Fletcher ([34]),
CD
k+1

k

est égale à :

kgk+1 k2
=
dTk gk

(CD)

La méthode de descente conjuguée CD proposée par Fletcher [34] est étroitement liée à la
. Une di¤érence
méthode Fletcher Reeves FR. Avec une recherche linéaire exacte, Fk R = CD
k
importante entre FR et CD est que, avec CD, la descente su¢ sante (2.3) est assurée pour une
recherche linéaire de Wolfe forte et la contrainte
1=2 avec FR, n’est pas nécessaire pour
la méthode CD. En outre, pour une recherche linéaire qui satisfait aux conditions de Wolfe
CD
FR
relaxée (2.22-2.23) avec 1 1 et 2 = 0, il peut être démontré que : 0
k
k .
Par conséquent, à partir de l’analyse [1] ou le théorème de Zoutendijk bis, la convergence
globale est assurée. D’autre part, si 1
1 ou 2 > 0, Dai et Yuan [22] construisent des
exemples où kdk k2 augmente de façon exponentielle et le procédé de CD converge vers un point
où le gradient ne s’annule pas. En particulier, la méthode CD peut ne pas converger vers un
point stationnaire pour une recherche linéaire de Wolfe forte .
Théorème 3.3.3 ([22]) Supposons que L’hypothèse Condition C1 soit satisfaite. Considék2
rons une méthode du type (GC1), (GC2), (GC3) avec k = CD
= kgk+1
et le pas k satisfait
k
dT
g
k k
aux conditions de (Wolfe-relaxée1) et (Wolfe-relaxée2) :
f (xk ) + dTk gk
T
dTk gk+1
2 dk gk

f (xk + k dk )
et 1 dTk gk
0
k

2

avec 0 < < 1 < 1 et
1: Alors notre méthode génère des directions de descente su¢ sante à chaque itération

1.

Preuve. On a
dTk gk

=
=
)

T
CD
gk
k dk 1
dT gk
kgk k2 1 + T k 1
dk 1 gk 1
dTk 1 gk
dTk gk
=
1
+
dTk 1 gk 1
kgk k2

gk +

D’autre part de (2.23), on a
T
1 dk gk

dTk gk+1
) 1

2

1
44

T
2 dk gk
dTk 1 gk
+ T
dk 1 gk 1

1+

1

3.3. LES MÉTHODES DANS LESQUELLES LE TERME kGK+1 k2 FIGURE DANS LE
NUMÉRATEUR DE K
d’où
1

2

dTk gk
kgk k2

1+

1

Donc si kgk k =
6 0; on a :
C kgk k2

dTk gk

où C = 1

2

>0

et donc dk est une direction de descente su¢ sante.
Théorème 3.3.4 ([22]) Supposons que L’hypothèse Condition C1 soit satisfaite. Considék2
= kgk+1
rons une méthode du type (GC1), (GC2), (GC3) avec k = CD
et le pas k satisfait
T
k
dk gk
aux conditions de (Wolfe-relaxée1) et (Wolfe-relaxée2) :
f (xk ) + dTk gk
T
dTk gk+1
2 dk gk

f (xk + k dk )
et 1 dTk gk
et 0

2

avec 0 < <
1: Alors notre méthode est globalement convergente, dans le sens suivant :
lim inf kgk k = 0

k!1

Preuve. Du théorème précédent on a :
1

2

dTk gk
1+ 1
kgk k2
dTk gk
) 1
1+ 1
kgk k2
kgk k2
1
) (1 + 1 )
dTk gk
) (1 +

1)

1

) (1 +

1)

1

)

CD
k+1

kgk+1 k2 kgk k2
dTk gk kgk+1 k2
CD
k+1
FR
k+1

FR
k+1

Donc CD
k+1 véri…e l’inégalité (4.17).
D’après le théorème 4.2 on a :
lim inf kgk k = 0

k!1

45

1

1

1

1

<1

CHAPITRE 3. SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE

3.3.3

Méthode de Dai-Yuan

Introduction
Cette méthode été découverte par Y. H. Dai et Y. Yuan ([24]) en 1996,
DY
k

=

kgk+1 k2
; yk = gk+1
dTk yk

k

est égale à :
(DY)

gk

Cette méthode est fondamentalement di¤érente de la méthode Fletcher Reeves et aussi
de la méthode CD. Avec une recherche linéaire de Wolfe standard (2.14, 2.15), la méthode
de DY génère toujours des directions de descente. En plus elle est globalement convergente
aves des hypothèses tres générales sur la fonction objectif f: On exige seulement que f soit
continueument di¤érentiable et que le gradient soit Lipschitzien, c’est à dire que f véri…e
l’hypothèse Condition C1.
Théorèmes de convergence de Dai et Yuan exigeant seulement la condition de Wolfe
et la condition de Lipschitz C1
Théorème 3.3.5 ([31]) Supposons que la condition de Lipschitz C1 soit satisfaite. Considék2
= kgdk+1
rons une méthode du type (GC1), (GC2), (GC3) où k satisfait à DY
; yk = gk+1 gk
Ty
k
k
k
et le pas k satisfait aux conditions de (Wolfe1) et (Wolfe2) suivantes :
f (xk ) + dTk gk
dTk gk

f (xk + k dk )
dTk gk+1

avec 0 < <
autrement dit :

< 1: Alors toutes les directions générées par ces méthodes sont de descente,
dTk gk < 0;

8k

(4.4)

1

Preuve. La démonstration se fait par récurrence.
1) Pour k = 1 :
dT1 g1 = kg1 k2 < 0
2) Supposons que (4.16) est satisfaite pour k > 1 et démontrons qu’elle le sera pour k + 1 :
Supposons que :
dTk gk < 0; k > 1
En utilisant (4.7), on aura :
dTk yk = dTk (gk+1

gk ) > dTk (gk+1

gk ) = (
46

1) dTk gk =

(1

) dTk gk > 0

3.3. LES MÉTHODES DANS LESQUELLES LE TERME kGK+1 k2 FIGURE DANS LE
NUMÉRATEUR DE K
D’autre part :
dTk+1 gk+1 =
=
=
=
=
=

T
DY
gk+1
k+1 dk
2
DY T
kgk+1 k + k+1 dk gk+1
kgk+1 k2 T
kgk+1 k2 + T
d gk+1
dk yk k
kgk+1 k2 T
2
kgk+1 k + T
d (yk +
dk yk k

gk+1 +

gk )

kgk+1 k2 T
kgk+1 k + kgk+1 k + T
d gk
dk yk k
2

2

kgk+1 k2 T
d gk
dTk yk k

or puisque :dTk gk < 0; dTk yk > 0; il en résulte :
dTk+1 gk+1 < 0
Ce qui achève la démonstration.
Théorème 3.3.6 ([24]) Supposons que la condition de Lipschitz C1 soit satisfaite. Considék2
rons une méthode du type (GC1), (GC2), (GC3) où k satisfait à DY
= kgdk+1
; yk = gk+1 gk
Ty
k
k k
et le pas k satisfait aux conditions de (Wolfe1) et (Wolfe2) suivantes :
f (xk ) + dTk gk
dTk gk

f (xk + k dk )
dTk gk+1
avec 0 <
ment i.e.

<

< 1. La suite fxk g générée par l’algorithme de Dai-Yuan converge globalelim inf kgk k = 0

k!1

Preuve. En utilisant le théorème précédent, on aura :
X
k 1

cos2 kgk k2 < 1

(*)

d’autre part on a :
kdk+1 + gk+1 k2 =

2
DY
k+1 dk

) kdk+1 k2 =

DY 2
k+1

47

kdk k2

2dTk+1 gk+1

kgk+1 k2

(**)

CHAPITRE 3. SYNTHESE DES RESULTATS DE CONVERGENCE DES METHODES
DU GRADIENT CONJUGUE NON QUADRATIQUE
De (4.16) :
dTk+1 gk+1 =

gk+1 +

T
DY
k+1 dk

gk+1

2

kgk+1 k T
d gk =
dTk yk k
dTk+1 gk+1
=
) DY
k+1
dTk gk
=

DY T
k+1 dk gk

remplaçant ceci dans (**), on aura :
kdk+1 k2

dTk+1 gk+1

2

=

kdk k2

kgk+1 k2

2dTk+1 gk+1

2

2

2

dTk+1 gk+1
dTk+1 gk+1
dTk+1 gk+1
"
#
kdk k2
1
1
kgk+1 k2
1
=
2 +2 T
2 +
T
T
(dk gk )
dk+1 gk+1
kgk+1 k
kgk+1 k2
dk+1 gk+1
=

d’où

DY 2
k+1

kdk k2
(dTk gk )

1
kgk+1 k

kgk+1 k
dTk+1 gk+1

+

2

+

1
kdk k2
+
T
(dk gk ) kgk+1 k2
kdk k2

1
kgk+1 k2

1
kdk 1 k2
+ T
dk 1 gk 1
kgk k2

2

(dTk gk )

1
1
kdk 2 k2
+
+ T
dk 2 gk 2
kgk k2 kgk 1 k2
:
k
X
1
i=1

kgi k2

Supposons maintenant que (4.18) n’est pas satisfaite, autrement dit :
9! > 0 tel que kgk k > !; 8k
On aura :
kdk k2

2

(dTk gk )

)
d’où

k
1 X
1
1 = 2k
2
! i=1
!

1
kgi k2

X dTk gk
k 1

kdk k2

X dTk gk
k 1

2

kdk k2

2

=1

ce qui contredit (*): Ceci achève la démonstration.
48

!2

X1
k 1

k

3.3. LES MÉTHODES DANS LESQUELLES LE TERME kGK+1 k2 FIGURE DANS LE
NUMÉRATEUR DE K
Résultat de Dai et Yuan sur la descente su¢ sante
Dans [16], Dai a analysé la méthode de DY de façon plus approfondie. Le résultat suivant
donne des conditions su¢ santes pour obtenir des directions de descente su¢ santes.
Théorème 3.3.7 ([22]) Considérons une méthode du type (GC1), (GC2), (GC3) avec k =
DY
k . Si la méthode de DY est mise en œuvre avec une recherche linéaire quelconque garantissant
que les directions de recherche soient des directions de descente, et s’ il existe des constantes
kgk k
0, alors pour tout p 2]0; 1[, il existe une
1 et 2 telles que 1
2 pour tous k
constante c > 0 telle que la condition de descente su¢ sante suivante
c kgi k2

giT di

soit assurée pour au moins [pk] indices, i 2 [0; k], [r] désigne le plus grand entier inférieur ou
égal à r.

3.3.4

Méthode de Dai-Yuan généralisée

Dans le procédé de l’analyse de la méthode de DY, Dai et Yuan ont généralisé leurs résultats
pour toutes les méthodes du gradient conjugué où k peut se mettre sous la forme suivante :
k

=

Le procédé de FR correspond au choix
sous la forme :
DY
k

DY G
k

k

=

=

k+1

(DYG)

k

= kgk k2 . En utilisant (1.3),

DY
k

peut être réécrit

T
gk+1
dk+1
T
gk dk

Par conséquent, le procédé de DY a la forme (DYG) avec
été établi par Dai et Yuan dans [29, 31] :

k

= gkT dk : Le résultat suivant a

Théorème 3.3.8 ([36]) Considérons une méthode du type (GC1), (GC2), (GC3) avec k =
DY G
= k+1
; dk est une direction de descente pour tout k: Supposons aussi que L’hypothèse
k
k
2
P
(gkT dk )
Condition C1 soit satisfaite. Si la relation de Zoutendijk ( 1
< 1) est véri…ée et si
2
k=0 kdk k
l’une des trois relations suivantes
1
P
gkT dk

k=0

2
k

2

= 1 ou

1 kg k2
P
k

k=0

2
k

= 1 ou

1 Q
k
P

k=1 i=1

a lieu, alors la suite générée est globalement convergente, i.e.,
lim inf kgk k = 0:

k!1

49

2
i

=1


Documents similaires


Fichier PDF gradient conjugue cas quadratique et non quadratique
Fichier PDF professeur benzine rachid optimisation sans contraintes tome1
Fichier PDF professeur benzine rachid cours optimisation sans contraintes tome1
Fichier PDF 14 problemes ouverts sur le gradient conjugue sujets de theses de doctorat
Fichier PDF convergence et vitesse convergence methode du gradient
Fichier PDF convergence et vitesse de convergence de la methode du gradient professeur benzine rachid


Sur le même sujet..