MAT 2410:

Optimisation

Robert Guénette

Département de Mathématiques et de Statistique

Chapitre 3
Optimisation différentiable sans contrainte
Références

Condition d’optimalité
Condition du premier ordre
Condition du deuxième ordre

Méthodes numériques
Généralité
Méthode de descente
Méthode de Newton
Méthode quasi-Newton
Méthode du gradient conjugué
Méthodes de recherche linéaire
Méthodes directes
Références:
• Notes de cours: chapitre 3, section 3.1.
• Livre de M. Delfour: chapitre 3.
Condition nécessaire d’optimalité du premier ordre

Théorème:
Soit f : U −→ R une fonction numérique de classe C 1 définie sur un
ensemble ouvert U ⊂ Rn . Si x ∈ U est un point minimisant (minimum
local ou global), alors
∇f (x) = 0.
Preuve: Fixons v ∈ Rn . La fonction t → f (x + tv ) atteint un minimum
en t = 0. Par conséquent
d
f (x + tv )|t=0 = (∇f (x), v ) = 0, v ∈ Rn ,
dt
d’où le résultat.
Condition nécessaire et suffisante d’optimalité

Théorème:
Soit f : U −→ R une fonction numérique convexe de classe C 1 définie
sur un ensemble ouvert convexe U ⊂ Rn .
I x ∈ U est un point minimisant de f si et seulement si ∇f (x) = 0.
Preuve: Il suffit de montrer l’implication ⇐=.
f est convexe si

f (y ) ≥ f (x) + (∇f (x), y − x) ∀y ∈ U

Mais ∇f (x) = 0 =⇒ f (y ) ≥ f (x) ∀y ∈ U, d’où le résultat.

Condition nécessaire d’optimalité du deuxième ordre
Théorème:
Soit f : U −→ R une fonction numérique de classe C 2 définie sur un
ensemble ouvert U ⊂ Rn . x ∈ U est un point minimisant de f , alors
I ∇f (x) = 0
I Hf (x) ≥ 0 où Hf est la matrice hessienne.
Preuve: Montrons que Hf (x) ≥ 0. Par Taylor, on a

1
f (y ) = f (x) + (∇f (x), y − x) + (H (y − x), (y − x))
2
où H = H(x + t̄(y − x)) pour 0 < t̄ < 1. Ceci est valide dans un
voisinage V du point x. Mais
1
∇f (x) = 0 =⇒ f (y ) − f (x) = (H (y − x), (y − x)).
2
Par un argument de continuité et y → x, on obtient que

(Hf (x) (y − x), (y − x)) ≥ 0

Pour tout v ∈ Rn , il est toujours possible de choisir r ∈ R de sorte que

y = x + r v ∈ V . En posant y − x = r v , on obtient le résultat.
Condition suffisante d’optimalité du deuxième ordre

Théorème:
Soit f : U −→ R une fonction numérique de classe C 2 définie sur un
ensemble ouvert U ⊂ Rn .
(a) Si le point x ∈ U vérifie

∇f (x) = 0 et Hf (x) > 0,

où Hf est la matrice hessienne au point x, alors x est un minimum

local dans U.
(b) S’il existe un voisinage V du point x ∈ U vérifiant

∇f (x) = 0 et Hf (y ) ≥ 0 ∀y ∈ V ,

alors x est un minimum global dans V et local dans U.

Preuve de (a)

Si Hf (x) > 0, on aura que localement, il existe un voisinage V vérifiant

x ∈ V ⊂ U tel que =⇒ Hf (y ) > 0 ∀y ∈ V .
Par Taylor, on a
1
f (y ) = f (x) + (∇f (x), y − x) + (H (y − x), (y − x))
2
où H = H(x + t̄(y − x)) pour 0 < t̄ < 1.
Mais ∇f (x) = 0 et que H = H(x + t̄(y − x)) > 0.
Ceci implique
1
f (y ) = f (x) + (H (y − x), (y − x)) ≥ f (x) ∀y ∈ V .
2
Donc x est un minimum local.
Preuve de (b)

Pour y ∈ V , on a
1
f (y ) = f (x) + (∇f (x), y − x) + (H (y − x), (y − x))
2
Mais ∇f (x) = 0 et Hf (y ) ≥ 0 ∀y ∈ V =⇒ H ≥ 0 Donc

1
f (y ) = f (x) + (∇f (x), y − x) + (H (y − x), (y − x))
2
1
f (y ) = f (x) + (H (y − x), (y − x))
2
f (y ) ≥ f (x)

d’où le résultat.
Méthodes numériques de minimisation
On considère le problème de minimisation f (x̄) = min f (x) où
x∈U
f : U −→ R est une fonction numérique définie sur un ensemble ouvert
U ⊂ Rn .

On cherche à produire une suite ayant les propriétés suivantes:

I f (xk+1 ) ≤ f (xk )
I xk → x̄ où x̄ est un point minimisant (local ou global).
Les méthodes sont regroupées en deux familles.
a) Les méthodes de descentes

x 0 ∈ Rn ,

xk+1 = xk + ρk dk .

où dk est la direction de descente et ρk > 0.

b) Les méthodes de type Newton. On résout le système non linéaire

∇f (x) = 0.
Méthode du gradient

Dans la méthode du gradient, on choisit

dk = −∇f (xk )

comme direction de descente car

f (xk+1 ) = f (xk − ρk ∇f (xk ))

1
= f (xk ) − ρk (∇f (xk ), ∇f (xk )) + 2 ρ2k (H ∇f (xk ), ∇f (xk )))

' f (xk ) − ρk k∇f (xk )k2 ≤ f (xk )

Algorithme du gradient:
I x0 ∈ Rn donné
I xk+1 = xk − ρk ∇f (xk ) où ρk > 0.
Si ρk = ρ, l’algorithme est dit à pas constant.
Critère d’arrêt

On peut utiliser un (ou une combinaison) des critères suivants pour

arrêter les itérations d’un algorithme de descente.
I Etant donné que ∇f (xk ) → ∇f (x̄) = 0, on pose

k∇f (xk )k < 1 .

I On a xk → x̄, on peut aussi prendre

kxk+1 − xk k < 2 .

I Finalement, on a f (xk ) → f (x̄) , on peut prendre

kf (xk+1 ) − f (xk )k < 3 .

Etude de la convergence
Voici un résultat de convergence de la méthode du gradient.
Théorème: Soit f : Rn −→ R une fonction convexe et coercive de classe
C 2 admettant un seul minimum. De plus, on suppose qu’il existe une
constante M > 0 telle que
(Hf (x) v , v ) ≤ M kv k2 ∀x, v ∈ Rn .
Si on choisit les ρk dans l’intervalle
0 < β1 < ρk < β2 < 2/M,
alors l’algorithme du gradient converge.
1
Exemple: on prend f (x) = (Ax, x) − (b, x) + c avec A > 0. Vérifions
2
les hypothèses du théorème.
On sait que Hf (x) = A. Aussi f admet un seul minimum. De plus
(A v , v ) ≤ M kv k2 ∀v ∈ Rn
où M > 0 est la plus grande valeur propre de A. Donc la méthode du
gradient converge et s’écrit
I x0 ∈ Rn donné,
I xk+1 = xk + ρk (b − A xk ).
Méthode du gradient à pas optimaux
Dans la pratique, la méthode du gradient à pas constant converge très
lentement. Pour améliorer la convergence il est préférable de choisir les
ρk de manière optimale
I x0 ∈ Rn donné
I xk+1 = xk − ρk ∇f (xk )
où ρk > 0 est choisi de sorte que

min f (xk − ρ ∇f (xk ))

ρ

Note: la condition d’optimalité de ce problème de minimisation s’écrit

d
0= f (xk − ρ ∇f (xk ))|ρ=ρk = (∇f (xk+1 ), ∇f (xk ))
dρ

c’est-à-dire
∇f (xk+1 ) ⊥ ∇f (xk )
Calcul du pas optimal
En général, il n’est pas facile de calculer exactement la valeur ρ qui
minimise min f (xk − ρ ∇f (xk )). Par contre, pour la fonction
ρ

1
f (x) = (Ax, x) − (b, x) + c
2
avec A > 0, la situation est plus facile.

Résidu: il est défini par r = −∇f (x) = b − A x.

La méthode du gradient s’écrit:

xk+1 = xk − ρk ∇f (xk ) = xk + ρk rk
=⇒ Axk+1 − b = Axk − b + ρk Ark
=⇒ rk+1 = rk − ρk Ark

La condition d’optimalité pour ρk est

∇f (xk+1 ) ⊥ ∇f (xk ) ⇐⇒ (rk+1 , rk ) = 0 ⇐⇒ (rk − ρk Ark , rk ) = 0

krk k2
ce qui fournit la valeur ρk = .
(Ark , rk )
Méthode de Newton

Soit f : U −→ R une fonction numérique de classe C 2 définie sur un

ensemble ouvert U ⊂ Rn .
Une condition nécessaire (et suffisante si f est convexe) pour qu’un point
x̄ ∈ U soit un minimum (local ou global) est

∇f (x̄) = 0

Par conséquent, le point x̄ doit vérifier le système de n équations à n

variables
F (x) = ∇f (x) = 0.
Une approche très populaire pour résoudre F (x) = 0 est la méthode de
Newton.
Méthode de Newton (suite)
Soit F : U −→ Rn une application à valeur vectorielle de classe C 2
définie sur un ensemble ouvert U ⊂ Rn . On notera F = (F1 , F2 , . . . , Fn ).


 F1 (x1 , x2 , x3 , . . . , xn ) = 0
 F2 (x1 , x2 , x3 , . . . , xn ) = 0



F (x) = 0 ⇐⇒ F3 (x1 , x2 , x3 , . . . , xn ) = 0
 .. .
= ..



 .
Fn (x1 , x2 , x3 , . . . , xn ) = 0


Résidu: le résidu est défini par R(x) = −F (x).

Matrice jacobienne: la matrice jacobienne dF ( aussi noté par J) est

définie par  ∂F 
∂F1
1
∂x1 ∂x2 . . . ∂F
∂xn
1

 ∂F
 2 ∂F2 . . . ∂F2 

 ∂x1 ∂x2 ∂xn 
dF (x) = 
 .. .. .. .. 

 . . . . 
 
∂Fn ∂Fn ∂Fn
∂x1 ∂x2 . . . ∂xn
Méthode de Newton (suite)

La méthode de Newton est basée sur l’approximation linéaire de F autour

d’un point x0
F (x0 + ∆x) ≈ F (x0 ) + dF (x0 ) ∆x
On désire calculer la correction ∆x de sorte que
−1
0 = F (x0 +∆x) ≈ F (x0 )+dF (x0 ) ∆x = 0 =⇒ ∆x = − [dF (x0 )] F (x0 )

Etant donné l’approximation, il est nécessaire d’itérer ce qui conduit à

l’algorithme suivant.

Méthode de Newton
1. Etant donné une approximation initiale x0 ,
2. Résoudre le système linéaire: dF (xk ) ∆x = −F (xk ) = R(xk ),
3. Mettre à jour la solution: xk+1 = xk + ∆x,
||∆x||
4. Si ||xk+1 || < 1 et/ou ||F (xk+1 )|| < 2 , la convergence est atteinte.
Calcul du minimum par la méthode de Newton
Soit f : U −→ R une fonction numérique de classe C 2 définie sur un
ensemble ouvert U ⊂ Rn . Il s’agit de résoudre

f (x̄) = min f (x)

x∈U

On pose F (x) = ∇f (x). La matrice jacobienne est

∂Fi ∂ ∂f ∂2f
dF (x) = = = = Hf (x)
∂xj ∂xj ∂xi ∂xi ∂xj

qui est toujours symétrique.

L’algorithme de Newton s’écrit

x0 ∈ Rn ,

−1
xk+1 = xk − [Hf (xk )] ∇f (xk ).

Remarque:
I Très sensible au choix du point initial.
I La convergence est en général quadratique.
Lien entre Newton et la méthode de descente
Faisons l’hypothèse que la matrice hessienne vérifie au point minimisant
x̄, la condition

Hf (x̄) > 0 =⇒ Hf (x) > 0 ∀x près de x̄.

En particulier, on aura pour les xk près de x̄

−1
Hf (xk ) > 0 =⇒ [Hf (xk )] > 0.

On développe f par Taylor autour du point xk

1
f (xk+1 ) = f (xk ) + (∇f (xk ), xk+1 − xk ) + (H (xk+1 − xk ), xk+1 − xk ).
2
Mais l’algorithme de Newton fournit la valeur xk+1 = xk − Mk−1 ∇f (xk )
−1
où Mk−1 = [Hf (xk )] > 0.
En négligeant le terme d’ordre 2, on obtient

f (xk+1 ) = f (xk ) − (Mk−1 ∇f (xk ), ∇f (xk ) + 1

2 (H (xk+1 − xk ), xk+1 − xk ),
≈ f (xk ) − (Mk−1 ∇f (xk ), ∇f (xk )),
≤ f (xk ) car Mk−1 > 0.
Méthode quasi-Newton

La méthode de Newton pose plusieurs difficultés.

Approximation de la matrice hessienne

En premier, il y a la nécessité de calculer la matrice hessienne. Pour
certains types de problèmes, cela peut devenir problématique. Dans ce
cas, on peut avoir recours à une approximation de la matrice hessienne.
Pour cela, on utilise la formule de différences finies
∇f (x + hej ) − ∇f (x)
H(x) ej ≈
h
où ej est le j ième vecteur de la base canonique de Rn . h > 0 est une
petite valeur de l’ordre de 10−8 . On notera que H(x) ej représente la j
ième colonne de la matrice hessienne.
Méthode quasi-Newton (suite)

Méthode de quasi-Newton modifiée

Cette approche est basée sur l’observation que si Mk est une matrice
symétrique et définie-positive, alors

dk = −Mk−1 ∇f (xk )

est une direction de descente. En effet, on applique de nouveau Taylor

1
f (xk+1 ) = f (xk + dk ) = f (xk ) + (∇f (xk ), dk ) + (H dk , dk ).
2
En négligeant le terme d’ordre 2, on obtient

f (xk+1 ) = f (xk ) − (Mk−1 ∇f (xk ), ∇f (xk ) + 1

2 (H dk , dk ),
≈ f (xk ) − (Mk−1 ∇f (xk ), ∇f (xk )),
≤ f (xk ) car Mk−1 > 0.
Méthode quasi-Newton (suite)
Le choix de newton comme direction de descente dk = −H(xk )−1 ∇f (xk )
ne fonctionne que si la matrice est H(xk ) > 0. Supposons qu’à une
certaine itération, la matrice H(xk ) n’est pas définie-positive. Elle admet
les valeurs propres
λ1 ≤ λ2 ≤ · · · ≤ λn
Si λ1 <  pour une petite valeur  > 0, on peut translater la matrice
H(xk ) de sorte que les valeurs propres soient toujours plus grande que
 > 0. Il suffit de poser

Mk = H(xk ) + ( − λ1 ) I .

Méthode de Newton modifiée

1. Etant donné une approximation initiale x0 ,
2. Calculer la première valeur propre λ1 de H(xk ). Si λ1 < , poser
Mk = H(xk ) + ( − λ1 ) I , sinon Mk = H(xk ).
3. Calculer la direction de descente: Mk dk = −∇f (xk ),
4. Mettre à jour la solution: xk+1 = xk + dk .
Méthode quasi-Newton (suite)

Finalement, il est souvent nécessaire de garantir que f (xk+1 ) ≤ f (xk ).

Ceci peut être fait en modifiant la mise à jour de la solution

xk+1 = xk + ρk dk

où ρk > 0 est choisi de sorte que

min f (xk + ρ dk )
ρ

Dans la pratique, il est préférable de faire plutôt une recherche linéaire à

partir de la valeur ρ = 1. Afin de garantir la convergence quadratique, il
est important de terminer les itérations avec le choix de ρk = 1. Les
algorithmes de recherche linéaire seront présentés plus loin.
Directions conjugées

Pour l’algorithme du gradient à pas optimal, les directions de descentes

dk = −∇f (xk ) vérifie la propriété

dk+1 ⊥ dk .

Pour des courbes de niveaux très applaties, la convergence de

l’algorithme du gradient peut être très lente à cause du mouvement en
zig-zag. Par conséquent, nous allons définir d’autres directions de
descentes qui respectent mieux la géométrie du problème.

En premier, nous allons considérer le cas quadratique min f (x) avec

1
f (x) = (Ax, x) − (b, x) où A est symétrique et définie-positive.
2
C’est-à-dire, nous allons traiter de la résolution itérative du système
linéaire
Ax = b.
Algorithme du gradient conjugué
Directions conjugées Un ensemble de vecteurs {d0 , d1 , d2 , . . . , dk } est
dit A-conjuguée si
(A di , dj ) = 0 ∀i 6= j
Autrement dit, les {di } sont perpendiculaires entre eux par rapport au
produit scalaire induit par la matrice A: hu, v i = (Au, v ).

Le but de l’algorithme du gradient conjugué est de construire deux suites

de vecteurs: les itérés {x0 , x1 , x2 , . . . , xk } et les directions de descentes
{d0 , d1 , d2 , . . . , dk } qui vérifient les propriétés suivantes. On note le
vecteur résidu: rk = b − Axk .
I la suite des résidus {r0 , r1 , r2 , . . . , rk } forme un système orthogonal
(au sens usuel)
I la suite des directions de descentes {d0 , d1 , d2 , . . . , dk } forme un
système A-conjuguées.
Conséquence: l’algorithme du gradient conjugué converge en au plus n
itérations, i.e. fournit la solution exacte de Ax = b.
Algorithme du gradient conjugué (suite)

L’objectif est de construire les itérés xk et les directions conjuguées dk .

Voici les étapes de l’algorithme du gradient conjugué

I Mise à jour de xk :
xk+1 = xk + ρk dk
I Mise à jour du résidu rk :

rk+1 = rk − ρk A dk

I Mise à jour des directions conjuguées dk :

dk+1 = rk+1 + βk dk

L’algorithme démarre avec le choix d0 = r0 = b − A x0 pour un certain

point initial x0 (par exemple x0 = 0.)
Calcul des coefficients ρk

Il suffit d’exiger que rk+1 ⊥ rk .

(rk , rk )
0 = (rk+1 , rk ) = (rk − ρk A dk , rk ) =⇒ ρk =
(A dk , rk )

Or rk = dk − βk−1 dk−1 =⇒

(A dk , rk ) = (A dk , dk −βk−1 dk−1 ) = (A dk , dk ) car les dk sont A-conjugué.

Ceci fournit la valeur

krk k2
ρk =
(A dk , dk )
Calcul des coefficients βk

Il suffit d’exiger que dk+1 ⊥A dk .

(rk+1 , A dk )
0 = (dk+1 , A dk ) = (rk+1 + βk dk , A dk ) =⇒ βk = −
(A dk , dk )
rk+1 − rk
Mais rk+1 = rk − ρk A dk =⇒ −A dk = . Ceci fournit la valeur
ρk

(rk+1 , A dk ) (rk+1 , rk+1ρk−rk ) (rk+1 , rk+1 )

βk = − = =
(A dk , dk ) (A dk , dk ) ρk (A dk , dk )
krk k2
car (rk+1 , rk ) = 0. De plus, ρk = (A dk ,dk )
Ceci fournit la valeur finale
krk+1 k2
βk = .
krk k2
Méthode du gradient conjugué
Voici l’algorithme final:

I Evaluer le résidu initial r0 = b − Ax0 et poser d0 = r0 .

I Pour k = 0, . . . , jusqu’à convergence, faire:
krk k2
I calculer ρk =
(A dk , dk )
I xk+1 = xk + ρk dk
I rk+1 = rk − ρk A dk
krk+1 k2
I βk =
krk k2
I dk+1 = rk+1 + βk dk
I Fin de la boucle sur k
Remarques: Le critère d’arrêt est généralement de la forme krk k <  ou
krk k
encore < . Souvent, on prend x0 = 0 comme point de départ.
kr0 k
Généralisation au cas non linéaire

Nous allons généralisé l’algorithme du gradient conjugué pour des

problèmes min f (x) où f est non quadratique (cas non linéaire).

Les principales étapes de l’algorithme demeurent les mêmes.

On pose rk = −∇f (xk ).
I Mise à jour de xk :
xk+1 = xk + ρk dk
I Mise à jour du résidu rk :

rk+1 = −∇f (xk+1 )

I Mise à jour des directions conjuguées dk :

dk+1 = rk+1 + βk dk
Calcul des coefficients: cas non linéaire

I Calcul des coefficients ρk : on calcule la valeur optimale qui réalise le

minimum de
min f (xk + ρ dk ),
ρ

généralement fait par un algorithme de recherche linéaire.

I Calcul des coefficients βk : deux choix sont possibles
krk+1 k2
I βk = (Fletcher-Reeves)
krk k2
(rk+1 − rk , rk+1 )
I βk = (Polak-Ribière)
krk k2
Souvent, ce dernier choix conduit à de meilleurs résultats.
Remarque: dans le cas non linéaire, on perd la propriété que l’algorithme
converge en au plus n itérations.
Méthodes de recherche linéaire

Dans plusieurs algorithmes présentés jusqu’à présent, il est nécessaire de

minimiser
min f (x + ρ d),
ρ>0

suivant une direction de descente d.

Posont g (ρ) = f (x + ρ d). La condition d’optimalité du minimum est

g 0 (ρ) = 0

que l’on peut résoudre soit par la méthode de Newton ou celle de la

sécante.
Recherche linéaire: méthode de Newton


 ρ0 donné,

g 0 (ρk )
 ρk+1 = ρk − 00

g (ρk )
où g 0 (ρ) = (∇f (x + ρ d), d) et g 00 (ρ) = (Hf (x + ρ d)d, d)

Remarques:
I Converge rapidement
I On peut choisir ρ0 = 0
I Si f convexe, g 00 (ρ) > 0
I Nécessite le calcul de la matrice hessienne
I Peut diverger si ρopt trop loin de ρ0 = 0
I Peut converger vers une valeur ρ < 0
Recherche linéaire: méthode de la sécante

 ρ0 , ρ1 donnés,


ρk − ρk−1
 ρk+1 = ρk − g 0 (ρk )
g 0 (ρk ) − g 0 (ρk−1 )
où g 0 (ρ) = (∇f (x + ρ d), d). On notera que

g 0 (ρk ) − g 0 (ρk−1 )
g 00 (ρk ) ≈
ρk − ρk−1

Remarques:
I Converge rapidement
I Besoin de 2 valeurs: ρ0 = 0 mais ρ1 =?
I N’exige pas le calcul de la matrice hessienne
I Peut diverger si ρopt trop loin de ρ0 = 0
I Peut converger vers une valeur ρ < 0
Méthode de recherche linéaire approchés

En général, il n’est pas nécessaire de calculer précisément la valeur de ρ

qui minimise
min f (x + ρ d).
ρ>0

On peut se contenter d’une valeur très approximative. En fait, il suffit de

trouver une valeur ρ qui diminue de manière significative
f (x + ρ d) < f (x).

Posons g (ρ) = f (x + ρ d). On choisit une valeur 0 < β < 1 plus près de
0 ( par exemple: β = 0.1).
On dira que la valeur ρ diminue de manière significative f si

g (ρ) ≤ g (0) + β ρ g 0 (0) ⇐⇒ f (x + ρ d) ≤ f (x) + β ρ (∇f (x + ρ d), d)

Méthode d’Armijo

I ρ donné. (ρ = 1)
I On vérifie que g (ρ) ≤ g (0) + β ρ g 0 (0)
I Sinon, on diminue le pas: ρ ←− τ ρ
où 0 < τ < 1 pas trop petit, par exemple τ = 0.5.

Remarque: cette méthode connue sous le nom de Armijo Backtracking

Line Search, est idéal pour les méthodes de minimisation de type Newton
car la valeur ρ = 1 joue un rôle particulier.
Conditions de Wolfe
Pour les méthodes de type gradient (conjugué), la méthode d’Armijo
n’est pas suffisante. La condition

g (ρ) ≤ g (0) + β ρ g 0 (0)

va fournir une borne supérieure ρmax pour laquelle la condition est

satisfaite. Mais on a aucune borne inférieure. Donc on peut être très loin
du minimum de min f (x + ρ d). Pour cela, on introduit une seconde
ρ>0
condition qui exige que la dérivée g 0 (ρ) soit près de 0. Soit 0 < β2 < 1
pas trop petit, par exemple β2 = 0.9.

Condition faible de Wolfe

g 0 (ρ)
≤ β2 ⇐⇒ −g 0 (ρ) ≤ β2 (−g 0 (0))
g 0 (0)
car g 0 (0) < 0. Cette condition permet d’accepter toutes les valeurs où
g 0 (ρ) > 0.

Condition forte de Wolfe: |g 0 (ρ)| ≤ β2 |g 0 (0)|

Cette condition plus forte, limite grandement les valeurs acceptables de ρ.
Méthode directe basée sur le nombre d’Or

I Connue sous le nom de Golden section minimization.

I Permet le calcul d’un minimum (local) d’une fonction continue
f : [a, b] → R.
I N’utilise pas la dérivée.
I Peut s’appliquer aux fonctions non dérivables

Principe de la méthode: soient x1 < x2 dans l’intervalle [a, b]

I Si f (x1 ) ≤ f (x2 ), alors il y a un minimum (local) dans l’intervalle
[a, x2 ].
I Si f (x1 ) ≥ f (x2 ), alors il y a un minimum (local) dans l’intervalle
[x1 , b].
Méthode directe (suite)

A partir du principe de base, il s’agit de construire une suite de

sous-intervalles [ak , bk ] de l’intervalle initial [a, b] contenant le minimum
local x̄. On pose a0 = a et b0 = b.
I ak ≤ x̄ ≤ bk ∀k,
I bk − ak → 0.

Pour les deux évaluations x1 < x2 dans chacun des sous-intervalles

[ak , bk ], on pourrait prendre ceux situés au tiers et au deux-tiers de
l’intervalle.

Par exemple: pour [a, b] = [0, 1], on aurait x1 = 1/3 et x2 = 2/3. Si

f (x1 ) ≤ f (x2 ), les prochaines évaluations de l’intervalle [0, 2/3] seraient
x1 = 2/9 et x2 = 4/9. Aucun de ces points ne correspondent aux points
x1 , x2 de l’itération précédente.
Méthode directe (suite)

Par un meilleur choix des points x1 , x2 , il est possible de réutiliser un de

ces points à l’itération suivante. Pour cela, on pose x1 = (1 − λ)ak + λbk
et x2 = λak + (1 − λ)bk avec 0 < λ < 1. Faisons l’hypothèse que
l’intervalle [ak , x2 ] est choisi. Il s’agira de déterminer λ de sorte que le
nouveau x2 est égal à l’ancien x1

x1 = λak + (1 − λ)x2

En substituant, on obtient
√
2 3− 5
λ = (1 − λ) =⇒ λ = ≈ 0.382 > 0
2
√
−1 + 5
On observe que 1 − λ = ≈ 0.618 est le nombre d’Or.
2
Autrement dit, le découpage de l’intervalle [ak , bk ] doit se faire suivant
les rapports 0.382 et 0.618.
Méthode directe (suite)

Il reste à préciser le critère d’arrêt.

Pour cela, il faut évaluer bk+1 − ak+1 en fonction de bk − ak . De

nouveau, faisons l’hypothèse que l’intervalle [ak , x2 ] est choisi. On aura
que ak+1 = ak et bk+1 = x2 . On obtient

bk+1 − ak+1 = [λak + (1 − λ)bk ] − ak = (1 − λ)(bk − ak ),

c’est-à-dire

bk − ak = (1 − λ)k (b − a) ≈ (0.618)k (b − a).

Si x̄ dénote le minimum cherché, on aura

x̄ − ak ≤ bk − ak = (1 − λ)k (b − a) < 

Ceci permet de calculer le nombre d’itérations k nécessaires pour obtenir

la précision désirée.