METHODES QUASI NEWTON .pdf



Nom original: METHODES QUASI-NEWTON.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 15/05/2016 à 23:05, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 1250 fois.
Taille du document: 287 Ko (25 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)










Aperçu du document


OPTIMISATION SANS CONTRAINTES
TOME 3 METHODES QUASI-NEWTON.
METHODES DFP ET BFGS.
ALGORITHMES ET ETUDE DE LA
CONVERGENCE

*********************
PROFESSEUR BENZINE RACHID
15 mai 2016

Table des matières
1 Méthodes Quasi-Newton
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Dérivation des méthodes . . . . . . . . . . . . . . . . .
1.3 Méthode de Correction de rang un . . . . . . . . . . .
1.3.1 Algorithme . . . . . . . . . . . . . . . . . . . .
1.3.2 Avantages . . . . . . . . . . . . . . . . . . . . .
1.3.3 Inconvénients . . . . . . . . . . . . . . . . . . .
1.4 Méthode de Davidon-Fletcher-Powell (D.F.P) . . . . .
1.4.1 Algorithme DFP . . . . . . . . . . . . . . . . .
1.4.2 Avantages et inconvénients de la méthode DFP
1.5 Méthode BFGS
. . . . . . . . . . . . . . . . . . .
1.6 Convergence des méthodes quasi-newton . . . . . . . .
1.6.1 Cas où la recherche linéaire est exacte . . . . . .
1.6.2 Cas où la recherche linéaire est inéxacte . . . .

2

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

3
3
3
4
5
7
7
7
8
12
12
15
15
16

Chapitre 1
Méthodes Quasi-Newton
1.1

Introduction

Ce chapitre est consacré aux méthodes dites Quasi-Newton pour la résolution des problèmes
d’optimisation non linéaires sans contraintes. Parmi ces méthodes, on s’étalera particulièrement
sur les trois plus importantes, la méthode de correction de rang un, la méthode DF P (Davidon,
Fletcher, Powell) et la méthode BF GS (Broyden, Fletcher, Goldfarb, Shano):

1.2

Dérivation des méthodes

Ces méthodes s’inspirent de l’algorithme de N ewton, mais sans calculer la matrice hessienne
de f; ni son inverse. L’itération de la méthode de Newton étant dé…nie par :
xk+1 = xk

H

1

(xk )rf (xk );

l’idée est de remplacer cette itération par :
k Sk rf (xk ) ;

xk+1 = xk

où k est un paramètre fourni par une recherche linéaire le long de la directon dk = Sk rf (xk ) ; Sk
est une approximation symétrique, dé…nie positive, de H 1 (xk ): Bien sur, plus Sk sera proche
de H 1 (xk ); plus l’algorithme convergera rapidement. L’objectif, est donc de trouver une bonne
suite de matrices Sk , faciles à construire, c’est à dire utilisant des informations seulement sur
le gradient et qui converge vite vers des approximations de plus en plus précises, de l’inverse
du hessien de f .
Pour réaliser celà, prenons f 2 C 2 ( Rn ); et faisons un dévelopement de rf (x) au voisinage
de xk ;
rf (x) = rf (xk ) + H(xk )(x xk ) + o(kx xk k)
c.à.d
rf (x) ' rf (xk ) + H(xk )(x
3

xk );

x 2 V (xk );

CHAPITRE 1. MÉTHODES QUASI-NEWTON
ou encore
H

1

(xk ) [rf (x)

rf (xk )] ' (x

xk ):

Les approximations sont exactes si f est quadratique. En particulier, avec x = xk+1 et si Sk
était une bonne aproximation de H 1 (xk ), on devrait avoir
rf (xk )] ' (xk+1

Sk [rf (xk+1 )

xk );

(4.1)

mais comme xk+1 est calculé aprés Sk , il est peu probable que cette équation soit satisfaite,
même approximativement. En revanche, on peut toujours imposer que Sk+1 satisfasse cette
équation exactement, d’où
Sk+1 [rf (xk+1 )

rf (xk )] = (xk+1

xk )

(4.2)

cette équation est dite“ équation de la secante”ou “condition "quasi N ewton":
A l’étape k, la remise à jour de la matrice Sk se fait avec une formule simple,
Sk+1 = Sk + Ck ;
Ck étant une matrice de correction qui intègre au mieux la nouvelle information fournie par
xk+1 et rf (xk+1 ) de telle manière que Sk+1 satisfasse la condition (4:2) : Basées sur ce principe,
les méthodes quasi N ewton di¤èrent l’une par rapport à l’autre, d’aprés la dé…nition de la
matrice Ck
Commençons par la méthode de correction de rang un qui est considérée comme une introduction élémentaire aux deux autres méthodes (DF P et BF GS) décrites par la suite.

1.3

Méthode de Correction de rang un

Etand donné que H 1 (xk ) est symétrique, il est naturel de construire des approximations
successives Sk symétriques. Par exemple, on peut exprimer Sk+1 en fonction de Sk de façon trés
simple, en rajoutant à cette derniere une matrice de rang un de la forme suivante : ak uk utk ; où
uk est un vecteur de Rn et ak est une constante. On obtiendra alors :
Sk+1 = Sk + ak uk utk :
Montrons qu’il est facile de calculer ak et uk de telle sorte que la condition (4.2) soit satisfaite.
Posons
pk = xk+1 xk
qk = rf (xk+1 )

rf (xk )

la condition (4.2 ) s’écrit donc
Sk+1 qk = pk
Soit en remplaçant par l’expression de Sk+1 ;
(Sk + ak uk utk )qk = pk ;
4

1.3. MÉTHODE DE CORRECTION DE RANG UN
ou encore :
ak uk (utk qk ) = pk

Sk qk

d’ou l’on déduit que uk est proportionnel à pk Sk qk ; avec un facteur qui peut être pris en
compte dans ak : En particulier en prenant uk = pk Sk qk et ak tel que ak (utk qk ) = 1, on obtient :
Sk+1 = Sk +

1.3.1

(pk

Sk qk )(pk Sk qk )t
(pk Sk qk )t qk

Algorithme

Etape initiale :Soit ">0, determinant le critère d’arret. Choisir un point initial x1 et une
matrice symétrique dé…nie positive S1 : Poser y1 = x1 ; k = 1; et aller aux étapes principales.
Etapes principales :
Etape1 : Si krf (yk )k < ": stop ; sinon, poser dk = Sk rf (xk ) et soit k la solution optimale
du problème min f (yk + dk ) ,
0:
Etape2 :. Construire Sk+1 comme suit :
Sk+1 = Sk +

(pk

Sk qk )(pk Sk qk )t
;
(pk Sk qk )t qk

avec
pk = k dk yk+1 yk ;
qk = rf (yk+1 ) rf (yk );
remplacer k par k + 1; et répeter l’étape 1.
Il est utile de citer le théorème suivant qui montre que lorsque H est constante, la condition
(4.2) est non seulement véri…ée pour i = k; mais aussi pour tout i < k; et que dans ce cas la
convergence est obtenue dans au plus n étapes.
Théorème 4.1 :
Si f est quadratique, de matrice hessienne H dé…nie positive et si p1 ; :::; pn sont des vecteurs
indépendants, alors la méthode de correction de rang un converge au plus dans (n+1) itérations
et (Sn+1 ) 1 = H:
Preuve
La preuve se fait par recurrence. Montrons tout d’abord que :
pour i

pi = Sk+1 qi ;

k

pour k = 1 elle est évidente d’aprés la dé…nition de S2 :
Supposons qu’elle est vraie pour k > 1 et montrons qu’elle vraie pour k + 1: On a donc
S k qi = p i

8i
5

k

1:

(4.3)

CHAPITRE 1. MÉTHODES QUASI-NEWTON
Pour éxploiter la dé…nition de Sk+1 ; calculons
(pk

Sk qk )t qi = ptk qi

qkt Sk qi = ptk qi

qkt pi :

(4.4)

ptk qi = 0:

(4.5)

En remarquant que qk = Hpk ; on obtient :
(pk

Sk qk )t qi = ptk qi

ptk Hpi = ptk qi

Donc
Sk+1 qi = Sk qi + 0 = pi ;

8i

k

1:

Reste le cas i = k: La relation est vraie d’aprés la condition ( 4.2 ). Ce qui établit le resultat
voulu au rang k + 1:
Pour terminer la preuve du théorème et puisque on a,
pi = Sn+1 qi = Sn+1 Hpi ;

(4.6)

i = 1; :::; n

et comme les vecteurs pi sont indépendents, alors,
Sn+1 H = I ou encore, Sn+1 = H 1

Exemple 4.1 :
Considérons le problème suivant :
(P 1)

(

1 t
x Qx
2n
x2R

min


0

1
B 0
Q=B
@ 1
2

0
3
1
1

1
1
2
0

1
2
1 C
C
0 A
1

Appliquons la méthode de correction de rang un sur cet exemple, en prenant " = 10 5 et
y0 = (0; 1; 2; 3): Les resultats obtenues sont illustrés au tableau 4.1, et la recherche linéaire
considérée est exacte.
tableau 4.1
iteration
xk
f (xk ) krf (xk )k
1
(0:000; 1:000; 2:000; 3:000)
15.000
13.000
2
( 2:005; 1:005; 0:746; 1:997) 6.187
4.357
3
(0:665; 0:548; 0:004; 0:113)
0.766
0.196
4
(0:000; 0:001; 0:004; 0:002) 0.002
0.087
5
(0:000; 0:000; 0:000; 0:000)
0.000
0.000

6

k

0.250
0.842
0.444
0.003


1.4. MÉTHODE DE DAVIDON-FLETCHER-POWELL (D.F.P)
Les matrices Sk obtenues à chaque itération sont :

S1

S3

0

1:000 0:000 0:000 0:000
B 0:000 1:000 0:000 0:000
= B
@ 0:000 0:000 1:000 0:000
0:000 0:000 0:000 1:000
0
0:228
0:495
0:129
B 0:495
0:549
0:101
= B
@ 0:129
0:101
0:722
0:578
0:103
0:469

1

0

C
C;
A

B
S2 = B
@

1
0
0:578
B
0:103 C
C ; S4 = B
@
0:469 A
0:002

0:927
0:140
0:117
0:134
0:129
0:213
0:160
0:485

0:140
0:730
0:226
0:259
0:213
0:328
0:126
0:176

0:117
0:226
0:809
0:217
0:160
0:126
0:719
0:461

D’aprés le tableau, on voit bien que le minimum de f est atteint en 4 itérations.

1.3.2

1
0:134
0:259 C
C
0:217 A
0:751

1
0:485
0:176 C
C
0:461 A
0:002

Avantages

Cette méthode présente l’avantage que le point xk+1 n’a pas besoin d’être choisi comme le
minimum exact, c’est à dire qu’on n’a pas besoin d’e¤ectuer des recherches linéaires exactes.

1.3.3

Inconvénients

Les inconvénients de cette méthode sont :
1. Même si la fonction est quadratique, et même si son hessien est dé…ni positif, il se peut que
la matrice Sk ne soit pas dé…nie positive.
2. Le dénominateur (pk Sk qk )t pk peut trés bien devenir nul ou trés petit, rendant le procédé
instable.
Dans ce qui suit, on présente les méthodes quasi-Newton, basées sur des formules de correction de rang 2 ( DFP, BFGS ), qui evitent ces inconvénients.

1.4

Méthode de Davidon-Fletcher-Powell (D.F.P)

Cette méthode a été proposée par Davidon en 1959 ([30]) et développée plus tard en 1963
par Fletcher & Powell ([31]). C’est une méthode assez remarquable pour plusieurs raisons. Tout
d’abord, quand elle est appliquée à une fonction quadratique, non seulement les di¤érentes itérations aboutissent à l’inverse du hessien, mais en plus elle engendrent des directions conjuguées.
La mise à jour de Sk+1 en fonction de Sk se fait en ajoutant cette fois deux matrices de rang
un, d’où le nom “correction de rang deux”. De façon plus précise construisons Sk+1 en fonction
de Sk , de la forme :
Sk+1 = Sk + Ak + Bk ;
avec Ak et Bk deux matrices de rang un chacune et de la forme suivante :
Ak = ak uk utk ;

Bk = bk vk vkt ;
7

CHAPITRE 1. MÉTHODES QUASI-NEWTON
ak ; bk sont des constantes, uk ; vk sont deux vecteurs de Rn : Sk+1 doit satisfaire la condition
(4.2), c’est à dire :
(Sk + ak uk utk + bk vk vkt )qk = pk
Sk qk + ak uk utk qk + bk vk vkt qk = pk
ak uk utk qk + bk vk vkt qk = pk

Sk qk

un choix évident pour satisfaire l’équation est de prendre uk = pk ; vk = Sk qk ; ak utk qk = 1 et
bk vkt qk = 1; d’où :
pk ptk Sk qk qkt Sk
DF P
Sk+1
= Sk +
(4.7)
pk qkt
qkt Sk qk
Remarque 4.1 :
Il y’a aussi une formule DFP, pour approcher le hessien lui même, au lieu de son inverse. Cette
formule est donnée par :
DF P
Bk+1
= Bk + 1 +

ptk Bk pk qk qkt
ptk qk
ptk qk

qk ptk Bk + Bk pk qkt
ptk qk

La prodédure est la même que celle de correction de rang un, mais en général il est recommandable d’implémenter les méthodes quasi-Newton avec une reinitialisation periodique pour
des raisons de convergence.
L’algorithme suivant est donné sous cette forme.

1.4.1

Algorithme DFP

Etape initiale : Soit " un scalaire d’arret, choisir un point initial x1 et une matrice symétrique
dé…nie positive S1 : Poser y1 = x1 ; k = j = 1; et aller aux étapes principales.
Etapes principales.
Etape1 : Si krf (yj )k < ": stop ; sinon, poser dj = Sj rf (yj ) et soit j la solution optimale
du problème
min f (yj + dj ) telque
0: Soit yj+1 = yj + j dj :
.Si j < n aller à l’étape 2
.Si j = n, poser y1 = xk+1 = yn+1 ; remplacer k par k + 1; poser j = 1 et aller à
l’étape 1.
Etape2 : Construire Sj+1 comme suit :
Sj+1

pj ptj
= Sj +
pj qjt

Sj qj qjt Sj
qjt Sj qj

avec
pj = j dj yj+1 yj ;
qj = rf (yj+1 ) rf (yj );
8

1.4. MÉTHODE DE DAVIDON-FLETCHER-POWELL (D.F.P)

remplacer j par j + 1; et répéter l’étape 1.
Dé…nition 4.1 :
Soit H une matrice ( n n) symétrique. Les vecteurs d1 ; :::; dn sont dits H conjugués s’ ils
sont linéairement indépendents et si dti Hdj = 0 pour i 6= j
Lemme 4.1 ([11])
Si H est symétrique dé…nie positive, et si les vecteurs non nuls d1 ; :::; dn sont H conjuguées,
alors ils forment une famille libre.
Théorème 4.2.
Considérons la méthode DFP décrite par la relation :
DF P
= Sk +
Sk+1

pk ptk
pk qkt

Sk qk qkt Sk
qkt Sk qk

1. A l’étape k, si Sk est symétrique dé…nie positive et si la recherche linéaire est exacte ( ou
bien si pk qkt > 0 ), alors la matrice Sk+1 est symétrique dé…nie positive aussi.
2. Si f est quadratique de hessien H, avec en plus H dé…nie positive, alors la méthode DFP
véri…e :
(i) pti Hpj = 0
1 i<j k
(ii) Sk+1 Hpi = pi
1 i k
3. Ces propriétés impliquent, dans le cas quadratique, la convergence de la méthode en n itérations et la propriété Sn+1 = H 1 :
Preuve :
1. Il est évident d’aprés la dé…nition de Sk+1 qu’elle est symétrique, montrons qu’elle est dé…nie
positive. Soit x un vecteur de Rn non nul,
pk ptk
x
ptk qk
(xt pk )2
= x t Sk x + t
p k qk
(xt pk )2
= x t Sk x + t
p k qk

xt Sk+1 x = xt Sk x + xt

Le terme (xt Sk x)(qkt Sk qk )

Sk qk qkt Sk
x
qkt Sk qk
(xt Sk qk )2
qkt Sk qk
(xt Sk qk )2
qkt Sk qk
xt

(xt Sk qk )2 est positif d’aprés Cauchy Shwartz. En e¤et, comme Sk
1

1

1

est dé…nie positive, alors il existe une matrice Sk2 dé…nie positive telleque Sk = Sk2 : Sk2 :
1

1

Posons a = Sk2 x et b = Sk2 qk , d’où
xt Sk x = at a; qkt Sk qk = bt b; etxt Sk qk = at b;
donc
(xt Sk x)(qkt Sk qk )

(xt Sk qk )2 = (at a)(bt b)
9

(at b)2

0:

CHAPITRE 1. MÉTHODES QUASI-NEWTON
Donc pour prouver que xt Sk+1 x > 0; il su¢ t de montrer que ptk qk > 0 et que qkt Sk qk > 0:
ptk qk =

t
k dk

[rf (yk+1 )

t
k dk rf (yk )

rf (yk )] =

Puisque yk+1 est le minimum le long de la direction dk et rf (yk ) 6= 0; (d’aprés l’hypothèse)
donc,
ptk qk = k rf (yk )Sk rf (yk ) > 0:
De plus qk 6= 0; d’où xt Sk x > 0:
Supposons que
(at a)(bt b) = (at b)2
:::( )
t
x pk = 0
:::( )

x t Sk x = 0 ,

( ) , a=
1

, Sk2 x = b
) x = qk
x =
6
0 ) 6= 0
( ) , ptk x = 0
) ptk qk = 0
contradiction avec le fait que ptk qk > 0:
2. On démontre ce point par récurence pour tout 1
Pour k = 1 :
(ii) Notons tout d’abord que pour tout i :
Hpi = H(yi+1

k

yi ) = rf (yi+1 )

n

rf ( yi ) = qi ;

en particulier Hp1 = q1 .
S2 Hp1 = S1 q1 +

p1 pt1
p1 q1t

S1 q1 q1t S1
q1t S1 q1

q1 = S 1 q1

S 1 q1 + p 1 = p 1 :

Supposons maintenant que (i), (ii) sont vraies pour k-1, et prouvons qu’elles le sont pour k. On
a:
rf (yk ) = rf (yi+1 ) + H(yk yi+1 ) = rf (yi+1 ) + H(pi+1 + ::: + pk 1 ):
Multiplions par pti ;

pti rf (yk ) = pti rf (yi+1 ) + pti H(pi+1 + ::: + pk 1 );
d’aprés l’hypothèse de reccurence pour (i) et le fait que yi+1 est le minimum de f suivant la
direction pti ; on a
pti rf (yk ) = 0;
81 i < k;
10

1.4. MÉTHODE DE DAVIDON-FLETCHER-POWELL (D.F.P)
d’aprés l’hypothèse de reccurence pour (ii), pi = Sk Hpi ;

0

i

k: D’où

pti HSk rf (yk ) = 0;
et et comme
k Sk rf (yk );

p=
on obtient :

pti Hpk = 0;
d’ou (i) est vraie pour k.
Maintenant d’aprés (ii) pour k

et

k

6= 0;

pour i < k

(4.8)

1, Hpk = qk ; et d’après (4.8) on trouve :

qkt Sk Hpi = qkt pi = ptk Hpi = 0;
1 i<k
Sk+1 Hpi = Sk Hpi = pi ;
1 i < k;
pour i = k on a, Sk+1 Hpk = Sk qk = pk ; d’où (ii) est vraie pour k:
3. La méthode engendre des directions conjuguées, d’aprés le point 2. De plus, les
directions p1 ; :::; pk sont des vecteurs propres (associés à la valeur propre 1) de la matrice
Sn+1 H: Elles forment une famille libre, puisque ces vecteurs sont des directions conjuguées.
Notons P la matrice telle que ses colonnes sont ces directions, alors P est inversible et d’après
(ii)
Sn+1 HP = P ) Sn+1 H = I ) Sn+1 = H 1 :
Exemple 4.2 :
Considérons le même problème que l’exemple 4.1 et appliquant la méthode DFP, on trouve les
resultats suivants
tableau 4.2
iteration
xk
f (xk ) krf (xk )k
1
(0:000; 1:000; 2:000; 3:000)
15.000
13.000
2
( 2:005; 1:005; 0:746; 1:997) 6.187
4.357
3
(0:665; 0:548; 0:004; 0:113)
0.766
1.969
4
(0:000; 0:001; 0:004; 0:002) 0.002
0.087
5
(0:000; 0:000; 0:000; 0:000)
0.000
0.000

k

0.250
0.812
0.483
0.602


Les matrices Sk obtenues à chaque itération sont :

S1

S3

0

1:000 0:000 0:000 0:000
B 0:000 1:000 0:000 0:000
= B
@ 0:000 0:000 1:000 0:000
0:000 0:000 0:000 1:000
0
0:176
0:495
0:129
B 0:453
0:515
0:101
= B
@ 0:129
0:101
0:722
0:567
0:112
0:469

1

0

C
C;
A

B
S2 = B
@

1
0
0:567
B
0:112 C
C ; S4 = B
@
0:469 A
0:002
11

0:947
0:140
0:123
0:149
0:129
0:213
0:160
0:485

0:136
0:730
0:227
0:261
0:213
0:328
0:126
0:176

0:117
0:227
0:811
0:213
0:160
0:126
0:720
0:462

1
0:134
0:261 C
C
0:213 A
0:761
1
0:485
0:176 C
C
0:462 A
0:002

CHAPITRE 1. MÉTHODES QUASI-NEWTON

1.4.2

Avantages et inconvénients de la méthode DFP

Avantages
1.Pour des fonctions quadratique (avec une recherche linéaire exacte)
(i) elle termine au plus en n étapes avec Sn+1 = H 1
(ii) Elle engendre des directions conjuguées.
2.Pour des fonctions quelconques :
(iii) Les matrices Sk restent dé…nies positives. Ceci entraine que les propriétes de descente
de la fonction sont véri…ées..
(iv) une convergence superlinéaire
Inconvénients
Cette méthode est assez sensible à la précision de la recherche linéaire (la convergence dépend
du fait que la recherche linéaire est exacte ou non).

1.5

Méthode BFGS

Cette méthode a été développée de façon indépendente par Broyden ([34],1970), Fletcher
([33],1970), Goldfarb ([35],1970) et Shanno ([36],1969). Pour construire une approximation de
l’inverse du hessien, elle utilise une formule de correction de rang deux qui dérive directement
de la formule (4.7). Plus précisement :
Sk+1 = Sk +

qkt Sk qk pk ptk
pk ptk
+
ptk qk
(pk qkt )2

pk qkt Sk + Sk qk ptk
:
ptk qk

(4.9)

Cette formule est moins sensible aux erreurs dans les recherches linéaire, et elle est considérée
comme la meilleure actuellement. On peut se demander ce qui justi…e l’introduction d’une telle
formule. Une des réponses est que si l’on note Bk = (Sk ) 1 , c.à.d, Bk approxime Hk et non pas
son inverse.
la condition quasi-Newton (voir formule 4.2) sera dans ce cas :
Bk+1 pk = qk ;

(4.10)

qk qkt
qkt pk

(4.11)

et
Bk+1 = Bk +

Bk pk ptk B
:
ptk Bpk

Comme l’a remarqué Fletcher ([33]), si l’on interverti les rôles de pk et de qk dans (4:7), on
obtient les matrices veri…ant (4:10), qui est la relation inverse de (4:9). On voit alors que la
formule (4:11) permet de construire une approximation de la matrice hessienne elle même (et
non pas son inverse). Posons
qk q t
Bk pk ptk B
Ck = t k
;
qk p k
ptk Bpk
12

1.5. MÉTHODE BFGS
d’aprés la relation :
1
Sk+1 = Sk + Ck = Bk+1
= (Bk + Ck ) 1 ;

et par application de la formule de Sherman
(A + at b)
où A est une matrice (n

1

Morrison

=A

1

(4.12)

woodbury suivante :

A 1 abt A 1
;
1 + bt A 1 a

(4.13)

n), b est un vecteur de Rn ; et en supposant que
(1 + bt A 1 a) 6= 0;

on obtient :
[Bk+1 ]

1

"

q t [Bk ] 1 qk
= [Bk ] 1 + 1 + k t
p k qk

#

pk ptk
ptk qk

pk qkt [Bk ]

1

+ [Bk ]
t
p k qk

1

qk ptk

:

Ce qui montre que [Bk+1 ] 1 est exiprimé directement en fonction de [Bk ] 1 et d’où la formule
de correction de rang (4:9).
Remarques importantes :
1. La formule (4.9) à des propriétés analogues à celles de la formule (4.7). En particulier :
(i) Si ptk qk > 0; alors la dé…nie positivité des matrices Sk est préservée.
(ii) Appliquée à une fonction quadratique (matrice hessienne H dé…nie positive), cette formule permet d’obtenir en au plus n itérations, l’inverse H 1 du hessien de f . De plus les directions pk engendrées par l’algorithme BFGS sont mutuellement conjuguées par rapport à
H.
2. Lorsque l’algorithme BFGS ou DFP est appliqué à une fonction non linéaire quelconque (non
quadratique), il faut procéder à des réinitialisations périodiques, pour assurer la convergence
globale.
3. Théoriquement, la condition ptk qk > 0 assure la dé…nie positivité des matrices Sk+1 ou Bk+1 ,
mais sur le plan pratique rien n’est garanti, à cause des erreurs d’arrondi, Sk+1 ou Bk+1 peuvent
devenir singulières ou non dé…nies.
4. La majorité des auteurs a¢ rme la superiorité de l’algorithme BFGS sur celui de DFP, soit
sur le plan théorique ou pratique ( il est plus stable ).
Exemple 4.3 :
Si on considère le même exemple traité par DFP et la méthode de correction de rang un
pour illustrer la remarque1(ii), on trouve les resultats si dessous :
tableau 4.3
iteration
xk
f (xk ) krf (xk )k
1
(0:000; 1:000; 2:000; 3:000)
15.000
13.000
2
( 2:005; 1:005; 0:746; 1:997) 6.187
4.357
3
(0:665; 0:548; 0:004; 0:113)
0.766
0.196
4
(0:000; 0:001; 0:004; 0:002) 0.002
0.087
5
(0:000; 0:000; 0:000; 0:000)
0.000
0.000

13

k

0.250
0.732
0.393
0.601


CHAPITRE 1. MÉTHODES QUASI-NEWTON
et les matrices Sk obtenues à chaque itération sont :

S1

S3

0

1:000 0:000 0:000 0:000
B 0:000 1:000 0:000 0:000
= B
@ 0:000 0:000 1:000 0:000
0:000 0:000 0:000 1:000
0
0:309
0:561
0:129
B 0:561
0:603
0:101
= B
@ 0:129
0:101
0:722
0:595
0:008
0:469

1

C
C;
A

0

B
S2 = B
@

1:017
0:124
0:141
0:198

1
0
0:595
B
0:008 C
C ; S4 = B
A
@
0:469
0:002

0:124
0:732
0:230
0:270

0:129
0:213
0:160
0:485

0:141
0:230
0:815
0:200

0:213
0:328
0:126
0:176

0:160
0:126
0:722
0:463

1
0:196
0:270 C
C
0:200 A
0:796
1
0:485
0:176 C
C
0:463 A
0:006

Implémentation numérique.
On a mis en oeuvre les méthodes quasi-Newton ( DFP et BFGS ) dé…nies précédement, et
comme fonction test on a pris la fonction de Rosenbrock généralisée, dé…nie par :
nP1
f (x) =
[100(xi+1 x2i )2 + (1 xi )2 ]
i=1

Comme point de départ on prend x0 = ( 1:2; 1; :::; 1:2; 1)t
Notons que le minimum de cette fonction est atteint au point x = (1; 1; :::; 1)t avec f (x ) = 0
On a implémenté l’algorithme ( DFP et BFGS ) dans le cas continu et dans le cas avec
reinitialisation en introduisant la recherche linéaire de Wolf ( chapitre 2 ).
On a pris une précision " = 10 5 et S0 = I:
Les resultats obtenus sont présentés dans les tableaux si dessous.

tableau 4.4 : DFP et
n
DF P
k
2
95
4
119
10
1160
30 pas de convergence

n
2
4
10
30

BFGS implémentés sans reinitialisation

f (x)
3:75 10
5:69 10
2:08 10
-

15
15
13

BF GS
k
25
37
68
163

f (x)
3:54 10
1:12 10
1:09 10
3:30 10

18
15
14
16

tableau 4.4 : DFP et BFGS implémentés avec reinitialisation
DF P
BF GS
k
f (x)
k
f (x)
11
55
4:65 10
45
1:04 10
11
99
1:03 10
69
7:95 10
193
1:18 10 12
182
0:39
13
572
1:44 10
186
3:30 10
14

11
14

16

1.6. CONVERGENCE DES MÉTHODES QUASI-NEWTON
on a aussi implémenté ( DFP et BFGS ) avec la procedure d’Armijo (voir chap2, recherches
linéaires inéxactes). Les resultats sont illustrés dans les tableaux si dessous :

tableau 4.5 : DFP et BFGS implémentés sans
n
DF P
k
f (x)
k
16
2 37
7:34 10
30
15
4 77
3:52 10
34
10 121
3:98
59
50 pas de convergence 262
tableau 4.6 :
n
k
2 37
4 52
10 161
50 936

reinitialisation

BF GS
f (x)
2:19 10
2:18 10
3:98
2:36 10

17
16

14

DFP et BFGS implémentés avec reinitialisation

DF P
f (x)
3:14 10
4:84 10
3:98
3:98

11
10

BF GS
k
f (x)
31 2:33 10
57 1:49 10
180 3:9
852 3:33 10

13
15

14

la valeur 3:98 correspond à un minimum local de f , x = ( 1; 1; :::; 1) souvent rencontré
avec n = 10:
D’aprés ces tests on con…rme deux points essentiels notés dans les remarques précédentes :
1. La superiorité et la stabilité de l’algorithme BFGS sur celui de DFP .
2. L’utilité de la reinitialisation, comme le montre le cas n = 30; avec Wolf et n = 50 avec
Armijo.
On a aussi implémenté ces méthodes avec d’autres fonctions tests et les resultats sont
représentés dans l’annexe à la …n de ce mémoire.

1.6
1.6.1

Convergence des méthodes quasi-newton
Cas où la recherche linéaire est exacte

Dans ce cas, le théorème (4.2) montre que si f est une fonction quadratique, de hessien
dé…ni positif, la convergence se fait dans un nombre …ni ditérations.
Dans le cas géneral et en 1972 Powell ([37]) a montré que si f était convexe, deux fois
continuement di¤érentiable, alors la méthode DF P converge globalement vers la solution optimale. Sous des conditions plus fortes que celles que nous venons de citer, le même auteur ([26])
démontra que la méthode DFP convergeait vers la solution optimale de façon superlinéaire.
15

CHAPITRE 1. MÉTHODES QUASI-NEWTON
Maitenant on va prouver la convergence des méthodes quasi-Newton en utilisant le théorème1.6 (Voir Chap.1, Fonctions mutivoques et Algorithmes). Pour celà on note par A notre
algorithme tel que A = CB où A et B sont décris par la suite. Alors on doit véri…er les propriétés
suivantes :
1:B est fermé sur C = Rn n
2: Si y 2 B(x) ) f (y) f (x)
8x 2
= :
3: Si z 2 C(y) ) f (z) f (y):
4: L’ensemble = fx : f (x) f (x0 )g est compact, où x0 est le point de départ.
Pour les méthodes quasi-Newton, B est dé…nie comme suit :
donnons un point x, alors y 2 B(x) si y est obtenu en minimusant f à partir de x le long de la
direction d = S0 rf (x), où S0 est une matrice arbitraire dé…nie positive. De plus en démarrant
du point obtenu par B; l’application C donne le minimum de f le long des directions générées, il
suit que C véri…e la troisième condition. Il nous reste donc à montrer que B est fermée sur le complémentaire de , où = fx : rf (x) = 0g.
e¤et, soit xk 2
= ; xk ! x; et soit yk 2 B(xk ); yk ! y; on doit démontrer que y 2 B(x):
Par dé…nition de yk , yk = xk
0 tel que,
k S0 rf (xk ) pour k
f (yk )
comme rf (x) 6= 0 (car x 2
=

S0 rf (xk ))

f (xk

8

0;

(4.14)

), alors
k

de plus, quand k ! 1; y = x
f (yk )

!

=

ky xk
kS0 rf (x)k

0;

S0 rf (x): Alors :
f (xk

S0 rf (xk ))

8

0;

donc y est obtenu en mimimisant f le long de la direction S0 rf (x);-c.à.d- y 2 B(x); d’où
B est fermé sur C .
Notons encore que -rf (x)t S0 rf (x) < 0 (car S0 est dé…nie positive ), ce qui justi…e que d est
une direction de descente -c.à.d- y 2 B(x) ) f (y) f (x); 8x 2
= :
Supposons de plus que est compact, pour que les quatre conditions soient satisfaites et
par conséquent, en cosidérant le théorème 1.6, il suit que l’algorithme A converge vers un point
stationnaire.

1.6.2

Cas où la recherche linéaire est inéxacte

Dans ce cas, le théorème 4.2, de convergence …nie, n’est plus valable pour les méthodes DFP
et BFGS car sa preuve nécéssite les propriétées de la recherche linéaire éxacte.
Pour les fonctions non quadratiques, sans utiliser une recherche linéaire exacte, et sous
certaines conditions, Powell, en 1976 ([27]) a montré qu’une version de la méthode metricvariable ( méthodes DFP et BFGS) converge vers la solution optimale, si la fonction objective
f était convexe. Il montra aussi dans le même contexe que si la matrice hessienne de f était
dé…nie positive au point x (x solution optimale), alors la convergence était superlinéaire.
16

E

1.6. CONVERGENCE DES MÉTHODES QUASI-NEWTON
Dans notre mémoire on utilisé les méthodes DFP et BFGS avec les recherches linéaire
inéxactes de Wolf et d’Armijo(voir Chap.2). Donc il est nécéssaire de donner les théorème qui
caractérisent la convergence de ces méthodes.
Théorème 4.3 :
Soit l’algorithme xk+1 = xk
k Sk rf (xk ); où fSk g est une suite de matrices dé…nies positives
dont les spectres sont uniformément bornés (0 < c1 minmi (Sk ) maxmi (Sk ) c2 ): Si f 2
i

i

C 1 (Rn ); minorée, et à gradient Lipschitsien de constante L, et si les k sont choisis selon la
méthode de sélection d’Armijo (voir recherche linéaire d’Armijo, Chap.2), alors cet algorithme
converge vers un mimimum local de f:
Preuve :
L’algorithme est bien une méthode de descente, car :
rf (xk )t dk =

krf (xk )k2Sk

c1 krf (xk )k2 ;

par ailleurs, en appliquant la formule de la moyenne à la fonction
f (xk + dk ) = f (xk ) + rf ( k )t ( dk );

k

7! f (xk + dk ); on obtient :

2 [xk ; xk + dk ]:

On peut donc écrire
f (xk + dk )

f (xk ) = (rf ( k )

rf (xk ))t ( dk );

ce qui, en utilisant le caractère lipschitizien du gradient de f et la dé…nition de dk ,
f (xk + dk )

f (xk )

L k dk k2 + (rf (xk ))t ( dk );
L 2 kSk rf (xk )k2
rf (xk )t Sk rf (xk ):

Le premier terme du membre de droite étant majoré par L 2 c2 krf (xk )k2Sk ; on peut conclure
que :
f (xk + dk ) f (xk )
(L c2 1) krf (xk )k2Sk :
(4.15)
Rappelons que la méthode de sélection d’armijo, dans le cas d’une direction de descente dk =
Sk rf (xk ) est
f (xk + dk ) f (xk )
" krf (xk )k2Sk :

1 "
dans
c2 L
(4.14) pour remplir la condition d’armijo. Par ailleurs, compte-tenu du principe de sélection,
1 "
on aura k
.
2c2 L
On en déduit d’une part qu’avec ce choix, on a f (xk+1 ) = f (xk + k dk ) < f (xk ); et donc
que la suite ff (xk )gk2N converge, puisqu’elle est minorée, et d’autre part que krf (xk )k2Sk
f (xk ) f (xk+1 )
: Le terme de droite convergeant vers 0 ; donc krf (xk )k ! 0; puisque tous les
"
Sk ont un spectre strictement positif . La méthode proposée converge donc vers un minimum
local de f:
La constante " étant …xée, il su¢ t de choisir

k

tel que L c2

17

1

";c.-à-d.

k

CHAPITRE 1. MÉTHODES QUASI-NEWTON
Théorème 4.4 :
Supposons que f est convexe et possède des dérivées secondes continues sur l’ensemble borné
fx : f (x) f (x1 )g : Alors l’algorithme BFGS avec recherche linéaire de wolfe véri…e :
lim inf kg(x)k = 0:
Preuve :
soit
pk = xk+1 xk :
qk = rf (xk+1 ) rf (xk ):
Les hypothèses de ce théorème impliquent :
kqk k2
(pk ; qk )

(4.16)

M

où M est une constante véri…ant :
kHk k

M

(pour la démonstation de cette partie voir lemme 5.2 chapitre 5).
Prenons maintenant la formule BFGS approchant le Hessien. La trace et le determinant de
Bk+1 sont donnés par :
kqk k2 kBk pk k2
(4.17)
tr (Bk+1 ) = tr(B) + t
p k qk
ptk Bk pk
det(Bk+1 ) = det(Bk )

ptk qk
:
ptk Bk pk

(4.18)

L’inégalité ( 4.16) et la notion de trace impliquent la majortion suivante
tr(Bk+1 ) < tr(B1 ) +

k
X
kqj k2
j=1

Pjt qj

tr(B1 ) + M K
c3 k; k = 1; 2; 3; ::
où c3 = tr(B1 ) + M:
Rapplons ici que la moyenne arithmétique est superieure à la moyenne géométrique : si
a1 ; a2 ; ::::; an sont k nombres positifs, alors
1X
aj
k j=1
k

!k

k
Y

aj

(4.19)

j=1

Appliquons ce resultat aux valeurs propres de la matrice Bk+1 on obtient la relation :
det(Bk+1 ) <

(c3 k)n
; k = 1; 2; 2; :::
n
18

(4.20)

1.6. CONVERGENCE DES MÉTHODES QUASI-NEWTON
Puisque la trace de Bk+1 est positive, on déduit aussi que
k
X
kBj pj k2
j=1

< tr(B1 ) +

ptj Bj pj

k
X
kqj k2

ptj qj

j=1

c3 k; k = 1; 2; 3; :::

Appliquons encore une fois la relation ( 4.20 ), on trouve
k
Y
kBj pj k2

ptj Bj pj

j=1

< ck3 ;

k = 1; 2; 3; :::::

(4.21)

De plus (4:19) nous donne
k
det(Bk+1 ) Y ptj qj
=
:
det(B1 )
pt B p
j=1 j j j

(4.22)

D’après (4.21), (4.22), et (4.23), on déduit :
k
Y
kBj pj k2 ptj qj

ptj Bj pj

j=1

remplaçons Bj pj = Bj

j dj

=

j Bj (

2

(

<

ck4 ; k = 1; 2; 3; :::

Bj 1 rfj ) =

n
Y
krfj k2 ptj qj
j=1

n

ck3 =n ck3
;
det(B1 )

ptj rfj )2

j rfj

;on obtient

< ck4 ; k = 1; 2; 3; :::;

Rappelons que la recherche de Wolfe permet de donner
dtk rf (xk + k dk )
dtk [rf (xk + k dk ) rf (xk )]
ptk qk

c2 dtk rfk ;
dtk rfk (c2 1);
( ptk rfk )(1 c2 );

d’où,

et il suit que

ptk qk
ptk rfk

1

k
Y
krfj k2
<
t
p
rf
j
j
j=1

où bien
19

c2 ;

k

c4
1

c2

;

(4.23)

CHAPITRE 1. MÉTHODES QUASI-NEWTON



k
Y
krfj k2
kpj k cos
j=1

<
j

k

c4
1

c2

; k = 1; 2; 3; :::;

(4.24)

est l’angle compris entre pj et rfj :
Comme f (x) est bornée inferieurement, la condition (Wolfe) nous permet de conclure que
la somme
j

1
X
k=1

t
k dk rfk =

1
X
k=1

kpk k krfk k cos( k )

est convergente.
Donc si on suppose qu’il existe un " > 0 telque krfk k > " > 0 pour tout k; alors
kpk k cos( k ) ! 0:
kgj k2
! 1 quand j ! 1
kpj k cos j
qui donne une contradiction avec( 4.24 ), et par conséquent
lim inf kg(x)k = 0:
Dans ce cas les termes

20

Bibliographie
[1] M. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method with
inexact line search, IMA J. Numer. Anal., 5 (1985), pp. 121–124.
[2] L. Armijo, Minimzation of function having lipschitz continous …rst partial derivatives,
Paci…c Journal of Mathematics, Vol. 16 (1966), pp.1-3.
[3] L. Andrieu, Optimisation sous contrainte en probabilité, THESE présentée pour l’obtention
du titre de Docteur de l’Ecole Nationale des Ponts et Chaussées, décembre (2004)
[4] M. Bellou…, R. Benzine, and Y. Laskri, Modi…cation of the Armijo line search to satisfy
the convergence properties of HS method, An International Journal of Optimization and
Control : Theories & Applications (IJOCTA), 141(2013), 145-152 .
[5] M. Bellou… and R. Benzine, Global Convergence Properties of he HS Conjugate Gradient
Method. Applied Mathematical Sciences, Vol. 7, 142(2013), 7077 –7091
[6] E. M. L. Beale, A derivative of conjugate gradients, in Numerical Methods for Nonlinear
Optimization, F. A. Lootsma, ed., Academic Press, London, (1972), pp. 39–43.
[7] M. S. Bazaraa and H. D. Sherali, et C. M. Shetty , Nonlinear Programming, Theory and
Algorithms, Wiley-Interscience(1993).
[8] I. Bongartz, A. R. Conn, N. I. M. Gould, and P. L. Toint, CUTE : constrained and
unconstrained testing environments, ACM Trans. Math. Software, 21 (1995), pp. 123–160.
[9] C. G. Broyden, The convergence of a class of double-rank minimization algorithms 1.
general considerations, J. Inst. Math. Appl., 6 (1970), pp. 76–90.
[10] A. Buckley, Conjugate gradient methods, in Nonlinear Optimization 1981, M. J. D. Powell,
ed., Academic Press, London, (1982), pp. 17–22.
[11] C. W. Carroll, The created reponse surface technique for optimizing nonlinear restrained
systems, Operations Res., Vol. 9 (1961), pp. 169-84.
[12] H. P. Crowder and P. Wolfe, Linear convergence of the conjugate gradient method, IBM
J. Res. Dev., 16 (1969), pp. 431–433.
[13] X.D. Chen and J. Sun, Global convergence of a two-parameter family of conjugate gradient
methods without line search, Journal of Computational and Applied Mathematics 146
(2002) 37–45.
[14] A. Cauchy, Analyse mathématique, Méthode générale pour la résolution des systèmes
d’équations simultanées, Comptes Rendus de l’Académie des Sciences de Paris, (1847)
t-25, pp. 536-538.
21

BIBLIOGRAPHIE
[15] Y. H. Dai, Analyses of conjugate gradient methods, Ph.D. thesis, Institute of Computational Mathematics and Scienti…c/Engineering Computing, Chinese Academy of Sciences,
1997.
[16] Y. H. Dai, New properties of a nonlinear conjugate gradient method, Numer. Math., 89
(2001), pp. 83–98.
[17] Y. H. Dai, A nonmonotone conjugate gradient algorithm for unconstrained optimization,
J. Syst. Sci. Complex., 15 (2002), pp. 139–145.
[18] Y. H. Dai, J. Y. Han, G. H. Liu, D. F. Sun, H. X. Yin, and Y. Yuan, Convergence properties
of nonlinear conjugate gradient methods, SIAM J. Optim., 10 (1999), pp. 345–358.
[19] Y. H. Dai and L. Z. Liao, New conjugacy conditions and related nonlinear conjugate
gradient methods, Appl. Math. Optim., 43(2001), pp. 87–101.
[20] Y. H. Dai and Q. Ni, Testing di¤erent conjugate gradient methods for large-scale unconstrained optimization, J. Comput. Math., 21 (2003), pp. 311–320.
[21] Y. H. Dai and Y. Yuan, Convergence properties of the Fletcher-Reeves method, IMA J.
Numer. Anal., 16 (1996), pp. 155–164.
[22] Y. H. Dai and Y. Yuan, Convergence properties of the conjugate descent method, Adv.
Math. (China), 26 (1996), pp. 552–562.
[23] Y. H. Dai and Y. Yuan, Further studies on the Polak-Ribière-Polyak method, Research
report ICM-95-040, Institute of Computational Mathematics and Scienti…c/Engineering
Computing, Chinese Academy of Sciences, 1995.
[24] Y. H. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global
convergence property, SIAM J. Optim., 10 (1999), pp. 177–182.
[25] Y. H. Dai and Y. Yuan, Convergence of the Fletcher-Reeves method under a generalized
Wolfe wearch, J. Comput. Math., 2 (1996), pp. 142–148.
[26] Y. H. Dai and Y. Yuan, A class of globally convergent conjugate gradient methods,
Research report ICM-98-030, Institute of Computational Mathematics and Scienti…c/Engineering Computing, Chinese Academy of Sciences, 1998.
[27] Y. H. Dai and Y. Yuan, Extension of a class of nonlinear conjugate gradient methods, Research report ICM-98-049, Institute of Computational Mathematics and Scienti…c/Engineering Computing, Chinese Academy of Sciences, 1998.
[28] Y. H. Dai and Y. Yuan, Nonlinear Conjugate Gradient Methods, Shanghai Science and
Technology Publisher, Shanghai, 2000.
[29] Y. H. Dai and Y. Yuan, A three-parameter family of hybrid conjugate gradient method,
Math. Comp., 70 (2001), pp. 1155–1167.
[30] Y. H. Dai and Y. Yuan, An e¢ cient hybrid conjugate gradient method for unconstrained
optimization, Ann. Oper. Res., 103 (2001), pp. 33–47.
[31] Y. H. Dai and Y. Yuan, A class of globally convergent conjugate gradient methods, Sci.
China Ser. A, 46 (2003), pp. 251–261.
22

BIBLIOGRAPHIE
[32] J. W. Daniel, The conjugate gradient method for linear and nonlinear operator equations,
SIAM J. Numer. Anal., 4 (1967), pp. 10–26.
[33] G. Fasano, Planar conjugate gradient algorithm for large-scale unconstrained optimization.
Part 1 : Applications, Journal of Optimization Theory and Applications 125(2005) 543–
558.
[34] R. Fletcher, Practical Methods of Optimization vol. 1 : Unconstrained Optimization, John
Wiley & Sons, New York, 1987.
[35] R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Comput. J.,
7(1964), pp. 149–154.
[36] R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimization,
Computer. J., 6 (1963), pp. 163-168.
[37] A. V. Fiacco and G. P. McCormick, Nonlinear Programming, John Wiley, New York,
(1968).
[38] J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods
for optimization, SIAM J. Optim., 2 (1992), pp. 21–42.
[39] J. C. Gilbert , Eléments d’Optimisation Di¤érentiable : Théorie et Algorithmes, Notes de
cours, École Nationale Supérieure de Techniques Avancées, Paris, (2007).
[40] L. Grippo and S. Lucidi, A globally convergent version of the Polak-Ribi´ ere conjugate
gradient method, Math. Prog., 78 (1997), pp. 375–391.
[41] L. Grippo and S. Lucidi, Convergence conditions, line search algorithms and trust region
implementations for the Polak-Ribiére conjugate gradient method, Technical Report 25-03,
Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, November
(2003) (to appear on Optim. Methods Softw.).
[42] A.A. Goldstein and J.F. Price, An e¤ective algorithm for minimzation, Num.Math., 10
(1969), pp. 184-189.
[43] A. A. Goldstein, On steepest descent, SIAM J. on Control A, Vol. 3, No. 1 (1965), pp.
147-151.
[44] W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent
and an e¢ cient line search, November 17, (2003) (to appear in SIAM J. Optim.).
[45] W. W. Hager and H. Zhang, CG DESCENT, a conjugate gradient method with guaranteed
descent, January 15, (2004) (to appear in ACM TOMS).
[46] J. Y. Han, G. H. Liu, and H. X. Yin, Convergence properties of conjugate gradient methods
with strong Wolfe linesearch, Systems Sci. Math. Sci., 11 (1998), pp. 112–116.
[47] M. R. Hestenes and E. L. Stiefel, Methods of conjugate gradients for solving linear systems,
J. Research Nat. Bur. Standards, 49 (1952), pp. 409–436.
[48] Y. F. Hu and C. Storey, Global convergence result for conjugate gradient methods, J.
Optim. Theory Appl., 71 (1991), pp. 399–405.
[49] R. A. Horn, and C. R. Johnson, Matrix Analysis, Cambridge University Press, (1990)
23

BIBLIOGRAPHIE
[50] G. H. Liu, J. Y. Han and H. X. Yin, Global convergence of the Fletcher-Reeves algorithm
with an inexact line search, Appl. Math. J. Chinese Univ. Ser. B, 10 (1995), pp. 75–82.
[51] Y. Liu and C. Storey, E¢ cient generalized conjugate gradient algorithms, Part 1 : Theory,
J. Optim. Theory Appl., 69 (1991), pp. 129–137.
[52] J. L. Nazareth, A conjugate direction algorithm without line searches, J. Optim. Theory
Appl., 23 (1977), pp. 373–387.
[53] J. L. Nazareth, Conjugate-gradient methods, Encyclopedia of Optimization, C. Floudas
and P. Pardalos, eds., Kluwer Academic Publishers, Boston, (1999).
[54] J. M. Perry, A class of conjugate gradient algorithms with a two-step variable-metric
memory, Discussion Paper 269, Center for Mathematical Studies in Economics and Management Sciences, Northwestern University, Evanston, Illinois, (1977).
[55] E. Polak and G. Ribière, Note sur la convergence de directions conjugées, Rev. Francaise
Informat Recherche Opertionelle, 3e Année 16 (1969), pp. 35–43.
[56] B. T. Polyak, The conjugate gradient method in extreme problems, USSR Comp. Math.
Math. Phys., 9 (1969), pp. 94–112.
[57] M. J. D. Powell, Some convergence properties of the conjugate gradient method, Math.
Prog., 11 (1976), pp. 42–49.
[58] M. J. D. Powell, Restart procedures of the conjugate gradient method, Math. Prog., 2
(1977), pp. 241–254.
[59] M. J. D. Powell, Nonconvex minimization calculations and the conjugate gradient method,
Numerical Analysis, Lecture Notes in Mathematics, Vol. 1066, Springer-Verlag, Berlin,
(1984), pp. 122–141.
[60] M. Rivaie, M. Mamat , L. W. June ,and I. Mohd, A new class of nonlinear conjugate
gradient coe¢ cients with global convergence properties. Applied Mathematics and Computation 218 (2012) 11323–11332.
[61] D. F. Shanno, On the convergence of a new conjugate gradient algorithm, SIAM J. Numer.
Anal., 15 (1978), pp. 1247–1257.
[62] J. Sun, X.Q. Yang, and X.D. Chen, Quadratic cost ‡ow and the conjugate gradient method,
European Journal of Opera-tional Research 164 (2005) 104–114.
[63] J. Sun and J. Zhang, Global convergence of conjugate gradient methods without line search,
Ann. Oper. Res., 163 (2001), pp. 161–173
[64] Z.J. Shi and J. Shen, Convergence of descent method without line search, Appl. Math.
Comput. 167 (2005) 94–107.
[65] Z.J. Shi, Restricted PR conjugate gradient method and its global convergence, Advances
in Mathematics 31 (1) (2002) 47–55 (in Chinese).
[66] Z.J.Shi and J.Shen, Convergence of Liu-Storey conjugate gradient method, European Journal of Operational Research,182(2)(2007), 552–560 .
[67] Z.J. Shi and J. Shen, Convergence of Polak-Rebière-Polyak conjugate gradient method,
Nonlinear Analysis, 66 (2007), 1428–1441.
24

BIBLIOGRAPHIE
[68] D. Touati-Ahmed and C. Storey, E¢ cient hybrid conjugate gradient techniques, J. Optim.
Theory Appl., 64 (1990), pp. 379–397.
[69] P. Wolfe, Convergence conditions for ascent methods, SIAM Review, 11 (1969), pp. 226–
235.
[70] P. Wolfe, Convergence conditions for ascent methods. II : Some corrections, SIAM Review,
13 (1971), pp. 185–188.
[71] P. Wolfe, A duality theorem for nonlinear programming, Quart. Appl. Math., 19 (1961),
pp. 239-244.
[72] H. Yabe and M. Takano, Global convergence properties of nonlinear conjugate gradient
methods with modi ?ed secant condition, Comput. Optim. Appl., 28, (2004), pp. 203–225.
[73] Y. Yuan, Analysis on the conjugate gradient method, Optim. Methods Softw., 2 (1993),
pp.19–29.
[74] Y. Yuan, Numerical Methods for Nonlinear Programming, Shanghai Scienti…c & Technical
Publishers, 1993.
[75] J. Z. Zhang, N. Y. Deng, and L. H. Chen, new quasi-Newton equation and related methods
for unconstrained optimization, J. Optim. Theory Appl., 102 (1999), pp. 147–167.
[76] J. Z. Zhang and C. X. Xu, Properties and numerical performance of quasi-Newton methods
with modi…ed quasi-Newton equations, J. Comput. Appl. Math., 137 (2001), pp. 269–278.
[77] G. Zoutendijk, Nonlinear Programming, Computational Methods, in Integer and Nonlinear
Programming, J. Abadie, ed., North-Holland, Amsterdam, (1970), pp. 37–86.
[78] G. Zoutendijk, Methods of Feasible Directions, Elsevier, Amesterdam (1960).

25



Documents similaires


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


Sur le même sujet..