Méthode des directions conjuguées

Pour les fonctions quadratiques !

1 xT A x + b T x + c
f (x) = 2
On construit n directions lin indép et mutuel-
lement conjuguées par rap. à A : d0 , . . . , dn−1

Directions mutuellement conjuguées par rap-

port à A : dT
i Adk = 0 k = 1, . . . , k − 1

Algorithme :
• Point de départ :
0

 x

g = ∇f (x 0 ) = Ax0 + b
 0

d0 = −g0
• itération k : on est au pt xk
gkT gk
αk = T ; xk+1 = xk + αk dk
dk Adk
T
gk+1 gk+1
gk+1 = ∇f (xk+1 ); βk =
gkT gk
dk+1 = −gk+1 + βk dk
• Si βk = 0 STOP sinon k ← k + 1 1
Exercice 4.2.5.

Soit f (x) = x2 2 2
1 + 10x2 + x3 + x1x2 − x1x2x3

1. Pour quel ensemble de pts, les directions

( √1 , √1 , 0)T et (− √1 , √1 , − √1 )T sont-elles
2 2 3 3 3
conjuguées par rapport au hessien de f ?
2. Déterminer x̌, le pt de cet ensemble de norme
min (le plus proche de 0)
3. Déterminer une 3ème direction (de norme 1),
conjuguée aux 2 autres par rapport au hessien
de f en x̌.

2
  
2x1 + x2 − x2 x3
1. ∇f =  x1 + 20x2 − x1 x3 
2x − x1 x2
 3 
2 1 − x3 −x2
2
∇ f =  1 − x3 20 −x1 
−x2 −x1 2

Les 2 directions seront conjuguées par rapport

à ∇2f si x est tq dT 2
1 ∇ f (x)d2 = 0

− √1
 
3
√1 √1 1
   
0 2
∇ f
 √ =0

2 2 3
− √1
 
  3
 −1

⇔ 1 1 0 ∇2 f  1  = 0
 

 −1 
  x2 − x 3 − 1
⇔ 1 1 0  19 + x3 + x1  = 0
 
x2 − x 1 − 2
⇔ x1 + x2 + 18 = 0
Equation d’un plan ⊥ au plan x3 = 0

3
⇒ ∀ pt de la forme x = (α, −18 − α, µ); α, µ ∈ R
les 2 directions seront conjuguées par rapport
au hessien de f en x
q
2. On doit minimiser x2
1 + x 2 + x2
2 3

→ min(x2 2 2 2 2 2
1 + x2 + x3) = min(2α + 36α + 18 + µ )
µ,α

∂ =0⇒µ=0 
∂µ
∂ = 0 ⇒ 4α + 36 = 0 ⇒ α = −9 
∂α
⇒ x̌ = (−9, −9, 0)
3. En x̌,
 
2 1 9
2
∇ f =  1 20 9 
9 9 2

On cherche d3 = (λ1 , λ2 , λ3 )T tq
dT ∇ 2f (x̌)d = 0
1 3
dT 2
2 ∇ f (x̌)d3 = 0

4
   
!2 1 9 λ1
1 1 0
⇒  1 20 9   λ2  = 0
  
−1 1 −1
9
 9 2 λ3
λ
21 18  1 
!
3
⇒  λ2  = 0
−10 10 −2
λ3
(
λ1 + 7λ2 + 6λ3 = 0
⇒
(
−5λ1 + 5λ2 − λ3 = 0
λ3 = −5λ1 + 5λ2
⇒
29λ1 = 37λ2
Si λ1 = 37α alors λ2 = 29α et λ3 = −40α

||d3|| = 1 :

λ2 + λ 2 + λ2 = 1 ⇒ α 2 = 1 = 1
1 2 3 292+372+402 3810

1
⇒ d3 = √ (37, 29, −40)
3810

5
Méthodes des directions conjuguées
Fonctions non quadratiques :
Généralisation de l’algo pr fcts quadratiques :
Fletcher-Reeves - Polak-Ribière

Algorithme :

• Point de départ : x0 ; d0 = −g0

• itération k : on est au pt xk
αk tq min g(α) = min f (xk + αdk )
α α
xk+1 = xk + αk dk
F R ||∇f (xk+1)||2
βk =
||∇f (xk )||2
P R ∇T f (xk+1 )[∇f (xk+1)−∇f (xk )]
βk =
||∇f (xk )||2
dk+1 = −gk+1 + βk dk
• Test d’arrêt, sinon k ← k + 1

Convergence globale pas assurée.

→ réinitialisation ttes les n étapes. (automatique pr PR)

Méthodes superlinéaires sur n étapes.

Méthodes quadratiques sur n étapes si Condition de Lip-
schitz (||∇2f (x∗ ).y|| ≤ K||y|| ∀y ∈ Rn)
6
Exercice 4.2.11.
! !T
2 0 −4
Minimiser f (x) = 1 2 x T x + x
0 8 −8
par la méthode de Fletcher-Reeves à partir de
x0 = (0 0)T .
Vérifier que :
• les directions de déplacement sont mutuel-
lement conjuguées
• les gradients sont orthogonaux
• dT T
k gk = −gk gk < 0 (Condition de descente)

f(x) est quadratique

⇒ F.R. ≡ algo des gradients conjugués.
! !
2 0 −4
∇f (x) = x+
0 8 −8

7
Première itération :
! !
0 4
x0 = d0 = −∇f (x0 ) = = −g0
0 8
αk ?

−∇fkT dk gkT gk
αk = = T
dT
k Adk dk Adk
 

4
4 8
8 80 5
⇒ α0 =    = =
4 8

2 0 4 544 34
0 8 8
! !
5 4 20/34
x1 = x0 + α0d0 = 34 =
8 40/34
!
−48/17
g1 = ∇f (x1 ) =
24/17
g1T g1 36
⇒ β0 = T = 289
g0 g0
!
120 8
d1 = −g1 + β0d0 = 289
−1

8
Deuxième itération
 
−24 120

8
−2 1
17 289 −1 17
⇒ α1 =    = ... =
120 120
8 −1

2 0 8 40
289 289 0 8 −1
 20  !
2
 
8
x2 = x1 + α1d1 = 34 40 + 17 120
−1
=
34
40 289 1
!
0
g2 =
0
⇒ β1 = 0 ⇒ α2 = 0; x2 = x3 = . . .
⇒ optimum atteint (pt stationnaire !)

La méthode converge bien en n (=2) étapes

au plus pour une fct quadratique.
Le min est en x∗ = (2 1)T ; f (x∗ ) = −8
C’est un min global (cf. répet précédente)

9
Vérifications :
• Directions mutuellement conjuguées ?
  
120 2 0 4
dT
1 Ad 0 = ( 8 −1 ) 0 8 8
=0
289
⇒ d0, d1 conjuguées par rapport à A
• Gradients orthogonaux ?
  
−4
∇f (x0 ) = g0 =


−8

  ⇒ g0T g1 = 0 OK
2
∇f (x1 ) = g1 = −24 

17 −1


• Condition de descente ?
k = 0 dT T
0 g0 = −g0 g0 < 0 OK car !
d0 = −g0
 −2
120 24

T
k = 1 d1 g1 = 289 8 −1
1 17

= 120.24.(−17)
289.17 = −120.24
289 !
−2
−g1T g1 = −( 24
 
) 2 −2 1
17 1
= −5.24.24
17 2 = −120.24 OK
289
⇒ d0 et d1 sont bien des directions de des-
cente
10
Méthode de Newton f ∈ C 2(Rn )

Au voisinage de xk , on remplace f par son ap-

proximation quadratique. Si ∇2f (xk ) > 0, xk+1
est le min de cette quadratique.

xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk ); αk = 1

• Convergence globale pas assurée.
• Convergence asymptotique superlinéaire d’ordre
2.
• Une seule étape pour f quadratique stricte-
ment convexe.

Exercice 4.2.7.
Soit f (x) = 2x3
1 + (3x 1 + 2)x 2 + 4x2 + 4x + 1
2 1 1
1. Approximer f(x) par une quadratique au voi-
sinage de 0.
2. Déterminer les itérés x1 et x2 par la méthode
de Newton.
3. Que se passe-t-il si on tente d’appliquer la
méthode de la plus forte pente ?
11
1. Taylor : x0 = 0
f (x) ' f (x0 ) + ∇T f (x0 )(x − x0) + 21 (x − x0)T ∇2f (x0 )(x − x0)
= q(x)

 
0
f 0
=1
     
6x21 + 3x22 + 8x1 +4 0 4
∇f = ⇒ ∇f
2x2 (3x1 + 2)  0  0 
12x1 + 8 6x2 0 8 0
∇2 f 6x2 6x1 + 4
⇒ ∇ 2f
0
= 0 4

⇒ q(x) = 4x1 + 2x2

2 + 4x1 + 1

2. Newton : x1 min de q(x) déterminé en 1.

∇q(x k+1 ) = 0
− 12
     
8x1 + 4 0
⇒ 4x2
= 0
⇒ x1 = 0

On peut aussi utiliser la relation

xk+1 = xk − [∇2f (xk )]−1 ∇f (xk )
  −1 
   1 
0 8 0 4 −2
Ici, x1 = 0 − 0 4 0
= 0
 1   −1  3   5 
−2 2 0 −4
x2 = 0
− 0 1
2
0
= 0
12
3. Plus forte pente :
x1 = x0 − α∇f (x0 )
αk = minα f (x0 + αd0) = minα g(α)
!
−4α
g(α) = f = −2.43 α3 + 4.42 α2 − 4.4α + 1
0
dg 3α2 + 8.42 α − 42 = 0
dα = −6.4
⇒ −24α2 + 8α − 1 = 0
∆ = 64 − 4.24 < 0 ⇒ Pas de min ?

La convergence globale est assurée si f ∈ C 1(Rn )

et f → +∞ si ||x|| → +∞, ce qui n’est pas le
cas ici.

Existe-t-il des pts stationnaires ?

2

 x2 = 0 ⇒ 6x1 + 8x1 + 4 = 0 Imp.

∇f (x) = 0 ⇒ ou

 2 ⇒ 3x2 + 4 = 0
x1 = − 3 Impos.
2 3
⇒ pas de pt stat !
⇒ pas de min local à la fonction.
13