Fichier PDF

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

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



PROFESSEUR BENZINE RACHID. COURS OPTIMISATION SANS CONTRAINTES TOME1 .pdf



Nom original: PROFESSEUR BENZINE RACHID. COURS OPTIMISATION SANS CONTRAINTES TOME1.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 20/03/2016 à 12:28, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 6390 fois.
Taille du document: 34.9 Mo (153 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


OPTIMISATION SANS
CONTRAINTES
TOME1 : CONDITIONS
D’OPTIMALITE. RECHERCHES
LINEAIRES. METHODE DU
GRADIENT. METHODE DE
NEWTON.

*****************
PROFESSEUR BENZINE RACHID
27 février 2016

1

Table des matières
1 OPTIMISATION SANS CONTRAINTES. NOTIONS DE
BASE ET CONDITIONS D’OPTIMALITE
6
1.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Direction de descente . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Schémas général des algorithmes d’optimisation sans contraintes 8
1.3.1
1.4

1.5
1.6
1.7

Exemples de choix de directions de descente . . . . . .

1.3.2 Exemple de choix de pas k . . . . . . . . . . . . .
Conditions nécessaires d’optimalité . . . . . . . . . . . . .
1.4.1 Condition nécessaire d’optimalité du premier ordre
1.4.2 Condition nécessaire d’optimalité du second ordre .
Conditions su¢ santes d’optimalité . . . . . . . . . . . . . .
Les modes de convergence . . . . . . . . . . . . . . . . . .
EXERCICES . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

9

. 9
. 9
. 9
. 9
. 10
. 11
. 12

2 OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES 23
2.1 Introduction. Méthodes à directions de descente . . . . . . . . 23
2.1.1 Choix optimal du pas k . . . . . . . . . . . . . . . . . 24
2.2 Recherches linéaires exactes . . . . . . . . . . . . . . . . . . . 32
2.2.1 L’intervalle d’incertitude . . . . . . . . . . . . . . . . . 32
2.2.2 La méthode progressive-retrogressive ou ForwardBackward Algorithm . . . . . . . . . . . . . . . . . 33
2.2.3 Fonctions unimodales . . . . . . . . . . . . . . . . . . . 39
2.3 Deux méthodes d’optimisation unidimensionnelle sans dérivées. 41
2.3.1 La méthode de dichotomie. . . . . . . . . . . . . . . . . 41
2.3.2 La méthode du nombre d’or ( golden section ). . . . . . 43

2

TABLE DES MATIÈRES

3

3 OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES
51
3.1 Introduction et rappels . . . . . . . . . . . . . . . . . . . . . . 51
3.2 Descente su¢ sante. Recherche linéaire inexacte d’Armijo . . . 59
3.2.1 Principe de la méthode . . . . . . . . . . . . . .
3.2.2 Interprétion graphique de la règle d’Armijo . . .
3.2.3 Contrainte des petits pas dans la règle d’Armijo
3.3 Recherche linéaire inexacte de Goldstein . . . . . . . .
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . .
3.3.2 L’Algorithme de Goldstein . . . . . . . . . . . .
3.4 Recherche linéaire inexacte de Wolfe . . . . . . . . . .
3.4.1 Introduction et exemple . . . . . . . . . . . . .
3.4.2 Recherche linéaire inexacte de Wolfe . . . . . .
3.4.3 Rechreche linéaire inexacte de Wolfe-forte . . .
3.4.4 L’algorithme de wolfe . . . . . . . . . . . . . . .
3.4.5 La règle de Wolfe relaxée . . . . . . . . . . . . .
3.4.6 Algorithme Fletcher-Lemaréchal . . . . . . . .
3.5 Problèmes résolus . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

59
61
64
66
66
68
70
70
72
76
77
78
79
79

3.6 programmes en Fortran pour les recherches linéaires d’Armijo,
de Goldstein et de Wolfe . . . . . . . . . . . . . . . . . . . . . 93
3.6.1 Programme en Fortran pour la recherche linéaire d’Ar3.6.2
3.6.3

mijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
programme en Fortran pour la règle Goldstein . . . . . 94
Programme en fortran 77 pour la recherche linéaire de
wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

4 METHODE DE LA PLUS FORTE PENTE
4.1 Introduction . . . . . . . . . . . . . . . . . . . .
4.2 Algorithme de la méthode de la plus forte pente
4.3 Lignes de niveau et méthode du gradient . . . .
4.3.1 Dé…nitions . . . . . . . . . . . . . . . . .
4.3.2 Lignes de niveau et direction du gradient

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

4.4 Inconvénients de la méthode de la plus forte pente . . . . . .
4.4.1 Lenteur de la méthode au voisinage des points stationnaires . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 Le phénomène de Zigzaguing . . . . . . . . . . . . . .
4.5 Quelques remèdes . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.

97
97
99
99
99
101

. 102
. 102
. 103
. 103

TABLE DES MATIÈRES
4.5.1 Changement de direction . . . . . . . . . . . . . . . .
4.5.2 Accéleration de la convergence . . . . . . . . . . . . .
4.6 Programme en fortran 90 de la méthode de la plus forte pente
et tests numériques . . . . . . . . . . . . . . . . . . . . . . .
4.6.1 Programme en fortran 90 . . . . . . . . . . . . . . . .
4.6.2 Tests numériques . . . . . . . . . . . . . . . . . . . .
4.7 PROBLEMES . . . . . . . . . . . . . . . . . . . . . . . . . .

4
. 103
. 103
.
.
.
.

104
104
106
108

5 CONVERGENCE ET VITESSE DE CONVERGENCE DE
LA METHODE DU GRADIENT
121
5.1 Théorèmes de convergence associés aux méthodes à directions
de descente et rechreches linéaires inexactes . . . . . . . . . . 121
5.1.1 Algorithme général des directions de descente . . . . . 122
5.1.2 Convergence globale . . . . . . . . . . . . . . . . . . . 122
5.1.3 Le théorème de Zoudentijk . . . . . . . . . . . . . . . . 123
5.2 Convergence de la méthode du gradient. Cas des recherches
linéaires inexactes . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.1 Cas de la recherche linéaire inexacte de Wolfe . . . . . 126
5.2.2 Cas de la recherche linéaire inexacte d’Armijo . . . . . 127
5.3 Fonctions multivoques. Le théorème de Zangwill . . . . . . . . 130
5.3.1 Notion d’algorithme en optimisation . . . . . . . . . . 130
5.3.2 Un modèle général des algorithmes : application multivoque . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.3.3 Convergence globale . . . . . . . . . . . . . . . . . . . 132
5.3.4 Applications multivoques fermées . . . . . . . . . . . . 132
5.3.5 Composition d’applications mutivoques . . . . . . . . . 133
5.3.6 Le Théorème de Zangwill . . . . . . . . . . . . . . . . . 134
5.4 Convergence de la méthode du gradient. Cas des recherches
linéaires exactes . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.5 Etude de la convergence et de la vitesse de convergence de la
méthode du gradient pour les fonctions quadratiques strictement convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.5.1 Rappel sur quelques propriétés des matrices symétriques
dé…ni-positives . . . . . . . . . . . . . . . . . . . . . . 139
5.5.2 Optimisation quadratique sans contraintes . . . . . . . 141
5.5.3 Etude de la convergence de la méthode du gradient
pour les fonctions quadratiques strictement convexes . 144
5.5.4 Etude de la vitesse de convergence de la méthode du
gradient pour les fonctions quadratiques strictement
convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 144

TABLE DES MATIÈRES
6 LA METHODE DE NEWTON
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . .
6.1.2 Etude de la convergence . . . . . . . . . . . . . . . .
6.1.3 Avantages et Inconvénients de la méthode de Newton
6.2 Programme en fortran et tests numériques . . . . . . . . . .

5
145
. 145
. 146
. 146
. 147
. 148

Chapitre 1
OPTIMISATION SANS
CONTRAINTES. NOTIONS
DE BASE ET CONDITIONS
D’OPTIMALITE
1.1

Dé…nitions

Dé…nition 1 Soit f : Rn ! R, on appelle problème de minimisation
sans contraites le problème ( P ) suivant :
(P )

min ff (x) : x 2 Rn g

1) x^ 2 Rn est un minimum global de ( P ) si et seulement si
f (^
x)

f (x) : 8x 2 Rn

2) x^ 2 Rn est un minimum local de ( P ) si et seulement si il existe un
voisinageV" (^
x) tel que
f (^
x)

f (x) : 8x 2 V" (^
x)

3) x^ 2 Rn est un minimum local strict de ( P ) si et seulement si il existe
un voisinageV" (^
x) tel que
f (^
x) < f (x) : 8x 2 V" (^
x); x 6= x^:

6

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION

1.2

Direction de descente

Dé…nition 2 Soit f : Rn ! R, x^ 2 Rn , d 2 Rn est dite direction de
descente au point x^ si et seulement si il existe > 0 tel que
f (^
x + d) < f (^
x) : 8 2 ]0; [

Donnons maintenant une condition su¢ sante pour que d soit une direction
de descente.

Théorème 1 Soit f : Rn ! R di¤erentiable au point x^ 2 Rn et d 2 Rn
une direction véri…ant la condition suivante :
f 0 (^
x; d) = rf (^
x)t :d < 0:
Alors d est une direction de descente au point x^:

Preuve : f est di¤érentiable au point x^: Donc
f (^
x + d) = f (^
x) + rf (^
x)t :d + kdk (^
x; d);
avec
(^
x; d) ! 0;
!0

ceci implique que
f 0 (^
x; d) = lim

f (^
x + d)

!0

f (^
x)

= rf (^
x)t :d < 0:

La limite étant strictement négative, alors il existe un voisinage de zéro
V (0) = ] ; + [ tel que
f (^
x + d)

f (^
x)

< 0; 8 2 ]

;+ [:

La relation (1) est particulièrement vraie pour tout

(1)

2 ]0; + [. On obtient

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
le résultat cherché en multipliant la relation (1) par

1.3

> 0:

Schémas général des algorithmes d’optimisation sans contraintes

Supposons que dk soit une direction de descente au point xk :Ceci nous
permet de considérer le point xk+1 , successeur de xk ; de la manière suivante :
xk+1 = xk +

k dk ;

k

2 ]0; + [ :

Vu la dé…nition de direction de descente, on est assuré que
f (xk+1 ) = f (xk +
Un bon choix de dk et de
gorithmes d’optimisation.

k

k dk )

< f (xk ):

permet ainsi de construire une multitude d’al-

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION

1.3.1

Exemples de choix de directions de descente

Par exemple si on choisit dk = rf (xk ) et si rf (xk ) 6= 0; on obtient la méthode du gradient. La méthode de Newton correspond à dk =
(H(xk )) 1 :rf (xk ): Bien sur rf (xk ) est une direction de descente (rf (xk )t :dk =
rf (xk )t :rf (xk ) = krf (xk )k2 < 0): Pour la deuxième direction si la matrice hessienne H(xk ) est dé…nie positive alors dk = (H(xk )) 1 :rf (xk ) est
aussi une direction de descente.

1.3.2

Exemple de choix de pas

On choisit en général
f (xk +

k

k

de façon optimale, c’est à dire que

k dk )

k

doit véri…er

f (xk + dk ) : 8 2 [0; +1[:

En d’autres temes on est ramené à étudier à chaque itération un problème de
minimisation d’une variable réelle. C’est ce qu’on appelle recherche linéaire.

1.4
1.4.1

Conditions nécessaires d’optimalité
Condition nécessaire d’optimalité du premier ordre

Théorème 2 Soit f : Rn ! R di¤erentiable au point x^ 2 Rn . Si x^ est
un minimum local de ( P ) alors rf (^
x) = 0:
Preuve : C’est une conséquence directe du théorème 4.1 et de la remarque
4.1. En e¤et, supposons que rf (^
x) 6= 0: Puisque la direction d = rf (^
x) est
une direction de descente, alors il existe > 0 tel que :
f (^
x + d) < f (^
x) : 8 2 ]0; [ :
Ceci est contradiction avec le fait que x^ est une solution optimale locale de
( P ):

1.4.2

Condition nécessaire d’optimalité du second ordre

Théorème 3 Soit f : Rn ! R deux fois di¤erentiable au point x^ 2 Rn .
Si x^ est un minimum local de ( P ) alors rf (^
x) = 0 et la matrice hessienne
de f au point x^ , qu’on note H(^
x); est semi dé…nie positive.

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Preuve : Soit x 2 Rn quelconque, f étant deux fois di¤érentiable au point
x^;on aura pour tout 6= 0
f (^
x + x) = f (^
x) +

1
2

2 t

x H(^
x)x +

2

x2

(^
x; x) ! 0:

(^
x; x);

!0

Ceci implique
f (^
x + x)

f (^
x)

2

1
= xt H(^
x)x + x2
2

x^ est un optimum local, il existe alors
f (^
x + x)

f (^
x)

2

> 0 tel que
0;

8 2]

;+ [:

Si on prend en considération (2) et on passe à la limite quand
on obtient
xt H(^
x)x 0; 8x 2 Rn :

1.5

(2)

(^
x; x):

! 0;

6= 0;

Conditions su¢ santes d’optimalité

Théorème 4 Soit f : Rn ! R deux fois di¤erentiable au point x^ 2 Rn .
Si rf (^
x) = 0 et H(^
x) est dé…nie positive alors x^ est un minimum local
strict de ( P ).

Preuve : f
x 2 Rn

étant deux fois di¤érentiable au point x^;on aura pour tout

1
x)(x x^)+k(x
f (x) = f (^
x)+ (x x^)t H(^
2

x^)k2 (^
x; (x x^));

(^
x; (x x^)) ! 0;
x!^
x

(3)
Supposons que x^ n’est pas un optimum local strict. Alors il existe une suite
fxk gk2NN telle que xk 6= x^ : 8k et
xk 6= x^ : 8k;

xk ! x^
k!1

et

f (xk )

Dans (3) prenons x = xk , divisons le tout par k(xk
(xk x^)
; on obtient
k(xk x^)k
f (xk )
k(xk

f (^
x)
1 t
x)dk + (^
x; (xk
2 = dk H(^
2
x^)k

x^));

(4)

f (^
x):

x^)k2 et notons dk =

(^
x; (xk

x^)) ! 0: ((5))
k!1

(rf (^
x) = 0):

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
(4) et (5) impliquent
1 t
x)dk + (^
x; (xk
d H(^
2 k

x^))

0; 8k:

D’autre part la suite fdk gk2NN est bornée (kdk k = 1; 8n ). Donc il existe
une sous suite fdk gk2N1 NN telle que
dk

! de

k!1; k2N1

:

Finalement lorsque k ! 1; k 2 N1 ; on obtient
1e
dH(^
x)de
2

0:

La dernière relation et le fait que de 6= 0 ( de = 1) impliquent que la matrice hessienne H(^
x) n’est pas dé…nie positive. Ceci est en contradiction avec
l’hypothèse.

1.6

Les modes de convergence

Dé…nition 8
Soit xk k2N une suite dans Rn convergeant vers x :
kxk+1 x k
=
< 1; on dit que xk k2N converge vers
1- Si lim sup xk x
k
k
k!1
x linéairement avec le taux :
Lorsque xk+1 x '
xk x , la convergence est dite linéaire asymptotique.
kxk+1 x k
2- Si lim sup xk x
< +1; > 1 la convergence est dite superlinéaire
k
k
k!1
d’ordre :
kxk+1 x k
3- Si lim xk x
= 0; on dit que xk k2N tend vers x de façon suk
k!1 k
perlinéaire.
Lorsque xk+1 x
l xk x , la convergence est dite superlinéaire
asymptotique.

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION

1.7

EXERCICES

Exercice 1
Considérons la fonction
f (x; y) = x2 + y 2
On note par D(f; (x0 ; y0 )) l’ensemble des vecteurs d = (d1 ; d2 ) 2 R2 tels que
d est une direction de descente de f au point (x0 ; y0 ) : En d’autres termes
D(f; (x0 ; y0 )) = d = (d1 ; d2 ) 2 R2 : rf (x0 ; y0 )T :d < 0
On prend (x0 ; y0 ) = (1; 1):Trouver et representez géométriquent l’ensemble
D(f; (1; 1)).
Solution Exercice 1
On a
rf (x; y)T = (2x; 2y) =) rf (1; 1)T = (2; 2)
et
rf (1; 1)T :d < 0 () 2 (d1 + d2 ) < 0 () d1 + d2 < 0
Par conséquent
D(f; (1; 1)) = d = (d1 ; d2 ) 2 R2 : d1 + d2 < 0
Géométriquent D(f; (1; 1)) est le demi plan situé au dessous de la droite
y = x:
Exercice 2
Soit f : R2 ! R telle que f 2 C 3 (Dr (b
x; yb)) supposons que rf (b
x; yb) =
(0; 0) : Montrez que
2

2

2

2

@ f
x; yb) : @@yf2 (b
x; yb)
(b
x; yb) > 0 et
a) Si @@xf2 (b
@x@y
(b
x; yb) est une solution maximale locale stricte.
2

2

2

2

2

@2f
@x2

(b
x; yb) < 0 alors

@ f
b) Si @@xf2 (b
x; yb) : @@yf2 (b
x; yb)
(b
x; yb) > 0 et @@xf2 (b
x; yb) > 0 alors (b
x; yb)
@x@y
est une solution minimale locale stricte.
2
2
2
@2f
x; yb) : @@yf2 (b
x; yb)
x; yb) n’est ni une
c) Si @@xf2 (b
(b
x; yb) < 0 alors (b
@x@y
solution minimale locale ni une solution maximale locale.
2
2
2
@2f
d) Si @@xf2 (b
x; yb) : @@yf2 (b
x; yb)
= 0. On ne peut pas conclure ;
(b
x
;
y
b
)
@x@y
l’étude doit continuer ; (b
x; yb) peut être une solution optimale ou ne pas l’être.

Solution Exercice 2

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Puisque rf (b
x; yb) = (0; 0), étudions la dé…nie positivité ou la dé…nie
négativité de H (b
x; yb) :
!
@2f
@2f
(b
x
;
y
b
)
(b
x
;
y
b
)
@x2
@x@y
H (b
x; yb) =
2
@2f
(b
x; yb) @@yf2 (b
x; yb)
@y@x
Soit

(x; y) H (b
x; yb) :

x
y

(x; y) 2 R2 t:q (x; y) 6= (0; 0) :
= x2

Posons

a=
Alors

2
@2f
@2f
2@ f
(b
x
;
y
b
)
;
c
=
y
(b
x
;
y
b
)
;
b
=
2y
(b
x; yb) :
@x2
@x@y
@y 2

a) si 4 = b2
or
b

2

2
@2f
@2f
2@ f
(b
x; yb)
(b
x
;
y
b
)
+
y
(b
x
;
y
b
)
+
2xy
@x2
@y 2
@x@y

x
y

(x; y) H (b
x; yb)

= ax2 + bx + c

4ac < 0, alors ax2 + bx + c est du signe de a

4ac = 4y

2

= 4y

2

"

@2f
(b
x; yb)
@x@y

@2f
(b
x; yb)
@x@y

2

f
@2f
4y
(b
x; yb) : 2 (b
x; yb)
@x2
@y
2@

2

2

@2f
@2f
(b
x
;
y
b
)
:
(b
x; yb)
@x2
@y 2

#

:

y 6= 0 =) 4y 2 > 0: Donc le signe de ax2 + bx + c est du signe de :
"
#
2
@2f
@2f
@2f
(b
x; yb)
(b
x; yb) : 2 (b
x; yb)
@x@y
@x2
@y
4<0,

@2f
@2f
(b
x
;
y
b
)
:
(b
x; yb)
@x2
@y 2

@2f
(b
x; yb)
@x@y

x

2

>0

alors le signe de (x; y) H (b
x; yb) y sera du signe de
a=

c’est a dire
si

@2f
@2f
(b
x
;
y
b
)
:
(b
x; yb)
@x2
@y 2

@2f
(b
x; yb) ;
@x2

@2f
(b
x; yb)
@x@y

2

> 0 et si

@2f
(b
x; yb) > 0
@x2

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
alors

x

(x; y) H (b
x; yb) y > 0

et (b
x; yb) est une solution minimale locale stricte
b)
si
alors

@2f
@2f
(b
x
;
y
b
)
:
(b
x; yb)
@x2
@y 2

@2f
(b
x; yb)
@x@y

x y

H (b
x; yb)

2

x
y

> 0 et si

@2f
(b
x; yb) < 0
@x2

<0

et (b
x; yb) est une solution maximale locale stricte
c) Si 4 = b2 4ac > 0; alors ax2 + bx + c n’a pas un signe constant, c’est
à dire entre les racines x1 et x2 ; ax2 + bx + c aura un signe (+ ou ) et à
l’exterieur des racines, ax2 + bx + c aura un autre signe.
D’après l’étude faite en a) et b).
Si
2
@2f
@2f
@2f
(b
x; yb)
(b
x
;
y
b
)
:
(b
x; yb) < 0
@x@y
@x2
@y 2

x
< 0 n’aura pas un signe constant
y
dans R2 mais dépend de x et y. En d’autres termes H (b
x; yb) n’est pas semi
dé…nie positive et n’est pas semi dé…nie négative. Donc (b
x; yb) n’est pas une
solution optimale locale.
Exercice 3
On considère f : R2 ! R dé…nie par
alors 4 > 0 et

x y

H (b
x; yb)

f (x; y) = x2 + y 2
Montrez en utilisant la dé…nition que (b
x; yb) = (0; 0) est une solution
2
minimale locale et globale de f dans R
Solution exercice 3
On a :
f (x; y) = x2 + y 2

0 8 (x; y) 2 R2

or
f (0; 0) = 0:
Donc
8 (x; y) 2 R2 : f (x; y)

f (0; 0)

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Ceci implique que (b
x; yb) est une solution minimale globale.
Puisque
f (x; y) f (0; 0) : 8 (x; y) 2 R2
cette relation reste vraie pour n’importe quel disque Dr (0; 0) : Par conséquent si on prend D1 (0; 0), on a :
f (x; y)
a:

f (0; 0) : 8 (x; y) 2 D1 (0; 0) :

et (0; 0) est une solution minimale locale stricte car si (x; y) 6= (0; 0) on
f (x; y) = x2 + y 2 > 0 = f (0; 0) :
Exercice 4
Trouvez tous les points stationnaires de
f : R2 ! R; f (x; y) = x2 + y 2

Solution exercice 4
(x; y) = 0 et @f
(x; y) = 0; c’est à
(x; y) stationnaire si et seulement @f
@x
@y
dire que (x; y) est solution du système linéaire suivant :
2x = 0
,
2y = 0

x=0
y=0

f admet un seul point stationnaire (0; 0) :
Exercice 5
Considérons la fonction f : R2 ! R, dé…nie par
f (x; y) = x2 + y 2 :
Montrer que H (b
x; yb) est semi-dé…nie positive en tout point (b
x; yb) 2 R2 :
Solution Exercice 5
On a

@f
@2f
@f
@ 2f
@ 2f
(b
x; yb) = 2b
x;
(b
x
;
y
b
)
=
2;
(b
x
;
y
b
)
=
2b
y
;
(b
x
;
y
b
)
=
0;
(b
x; yb) = 0:
@x
@x2
@y
@x@y
@y@x
Donc H (b
x; yb) ; (b
x; yb) 2 R2 quelconque est
H (b
x; yb) =

2 0
0 2

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
(x; y) H (b
x; yb)

x
y

2x
2y

= (x; y)

= 2x2 + 2y 2

0:

Donc H (b
x; yb) est semi dé…nie positive.

Exercice 6
Trouver une fonction f : R2 ! R et (b
x; yb) 2 R2 telle que rf (b
x; yb) =
0
et
H
(b
x
;
y
b
)
est
semi
dé…nie
positive,
mais
(b
x
;
y
b
)
n’
est
pas
une
solution
0
minimale locale
Solution Exercice 6
La fonction en question est la fonction f : R2 ! R, dé…nie par
f (x; y) = x3 + y 3
et
On a
rf (x; y) =

(b
x; yb) = (0; 0):
@f
(x; y)
@x
@f
(x; y)
@y

et
rf (x; y) =

0
0

()

3x2
3y 2

=

3x2 = 0
()
3y 2 = 0

Donc (b
x; yb) = (0; 0) est le seul point stationnaire.
a) Calcul de H(0; 0)
On a
!
@2f
@2f
(x;
y)
(x;
y)
@x2
@x@y
H(x; y) =
=
@2f
@2f
(x;
y)
(x;
y)
2
@y@x
@y

x=0
y=0

6x 0
0 6y

:

Par conséquent
H(0; 0) =

0 0
0 0

On a
8 (x; y) 2 R2 : (x; y)H(0; 0)

x
y

= 0:

Donc H(0; 0) est semi dé…nie positive.
b) Montrons que (0; 0) n’est pas une solution maximale locale
En e¤et. Par dé…nition (0; 0) est une solution maximale locale si et seulement si
9D (0; 0) : 8(x; y) 2 D (0; 0) : f (x; y) f (0; 0) = 0
(P)

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
D (0; 0) étant un disque ouvert de centre (0; 0) et de rayon ; c’est à dire
D (0; 0) = (x; y) 2 R2 : x2 + y 2 <

2

Pour démontrer que (0; 0) n’est pas une solution maximale locale, on doit
prouver le contraire de la proposion (P). En d’autres termes on doit prouver :
8Dr (0; 0); 9 (e
x; ye) 2 Dr (0; 0) tel que f (e
x; ye) > f (0; 0) = 0

Soit Dr (0; 0) un disque quelconque de centre (0; 0) et de rayon r > 0 quelconque. Considérons le point (e
x; ye) tel que
x
e > 0 et x
e2 < r2 et ye = 0

On peut choisir par exemple
On a bien sur

x
e=

r
> 0 et
2
Avec ce choix le point (e
x; ye) véri…e

Donc

x
e2 + ye2 = x
e2 + 02 =

r
2

r2
< r2
4
r2
r2
+0=
< r2 :
4
4

(e
x; 0) 2 Dr (0; 0):

D’autre part
r3
f (e
x; ye) = f (e
x; 0) =
> 0 = f (0; 0)
8
Par conséquent (e
x; ye) = (0; 0) n’est pas une solution maximale locale. On
démontre de la même manière que (e
x; ye) = (0; 0) n’est pas une solution
minimale locale.
Exercice 7
la condition rf (b
x; yb) = 0 n’implique pas en général que (b
x; yb) est une
solution optimale locale. Quelle est son utilité alors ?

Solution Exercice 7
On a l’a¢ rmation suivante :
Si rf (b
x; yb) 6= 0 alors (b
x; yb) n’est pas une solution optimale locale.
L’utilité de la condition nécessaire est donc de restreindre l’ensemble où
on cherche l’optimum. Au début on cherchait l’optimum dans R2 tout entier.

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
La condition nécessaire permet de restreindre l’ensemble R2 à l’ensemble
E = f(x; y) : rf (x; y) = (0; 0)g : On peut encore obtenir un ensemble plus
petit que E: Il s’agit de l’ensemble
F = f(x; y) : rf (x; y) = (0; 0) et H (x; y) est semi positive dé…nieg :
On a bien sur
F

E

R2

On obtient l’algorithme suivant :
Algorithme
(x; y) 2 R2 donné
Si rf (x; y) 6= 0; alors (x; y) n’est ni une solution minimale locale ni une
solution maximale locale.
Si rf (x; y) = 0 ; Calculez H (x; y) :
Si H (x; y) n’est pas semi-dé…nie positive et n’est pas semi dé…nie négative,
alors (x; y) n’est pas une solution minimale locale et n’est pas une solution
maximale locale.
Si H (x; y) est semi dé…nie positive.
Continuez les recherches car (x; y) peut être une solution minimale locale
ou non.
Si H (x; y) est semi dé…nie négative
Continuez les recherches car (x; y) peut être une solution maximale locale
ou non.
Exercice 8
Considérons la fonction f : R2 ! R, dé…nie par
f (x; y) = x2 + y 2 :
Montrez en utilisant le théorème4 ? que (b
x; yb) = (0; 0) est une solution minimale stricte.
Solution Exercice 8
Comme on l’a remarqué avant

@f
@f
(x; y) = 2x;
(x; y) = 2y;
@x
@y
rf (x; y) =
H (0; 0) =

0
0

2x = 0
, (x; y) = (0; 0)
2y = 0
!
@2f
@2f
(0;
0)
(0;
0)
2 0
@x2
@x@y
=
@2f
@2f
0 2
(0; 0) @y2 (0; 0)
@y@x
,

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
x
y

(x; y) H (0; 0)

= 2 x2 + y 2 :

Si
(x; y) 6= (0; 0)
alors
2 x2 + y 2 > 0:
Donc H (0; 0) est dé…nie positive. Donc (0; 0) est une solution minimale
locale stricte.
Exercice 9
Considérons la fonction f : R2 ! R, dé…nie par
f (x; y) = x3 + y 3 :
a) Trouvez les points stationnaire de f
b) Calculez H (0; 0)
c) H (0; 0) est elle semi-dé…nie positive ? Semi dé…nie négative
d) H (0; 0) est elle dé…nie positive ? dé…nie négative ?
e) Montrez que (0; 0) n’est pas une solution minimale locale
f) Montrez que (0; 0) n’est pas une solution maximale locale
g) Que peut on conclure ?
Exercice 10
Etudiez les solutions optimales locales de la fonction f dé…nie par
f (x; y) = x2

xy + y 2 + 3x

2y + 1

Solution exercice 10
Calculons les points stationnaires de f
@f
(x; y) = 2x
@x
@f
(x; y) =
@y
rf (x; y) =

0
0

,

y+3

x + 2y

2

2x y + 3 = 0
,
x + 2y 2 = 0

x=
y=

1
3

Calculons
@2f
@x2

4 1
;
3 3

;

@2f
@y 2

4 1
;
3 3

et

@2f
@x@y

4 1
;
3 3

4
3

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
On a
@2f
@2f
(x;
y)
=
2;
(x; y) = 2;
@x2
@y 2

8(x; y) 2 R2 :

@2f
(x; y) =
@x@y

1

Par conséquent
@2f
@x2

4 1
;
3 3

:

@2f
@y 2

@2f
@x@y

4 1
;
3 3

4 1
;
3 3

2

=4

1=3>0

D’autre part :
@2f
@x2
Donc le point (b
x; yb) =

4 1
;
3 3

4 1
;
3 3

= 2 > 0:

est une solution minimale locale sricte.

Exercice 11
Etudiez les solutions optimales locales de f , dé…nie par
f (x; y) = x3 + y 3

3xy

Solution exercice 11
Calculons les points stationnaires :

rf (x; y) =

0
0

@f
(x; y) = 3x2
@x

3y

@f
(x; y) = 3y 2
@y

3x

,

3x2
3y 2

3y = 0
,
3x = 0

x2
y2

y=0
x=0

Les solutions de ce système sont (x1 ; y1 ) = (0; 0) et (x2 ; y2 ) = (1; 1) :
D’autre part
8(x; y) 2 R2 :

@2f
@2f
@2f
(x;
y)
=
6x;
(x;
y)
=
6y;
(x; y) =
@x2
@y 2
@x@y

Par conséquent
a) Pour (x1 ; y1 ) = (0; 0), on a
@2f
@2f
@2f
(0; 0) = 0;
(0; 0) = 0;
(0; 0) =
@x2
@y 2
@x@y

3

Donc
@2f
@2f
(0;
0)
:
(0; 0)
@x2
@y 2

@2f
(0; 0)
@x@y

2

=0

9=

9<0

3

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Donc (0; 0) n’est pas une solution maximale locale
une solution minimale locale.
b) Pour (x2 ; y2 ) = (1; 1) on a
@2f
(1; 1) = 6;
@x2

et (0; 0) n’est pas

@2f
@2f
(1; 1) =
(1; 1) = 6;
@y 2
@x@y

3

et
@2f
@2f
(1;
1)
:
(1; 1)
@x2
@y 2

@2f
(1; 1)
@x@y

2

=6

6

9 = 27 > 0

Puisque
@2f
(1; 1) = 6 > 0:
@x2
Donc (x2 ; y2 ) = (1; 1) est une solution minimale locale stricte.
Exercice 12
Considérons la fonction f : R2 ! R dé…nie par
f (x; y) = 100(x

y 2 )2 + (1

x)2

a) Montrez que le point (1,1) véri…e les conditions nécessaires d’optimalité
du 2ème ordre
b) Le point (1,1) véri…e t’il les conditions su¢ santes d’optimalité ?
c) (1,1) est il une solution optimale locale ?
Exercice 13
Considérons la fonction f : R2 ! R dé…nie par
f (x; y) =

x4

y4

a) Montrez que le point (0,0) véri…e les conditions nécessaires d’optimalité
du 2ème ordre
b) Montrez que (0,0) n’est pas une solution minimale locale.
Exercice 14
Considérons la fonction f : R2 ! R dé…nie par
f (x; y) = 50x2

y3

a) Montrez que le point (0,0) véri…e les conditions nécessaires d’optimalité
du 2ème ordre
b) Montrez que (0,0) n’est pas une solution minimale locale.

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Exercice 15
Considérons la fonction f : R2 ! R dé…nie par
1
f (x; y) = x2 + x cos(y)
2
a) Trouvez les points stationnaires
b) Trouvez les points qui véri…ent la condition su¢ sante d’optimalité.
c) Trouvez les solutions minimales locales strictes.

Chapitre 2
OPTIMISATION DANS R:
RECHERCHES LINEAIRES
EXACTES
2.1

Introduction. Méthodes à directions de
descente

Soit f : Rn ! R: On considère le probleme de minimisation sans contraintes
(PSC) suivant :
min ff (x) : x 2 Rn g
(PSC)
Il existe deux grandes classes de méthodes qui contribuent à résoudre le
probléme (PSC) :
a) les méthodes à diréction de descente et rechreche linéaire
b) les méthodes à région de con…ance.
Nous nous intéréssons dans cette partie aux méthodes à rechreche linéaire
et à direction de déscente dont le principe est le suivant :
Supposons qu’à l’itération k on ait un point xk 2 Rn et une direction de
descente dk 2 Rn ; c’est à dire dk véri…e :
rf (xk )T dk < 0

(1)

On a démontré au chapitre 1, que celà implique
9 > 0 : 8 2]0; [ f (xk + dk ) < f (xk )
Le sucusseur xk+1 de xk est obtenu comme suit :
xk+1 = xk +

k dk

23

;

k

2 R+

(2)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES24

k s’appelle le pas . Le choix de dk et k caractérisent l’algorithme.
Supposons que dk est detérminée. Comment choissir le pas k ? Les methodes qui s’intéressent au choix et au calcul de k s’appellent rechreches
linéaires.
Il existe deux type de rechreches linéaires :
i) les rechreches linéaire exactes.
ii) les rechreches linéaire inexactes ou économiques.

Notons 'k ( ) la fonction d’une variable réelle suivante :
2]0; +1[

'k ( ) = f (xk + dk ) :

(3)

Dé…nition 1
Supposons qu’à l’itération k on ait un point xk 2 Rn et une direction de
descente dk 2 Rn : Soit 2]0; [ telle que
8 2]0; [ f (xk + dk ) < f (xk )

(4)

On appelle taux de décroissance de f du point xk au point xk + dk le nombre
positif (f; xk ; ; dk ) suivant :
(f; xk ; ; dk ) = f (xk )

2.1.1

f (xk + dk ) = 'k (0)

Choix optimal du pas

'k ( )

(5)

k

f; xk et dk étant …xes, (f; xk ; ; dk ) dépend de : La plus grande valeur
de (f; xk ; ; dk ) mesure la meilleure descente de f du point xk au point
xk + dk : Puisque f (xk ) est …xe et ne dépend de ; la plus grande valeur de
(f; xk ; ; dk ) est atteinte pour la plus petite valeur de f (xk + dk ); c’est à
dire
max f (f; xk ; ; dk ) : 2]0; +1[g
= max f'k (0) 'k ( ) : 2]0; +1[g
= minf'k ( ) : 2]0; +1[g
En d’autres termes, on peut choisir k de fçon optimale, c’est à dire qu’en
partant du point xk et la direction dk , f décroit le mieux possible au point
xk+1 = xk + k dk : Ceci est possible si on impose à k de véri…er la condition
suivante :
8 2]0; +1[: f (xk + k dk ) f (xk + dk )
(6)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES25
Notons 'k ( ) la fonction d’une variable réelle suivante :
2]0; +1[

'k ( ) = f (xk + dk ) :

(7)

(6) et (7) donnent
'k (
ou encore

k

k)

'k ( );

8 2]0; +1[

(8)

2]0; +1[g

(9)

est solution optimale de :
'k (

k)

= minf'k ( ) :

Trouvez k vérifant (9) s’appelle rechreche linéaire exacte. Ce travail s’effectue à chaque itiration k.
Donc à chaque itiration k, on doit résoudre un probléme d’optimisation
dans R.

001

3 :jpg

f ig1 : representation de (
Exercice 1
Considérons f : R2 ! R dé…nie par
f (x; y) = x2 + y 2

k)

( )

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES26
On prend
(xk ; yk )T = (1; 1); dk =

rf (xk ; yk )

a) Calculez 'k ( ); '0k ( ); 'k (0); '0k (0)
b) Trouver le pas optimal k :
Solution Exercice 1
a) On a
rf (x; y)T = (2x; 2y)
donc

rf (xk ; yk ) = ( 2; 2)

dk =
Maintenant

(xk ; yk )T + dTk = (1; 1) + ( 2; 2) = (1; 1) + ( 2 ; 2 ) = (1

2 ;1

2 )

Par conséquent
'k ( ) = f [(xk ; yk ) + dk )] = f (1 2 ; 1 2 ) = (1 2 )2 +(1 2 )2 = 2(1 2 )2
On a
'k ( ) = 2(1

2 )2 =) '0k ( ) = 16

et
'0k ( ) = 0 ()

8

1
= :
2

D’autre part
'00k ( ) = 16 > 0 : 8 2 R

Par conséquent k = 12 est une solution minimale globale de f sur R et
'k ( 21 ) = 0 est la valeur minimale globale.
Exercice 2
Considérons f : R2 ! R dé…nie par
f (x; y) = x2 + y 2
On prend
(xk ; yk )T = (3; 4); dk =
a) Calculez 'k ( ); '0k ( ); 'k (0)
b) Trouver le pas optimal k :
c) Trouver le plus grand > 0 tel que :

rf (xk ; yk )

8 2]0; [: f [(xk ; yk ) + dk ] < f (xk ; yk )

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES27
Solution Exercice 2
a) Si (xk ; yk )T = (3; 4) ; on aura
rf (xk ; yk ) = ( 6; 8)

dk =
et

(xk ; yk )T + dTk = (3; 4) + ( 6; 8) = (3; 4) + ( 6 ; 8 ) = (3

6 ;4

8 )

Par conséquent
'k ( ) = f [(xk ; yk ) + dk ] = f (3 6 ; 4
= (3 6 )2 + (4 8 )2 = 100 2
'0k ( ) = 200

100

'0k ( ) = 0 ()

= 0:5

8 )
100 + 25

b)
D’autre part
'00k ( ) = 200 > 0 : 8 2 R =)

= 0:5 est une solution minimale locale et globale

La valeur minimale globale est égale à
'k (0:5) = 0:
Par conséquent la fonction descent le mieux au point k = 0:5: Le meilleur
successeur du point (xk ; yk ) = (3; 4)T est le point au point (xk+1 ; yk+1 ) suivant :
(xk+1 ; yk+1 ) = (xk ; yk )+

k dk

= (3; 4)T +0:5( 6; 8)T = (3; 4)+( 3; 4) = (0; 0)

(xk+1 ; yk+1 ) = (0; 0) est la solution minimale globale du problème (PSC)
principal. En d’autres termes on a abouti à la solution optimale globale en
une iteration.
c) Le plus grand > 0 tel que :
8 2]0; [: f [(xk ; yk ) + dk ] < f (xk ; yk )
véri…e
'k (0) = 'k ( )
ou encore
25 = 100

2

100 + 25 ()

2

= 0:

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES28
La solution recherchée est
= 1:
On a
2 ]0; 1[: f [(xk ; yk ) + dk ] < f (xk ; yk )
2 ]1; +1[: f [(xk ; yk ) + dk ] > f (xk ; yk )
= 1 : f [(xk ; yk ) + dk ] = f (xk ; yk )
:/Users/sony/AppData/Local/Temp/graphics/graphe1-recherches-lineaires4 :pdf
Exercice 3
Considérons f : R2 ! R dé…nie par
f (x; y) = x2 + exp(y)
On prend
(xk ; yk )T = (1; 0); dk =
a) Calculez 'k ( ); '0k ( ); 'k (0)
b) Trouver le pas optimal k :
c) Trouver le plus grand > 0 tel que :

rf (xk ; yk )

8 2]0; [: f [(xk ; yk ) + dk ] < f (xk ; yk )
Solution Exercice 3
On a
rf (x; y)T = (2x; exp(y))
donc
dk =

rf (xk ; yk ) = ( 2; 1)

Maintenant
(xk ; yk )T + dTk = (1; 0) + ( 2; 1) = (1; 0) + ( 2 ;

) = (1

2 ;

)

Par conséquent
'k ( ) = f [(xk ; yk ) + dk )] = f (1
'k ( ) = (1

2 )2 + exp(

'k (0) = f (xk ; yk ) = 2
'0k ( ) = 8
e
4

)=4

2 ;
2

) = (1

4 +e

+1

2 )2 + exp(

)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES29
b)
'0k ( ) = 0 () 8

e

4 = 0 ()

' 0:570

D’autre part
'00k ( ) = e

+ 8 =) '00k (0:570) ' 8:56 > 0:

Par conséquent la solution minimale locale stricte est
k

' 0:570

c) On a 'k (0) = f (xk ; yk ) = 2
'k (0) = 2:
D’après le graphe et le tableau de variation de f; le premier

>

k

véri…ant

2 ]0; [: 'k ( ) < 'k (0)
2 ] ; +1[: 'k ( ) > 'k (0)
est solution de l’équation
'k ( ) = 'k (0) = f (xk ; yk ) = 2

(10)

L’équation (10) n’a pas de solution exacte. Essayons de trouver une solution approchée. On a les résultats numériques suivants :
'k (1:14863) = 1: 999 954 366 636 622 718 5
'k (1:14864) = 2: 000 003 086 743 885 842 4
Puisque 'k est continue sur R et
2 2 [1: 999 954 366 636 ; 2: 000 003 086 743 8]
alors, d’après le théorème des valeurs intermédiaires, il existe

véri…ant

2]1:14863; 1:14864[
et tel que
'k ( ) = 2:
On peut prendre comme valeur approximative de ;par exemple la moitié de
l’intervalle ]1:14863; 1:14864[; c’est à dire
' 1: 148 635

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES30

'( ) = f [(xk ; yk ) + dk )]
0
2.00
0.1 1. 54
0.2 1. 17
0.3 0.90
0.4 0.71
0.5 0.60
0:57 0:585
0.6 0.588
0.7 0.65
0.8 0.80
0.9 1. 04
1.0 1. 36
1.1 1. 36

( ) = f (xk ) [(xk ; yk ) + dk )]
0.00
0.45
0.82
1. 09
1. 28
1.39
1: 415 meilleure descente
1. 412
1. 34
1. 19
0.95
0.63
0.22

Exercice4
Considérons f : R2 ! R dé…nie par
f (x; y) = x2 + y 4
On prend
(xk ; yk ) = (1; 1); dk =

rf (xk ; yk )

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES31
a) Calculez 'k ( ):
b)Trouver le pas optimal
Exercice 5
Supposons que 'k ( ) = a
Trouvez k véri…ant :
'k (

k)

= minf'k ( ) :

k:

2

+ b + c ( fonction quadratique) avec a > 0.

2]0; +1[g = minfa

2

+b +c :

2]0; +1[g (11)

Solution Exercice5
'k ( ) = a 2 + b + c
La condition nécessaire d’optimalité est la suivante
'0k ( ) = 0
Or
'0k ( ) = 2a + b:
Donc

k

doit nécessairement véri…er
k

=

b
2a

Voyons maintenant la condition su¢ sante. Si H(
alors k est un minimum local strict. Or

k)

est dé…nie positive,

H( ) = '00k ( ) = 2a; 8 2]0; +1[
Voyons sous quelles conditions H( ) est dé…nie positive.
H( ) est dé…nie positve si et seulement si 8x 2 R : xT H( ) x > 0:
Or
xT H( )x = 2ax2
Puisque x 6= 0; une condition nécessaire et su¢ sante pour que 2ax2 > 0 est
a > 0:
Par conséquent
b
k =
2a
est une solution optimale locale stricte.
Remarque
a > 0; alors H( ) est dé…nie positve sur ]0; +1[: Alors 'k ( ) est strictement convexe sur ]0; +1[ et par conséquent le probléme (9bis) est un

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES32
probléme convexe et admet une solution optimale locale et globale unique
véri…ant :
'0 ( k ) = 0
c’est à dire
k

=

b
2a

Remarque
E¤ectuer une rechreche linéaire exacte à chaque itiration, est di¢ cilement
réalisable en pratique et assez couteux en temps et mémoire, c’est pour celà
qu’on chreche k moins coûteux et facile à calculer, c’est ce qu’on appelle
rechrechre linéaire inexacte ou économique.

2.2
2.2.1

Recherches linéaires exactes
L’intervalle d’incertitude

Dé…nition 2
Soit ' : R ! R: Considérons le problème unidimensionnel suivant :
min

2]0;+1[

'( ) = '(

)

L’intervalle [a; b] ]0; +1[ est dit intervalle d’incertitude si la solution
minimale
de ' ( ) appartient à [a; b] ; mais sa valeur exacte n’est pas
connue.
La notion d’intervalle d’incertitude joue un rôle central dans les algorithmes de recherches linéaires exactes et particulièrement dans la méthode
du nombre d’or. Cette méthode exige au démarrage la connaissance d’un
intervalle d’incertitude initial [a0 ; b0 ] :
Schémas général des recherches linéaires exactes utilisant les
intervalles d’incertitude
Le principe général de toutes ces méthodes est de construire une suite
d’intervalles [ak ; bk ] telles que :
a) On démarre à partir d’un intervalle d’incertitude initial [a0 ; b0 ] et " >
0 qui determine la longueur …nale de l’intervalle dincertitude [ak ; bk ] ( En
d’autres termes l’algorithme s’arrête lorsque bk ak < "):
b) 8k : [ak ; bk ] est un intervalle d’incertitude. En d’autres termes
2
[ak ; bk ] pour tout k
c) 8k : [ak+1 ; bk+1 ] [ak ; bk ]
d) L’algrithme s’arrête si bk ak < "

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES33
e) Comme solution
on prend n’importe quel nombre
pourrait prendre par exemple
'

=

ak + b k
; ak et bk tels que : bk
2

2 [ak ; bk ] : On

ak < ":

Conclusion :
On démarre d’un intervalle d’incertitude initial [a0 ; b0 ] et " > 0 (longueur
…nale de l’intervalle [af ; bf ]) : A chaque itération k, on enlève une partie
de l’intervalle d’incertitude [ak ; bk ], pour obtenir le nouveau intervalle d’incertitude [ak+1 ; bk+1 ] ; et ainsi de suite jusqu’à arriver au dernier intervalle
d’incertitude [af ; bf ] véri…ant bf af < ":
Ceci étant, une question naturelle se pose. Quel procédé nous permet
de determiner la partie de l’intervalle [ak ; bk ] à enlever. La réponse à cette
question fera l’objet du théorème 1
f ig1

2.2.2

La méthode progressive-retrogressive ou ForwardBackward Algorithm

Nous avons vu au paragrahe précédent, que la notion d’intervalle d’incertitude joue un rôle central dans les algorithmes de recherches linéaires
exactes et particulièrement dans la méthode du nombre d’or. Cette méthode
ainsi que la méthode de dichotomie et la méthode de Fibonnachi exigent au
démarrage la connaissance d’un intervalle d’incertitude initial [a0 ; b0 ] :
La méthode suivante dite méthode progressive-retrogressive ou en
tremes anglo-saxon : Forward-Backward Algorithm consiste à determiner un intervalle d’incertitude initial [a; b]. Son principe se résume à trouver
trois points ; et tels que ' décroit de à et croit de à : En d’autres
termes on devrait choisir ; et tels que :
'( ) < '( ) et '( ) < '( ):
Sous ces conditions, on choisit
[a; b] = [ ; ]

L’Algorithme suivant permet de determiner un intervalle d’incertitude
initial [a; b] :

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES34
Algorithme (méthode progressive-retrogressive) (forward-backward
method)
Etape1 : Initialisation
Choisir 0 2 [0; +1[; h0 > 0: Calculez '( 0 ): Poser k = 0 et allez à
Etape2
Etape2 : Comparaison des valeurs de la fonction objectif
Posez k+1 = k + hk : Calculez 'k+1 = ' ( k+1 ) : Si 'k+1 < 'k ; allez à
Etape3, sinon allez à Etape4
Etape3 : Etape Progressive (Forward Step)
Posez hk+1 = 2hk ; = k ; k = k+1 ; 'k = 'k+1 ; k = k + 1 et Allez
à Etape2
Etape4 : Etape retrogressive (Backward Step) ou …nalisation
Si k = 0; intervertir la direction. Poser hk = hk ; k = k+1 et allez à
Etape2. Sinon Poser
a = min ( ;

k+1 ) ;

b = max ( ;

k+1 )

Output [a; b] :L’intervalle cherché est [a; b] :
Stop.
Déscription de l’Algorithme : forward-backward method
Principe général
Comme on l’a signalé avant, l’Algorithme précédent : Forward-Backward
Algorithm consiste à déterminer un intervalle d’incertitude initial [a; b].
A l’tération k, l’Algorithme s’arrête si a réussi à trouver trois points
;
k
k+1 ; k+2 tels que ' décroit strictement de k à k+1 et croit strictement
de k+1 à k+2 : En d’autres termes on devrait choisir k ; k+1 ; k+2 tels
que :
'( k+1 ) < '( k ) et '( k+1 ) < '( k+2 ):
Sous ces conditions, on choisit
[a; b] = [

k;

k+2 ]

Théorème 2
Si au démarrage on a
Cas1 : '( 1 ) < '( 0 ); alors l’algorithme progresse à droite du point
On aura pour tout k
k
k+1 = k + 2 h0
Si au contraire on a

0:

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES35
Cas2 : '( 1 ) > '( 0 ); alors l’algorithme progresse en faisant une marche
arrière à partir du point 0 : On a pour tout k
k+1

=

k

2k h0

Détails
L’Algorithme démarre par un point initial 0 2 [0; +1[ et un pas initial
h0 > 0, le même pour tout l’algorithme. On calcule '( 0 ); on pose k = 0 et
on va à
Etape2.
On calcule 1 = 0 + h0 et '( 1 ) et on compare les 2 valeurs '( 0 ) et
'( 1 ): Deux cas sont possibles :
Cas1 : '( 1 ) < '( 0 )
L’Algorithme progresse à droite du point 1 , c’est à dire que tous les
autres points k ; k = 2; 3; ::: se trouvent à droite du point 1
2
3

k

=
=

+ h0
2 + h0
:::::::::
= k 1 + h0
1

Cas2 : '( 1 ) > '( 0 )
L’Algorithme progresse en faisant une marche arrière, à gauche du point
,
0 c’est à dire que tous les autres points k ; k = 2; 3; ::: se trouvent à gauche
du point 0

3

=
=

k

=

2

h0
h0
2
:::::::::
0

k 1

h0

Explication et détails
Cas1 : '( 1 ) < '( 0 ) ((On va progresser dans toutes les itérations
en faisant des marches avant : k+1 = k + hk )
D’après l’Algorithme on va à l’Etape 3 dans laquelle on fait doubler le pas
h1 = 2h0 (progression). L’itération devient k = k+1, c’est à dire k = 0+1 = 1
et on revient à l’Etape2(0).

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES36
Etape2(0)
on calcule k+1 = 2 ; puis '( 2 ):
Si '( 2 ) > '( 1 ); on va à l’Etape4(0)
Etape4(0)
A L’étape4(0), puisque k = 1; l’algorithme va s’arreter et [a; b] = [ 0 ; 2 ]
Si '( 2 ) < '( 1 ); on va à l’Etape3(0)
Etape3(0)
A l’étape3, on augmente le pas h2 = 2h1 = 22 h0 ; On pose k = k + 1 =
1 + 1 = 2 et on va à l’Etape2(bis)
Etape2(bis)
on calcule k+1 = k + hk = 3 = 2 + h2 = 2 + 22 h0 = 2 + 4h0 ; puis
'( 3 ):
Si '( 3 ) > '( 2 ); on va à l’étape4 et l’algorithme s’arrête et [a; b] =
[ 1; 3] :
Si '( 3 ) < '( 2 ); on va à l’étape3 une deuxième fois qu’on note Etape3
(bis)
Etape3 (bis)
on augmente le pas h3 = 2h2 = 23 h0 ; On pose k = k + 1 = 2 + 1 = 3 et
on va à l’Etape2(tris)
Etape2 (bis)
on calcule k+1 = k + hk = 4 = 3 + h3 = 3 + 23 h0 = 2 + 8h0 ; puis
'( 4 ):
Si '( 4 ) > '( 3 ); on va à l’étape4 et l’algorithme s’arrête et [a; b] =
[ 2; 4] :
Si '( 3 ) < '( 2 ); on va à l’étape3 une troisième fois qu’on note Etape3
(tris) et on fait une autre progression du pas et ainsi de suite jusqu’à avoir
l’intervalle …nal [a; b] :
Cas2 : '( 1 ) > '( 0 ) (On va progresser dans toutes les itérations
en faisant des marches arrières : k+1 = k hk )
D’après l’Algorithme, on va à l’Etape4(0)
Etape4(0)
Puisque k = 0; l’algorithme ne s’arrête pas à cette étape.
On change de direction en posant hk = hk ; c’est à dire h0 devient
h0 ; 0 devient 1 : Donc on pose h0 = h0 ; 0 = 1 et on va à létape2(0)
Etape2(0)
h0 = 0 (Donc 0 devient 1 et 1 devient 0 ):
1 =
0 + h0 =
1
Puisqu’on est dans le cas2 et que 0 est devenu 1 et 1 est devenu 0 ; on a
donc

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES37
' ( 1 ) < ' ( 0 ) . Par conséquent on va à l’Etape3(0)
Etape3(0)
h1 = 2h0 = 2h0 ; 0 = 1 ; ' ( 0 ) = ' ( 1 ) ; k = k+1 = 0+1 = 1: Allez
à Etape2(bis)
Etape2(bis) (progession en marche arrière)
2h0 (On progresse en faisant une marche arrière
2 =
1 + h1 =
0
à partir du point 0 ): On calcule ' ( 2 ) et on compare ' ( 2 ) et ' ( 1 ) =
' ( 0) :
Si ' ( 2 ) > ' ( 0 ) ; on va à l’étape4(bis)
Etape4 (bis)
k = 1: Donc l’Algorithme s’arrête et [a; b] = [ 2 ; 1 ]
Si ' ( 2 ) < ' ( 0 ) ; on va à l’étape3(bis)
Etape3(bis)
h2 = 2h1 = 4h0 et 3 = 2 + h2 = 2 4h0 (on progresse en marche
arrière). On calcule ' ( 3 ) et on compare ' ( 3 ) et ' ( 2 ) :
Si ' ( 3 ) > ' ( 2 ) ; on va à l’étape4 et l’algoithme s’arrete, [a; b] = [ 3 ; 1 ]
Si ' ( 3 ) < ' ( 2 ) ; on va à Etape3(tris) ((on fait une nouvelle progression en marche arrière) en posant
h3 = 2h2 = 8h0 et 4 = 3 + h3 = 3 8h0 et ainsi de suite.

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES38
Exercice7
Soit ' : ]0; +1[! R, dé…nie par
' ( ) = 100

2

100 + 25

Trouvez le premier intervalle d’incertitude [a; b] en appliquant l’Algorithme
Forward-Backward et en partant du point 0 = 0:1 et h0 = 0:1
Solution Exercice7
Etape1 : initialisation
0 = 0:1 , h0 = 0:1; k = 0: Allez à Etape2(1)
Etape2(1)
1 = 0 + h0 = 0:1 + 0:1 = 0:2
' ( 0 ) = '(0:1) = 16; ' ( 1 ) = '(0:2) = 9
' ( 1 ) < ' ( 0 ) : Donc on va Etape3(1)
Etape3(1) (progression)
h1 = 2h0 = 0:2; k = 1: Allez à Etape2(2)
Etape2(2)
2 = 1 + h1 = 0:2 + 0:2 = 0:4; ' ( 2 ) = ' (0:4) = 1
' ( 2 ) < ' ( 1 ) : Donc on va Etape3(2)
Etape3(2) (progression)
h2 = 2h1 = 0:4; k = 2: Allez à Etape2(3)
Etape2(3)
3 = 2 + h2 = 0:4 + 0:4 = 0:8; ' ( 3 ) = ' (0:8) = 9
' ( 3 ) > ' ( 2 ) : Donc on va Etape4(1)
Etape4(1)
k = 2: Donc k > 0: L’Algorithme s’arrête à cette étape.
[a; b] = [ 1 ; 3 ] = [0:2; 0:8]
Exercice 8
Soit ' : ]0; +1[! R, dé…nie par
' ( ) = 100

2

100 + 25

Trouvez le premier intervalle d’incertitude [a; b] en appliquant l’Algorithme
Forward-Backward et en partant du point 0 = 0:7 et h0 = 0:1
Solution Exercice 8
Etape1 : initialisation
0 = 0:7 , h0 = 0:1; k = 0: Allez à Etape2(1)
Etape2(1)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES39
+ h0 = 0:7 + 0:1 = 0:8
' ( 0 ) = '(0:7) = 4; ' ( 1 ) = '(0:8) = 9
' ( 1 ) > ' ( 0 ) : Donc on va Etape4(1)
Etape4(1) (Progression en Marche arrière)
k étant égal à 0; donc on pose h0 = h0 = 0:1
on pose
0 = 1 = 0:8
Allez à Etape3(1)
Etape3(1)
h1 = 2h0 = 0:2; Poser k = 1 et aller à Etape2(2)
Etape2(2)
0:2 = 0:8 0:2 = 0:6
2 = 1 + h1 = 1
' ( 2 ) = ' (0:6) = 1
' ( 2 ) < ' ( 1 ) : Donc on va à Etape3(2)
Etape3(2)
h2 = 2h1 = 0:4; Poser k = 2 et allez à Etape2(3)
Etape2(3)
0:4 = 0:6 0:4 = 0:2
3 = 2 + h2 = 2
f (0:2) = 9:0
' ( 3 ) = ' (0:2) = 9
' ( 3 ) > ' ( 2 ) : Donc on va à Etape4(2)
Etape4(2)
k étant di¤érent de zéro, donc l’algorithme va s’arreter à ce stade en
prenant :
[a; b] = [ 3 ; 1 ] = [0:2; 0:8]
1

=

2.2.3

0

Fonctions unimodales

Dé…nition 3
Soit ' : R ! R: ' est dite unimodale sur l’intervalle [a; b] ; s’il existe
2]a; b[ unique tel que :
a) ' est strictement décroissante sur [a; ]
b) ' est strictement croissante sur [ ; b]
L’intervalle [a; b] s’appelle intervalle d’unimodalité associé à la fonction
':
Remarque1
Si ' est unimodale sur l’intervalle [a; b] ; alors ' admet une solution minimale unique
2]a; b[ et ' est strictement décroissante sur [a; ]

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES40
et strictement croissante sur [

; b] :

On va voir dans le théorème suivant que la connaissance de deux valeurs
d’une fonction unimodale sur [a; b] permet de réduire l’intervale d’incertitude.
Théorème 1 Soit ' : R ! R telle que ' est unimodale sur l’intervalle
[a; b] : Soient ; 2 [a; b] tels que <
1- Si ' ( )
' ( ) ; alors ' est unimodale sur l’intervalle [a; ] : [a; ]
est le nouveau intervalle d’incertitude associé à ':
2- Si ' ( ) > ' ( ) ; alors ' est unimodale sur l’intervalle [ ; b] : [ ; b] est
le nouveau intervalle d’incertitude associé à ':
Preuve du Théorème1
Démontrons le point 1) par exemple. Supposons le contraire, c’est à dire
n’appartient pas à [a; ]: Donc
que la solution minimale locale stricte
appartient à ] ; b[ . Puisque
' est unimodale sur l’intervalle [a; b] ; donc par dé…nition on a
' est strictement décroissante sur [a; ] [ [ ; ] [ [ ;
et ' est strictement croissante sur [ ; b]
Puisque
sairement

<

]

et que ' est strictement décroissante, alors on aura néces'( ) > '( ):

Ceci est impossible.
Le point 2) se démontre de la même manière.
Conséquence importante du théorème 1.
1- Si ' ( )
' ( ), alors le nouveau intervalle d’incertitude est : [a; ]
(On supprime ] ; b]).
2- Si ' ( ) > ' ( ) ; alors le nouveau intervalle d’incertitude est : [ ; b]

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES41
(On supprime [a; [)

2.3
2.3.1

Deux méthodes d’optimisation unidimensionnelle sans dérivées.
La méthode de dichotomie.

La méthode de dichotomie est simple. Elle se base sur le théorème1. Le
choix des points k et k se fait de la façon suivante :
Choix des points

k

et

k

On …xe " > 0 au démarrage, assez petit. A l’itération k, k est le milieu
de [ak ; bk ] moins ": k est le milieu de [ak ; bk ] plus ": En d’autres termes
k

k

ak + b k
"
2
ak + b k
=
+"
2
=

Algorithme de la méthode de dichotomie
Initialisation : Choisir " > 0 et la longueur …nale de l’intervalle d’incertitude `:
[a1 ; b1 ] étant l’intervalle initial.
Poser k = 1 et aller à l’étape 1.
Etape 1 :

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES42
Si bk ak < ` stop. Le minimum appartient à [ak ; bk ] :
Sinon poser :
k

k

ak + b k
"
2
ak + b k
+"
=
2
=

et aller à l’étape 2
Etape 2 :
Si ' ( k ) > ' ( k ) poser ak+1 = k ; bk+1 = bk
Sinon posez ak+1 = ak ; bk+1 = k : Remplacer k par k + 1 et aller à l’étape
1.

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES43

2.3.2

La méthode du nombre d’or ( golden section ).

La méthode du nombre d’or améliore ( en diminuant le nombre d’observations ) de la méthode de dichotomie.
A l’itération k supposons que l’on a l’intervalle [ak+1 ; bk+1 ] alors :

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES44
Si ' ( k ) > ' (
Si ' ( k ) ' (

: [ak+1 ; bk+1 ] = [ k ; bk ]:
k ) : [ak+1 ; bk+1 ] = [ak ; k ] :

k)

Choix des points k et k
Dans la méthode du nombre d’or, on exige que
conditions suivantes :

k

et

k

véri…ent les deux

Condition 1
La longueur de [ak+1 ; bk+1 ] ne dépend pas de l’itération, c’est à dire que
dans les deux cas d’observations ' ( k ) > ' ( k ) ou ' ( k ) ' ( k ) on a :
bk

k

=

k

(12)

ak

Condition 2
Le choix de k+1 et k+1 se fait de la façon suivante :
A l’itération k + 1 on a
a) k+1 coincide avec k
ou bien
b) k+1 coincide avec k :
Conséquence importante
En d’autres termes, la méthode du nombre d’or calcule une seule valeur
à l’itération k + 1:
En e¤et.
a) Si k+1 = k ; on calcule à l’itération k + 1 seulement la valeur '( k+1 ),
car ' ( k+1 ) = ' ( k ) a été calculée à l’itération k:
b) Si k+1 = k ; on calcule à l’itération k + 1 seulement la valeur '( k+1 ),
car ' k+1 = ' ( k ) a été calculée à l’itération k:
Avec ces deux conditions, on obtient les théorèmes suivants :
Théorème2
Si k et k véri…ent la condition (12), alors il existe 2]0; 1[ tel que
k
k

= ak +

= ak + (1

(bk

(13)

ak ) ;

) (bk

ak ) :

(14)

et dans les 2 cas possibles : ' ( k ) > ' ( k ) ( [ak+1 ; bk+1 ] = [ k ; bk ]) ou
' ( k ) ' ( k ) ( [ak+1 ; bk+1 ] = [ak ; k ]); la longueur de l’intervalle [ak+1 ; bk+1 ]
diminuera fois par rapport à la longueur de [ak ; bk ] ; c’est à dire qu’on a :
8k : (bk+1

ak+1 ) =

(bk

ak )

(15)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES45
Preuve du Théorème2
Puisque k 2]ak ; bk [; donc k est une combinaison convexe des points ak
et bk ; c’est à dire, il existe 2]0; 1[ tel que
k

= bk + (1

)ak = ak + (bk

ak ):

Utilisons maintenant la condition (12). On obtient
k

=

k

ak

bk

donc
k

=

k

+ ak + b k

ou en remplaçant
k

=
=
=
=
=

bk + ak [ak + (bk ak )]
bk + ak (ak + bk
ak )
ak + (bk ak )
b k + ak
ak + (bk ak )
(bk ak )
ak + (1
) (bk ak ):

Reste à démontrer la relation (15). En e¤et. Supposonsons qu’on a :
' ( k ) ' ( k ) : Donc [ak+1 ; bk+1 ] = [ak ; k ] et en utilisant (13), on a
bk+1 ak+1 = k ak
= ak + (bk ak ) ak
(bk ak )
Si ' ( k ) > ' (
tilisant (14)

k ),

alors [ak+1 ; bk+1 ] = [ k ; bk ]). Par conséquent on aura en

=
=
=
=

bk+1 ak+1 = bk
k
bk [ak + (1
) (bk ak )]
bk (ak + bk ak
b k + ak )
b k ak b k + ak + b k
ak
(bk ak ) :

Théorème 3
Sous les conditions 1 et 2 citées ci dessus, on a
Cas1 : Si ' ( k ) ' ( k ) ; alors on a
8
ak+1 = ak
>
>
<
bk+1 = k
>
k+1 = k
>
:
) ( k ak )
k+1 = ak + (1

(16)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES46
Cas2 : Si ' ( k ) > ' (
8
>
>
<

k) ;

>
>
:

alors on a

k+1

ak+1 = k
bk+1 = bk
k+1 = k
= ak + (bk

(17)
k)

Le nombre
2]0; 1[ intervenant à chaque itération de la méthode du
nombre d’or est solution de l’équation
2

+

1=0

et sa valeur approximative est
' 0:618
Preuve du théorème3
En e¤et.
a) Suppoosons qu’on a ' ( k ) ' ( k ) : Donc d’après le théorème1, on a
ak+1 = ak ; bk+1 = k : La condition2 donne k+1 = k : En…n le théorème 2
implique
k+1

= ak+1 + (1
) (bk+1 ak+1 )
= ak + (1
) ( k ak )

b) Suppoosons maintenant qu’on a ' ( k ) > ' ( k ) : Donc d’après le théorème1, on a ak+1 = k ; bk+1 = bk : La condition2 donne k+1 = k : En…n le
théorème 2 implique
k+1

Calcul de
On a
k+1

= ak+1 + (bk+1 ak+1 )
= k + (bk
k)

dans le cas ' ( k )

= ak+1 + (bk+1
= k = ak + (1

(18) implique que
ak +

'(

ak+1 ) = ak +
) (bk ak )

(

k)

k

ak ) = ak +

est solution de l’équation
( (bk

ak )) = ak + (1

) (bk

ak )

[ak +

(bk

ak ) (18)
ak ]

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES47
ou encore
( (bk

ak ))

(1

) (bk

ak ) = 0

ce qui donne
(bk

2

ak ) (

Puisque bk 6= ak pour tout k; alors
2

+

1) = 0:

est solution de l’équation

+

(19)

1=0

L’équation (19) a deux solutions qui sont approximativement
x1 ' 0:618 033 988 749 894 848 2
x2 '
1: 618 033 988 749 894 848 2
2]0; 1[: Donc

' 0:618

Calcul de dans le cas ' ( k ) > ' (
Dans ce cas on a
k+1

k)

= ak+1 + (1
) (bk+1 ak+1 ) = k + (1
= k + bk
bk + k
k
= bk
bk + [ak + (1
) (bk ak )]
= k = ak + (bk ak )

) (bk

k)

(20) implique
bk

bk +

[ak + (1

bk

b k + ak +

) (bk

ak )] = ak +

(bk

ak )

ak ) = ak +

(bk

ak )

ou encore
(1

) (bk

ce qui est équivalent à
(bk

ak )

(bk

soit en mettant (bk

ak ) + (bk

)

(bk

ak ) en facteur et en divisant par (bk
1

ce qui donne …nalement,
1

ak ) (1

+

+

(1

)

ak ) = 0;
ak ) ; on a

=0

est solution de l’équation du second degré
2

= 0 ()

2

+

1 = 0:

(20)
(2.1)
(2.2)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES48
Algorithme de la méthode du nombre d’or.
Etape initiale :
Donner [a1 ; b1 ] le premier intervalle d’incertitude et choisir ` > 0 la longueur …nale de l’intervalle d’incertitude …nal [ak ; bk ] :Poser
= 0:618 et
(1
) = 1 0:618 = 0:382
Calculer
1
1

= a1 + (1
) (b1
= a1 + (b1 a1 )

a1 )

Poser k = 1 et aller à l’étape principale.
Etape principale :
1- Si bk ak < `; stop. La solution optimale appartient à [ak ; bk ] :
Sinon si ' ( k ) > ' ( k ) aller à 2, et si ' ( k ) ' ( k ) aller à 3.
2- Poser ak+1 = k et bk+1 = bk ; k+1 = k et k+1 = ak+1 + (bk+1 ak+1 ) :
Evaluer ' k+1 et aller à 4.
3- Poser ak+1 = ak et bk+1 = k et k+1 = k et k+1 = ak+1 + (1
) (bk+1 ak+1 ) :
Evaluer ' ( k+1 ) et aller à 4.
4- Remplacer k par k + 1 et aller à 1.
Exercice9
Soit ' : ]0; +1[! R, dé…nie par
' ( ) = 100

2

100 + 25

En partant de l’intervalle d’incertitude initial [a0 ; b0 ] = [0:2; 0:8] ; calculez
en appliquant la méthode du nombre d’or, une solution approchée de ,
solution optimale du problème
'(

) = min f' ( ) :

2 [0:2; 0:8]g :

L’algorithme s’arrêtera à l’itération k véri…ant bk

ak < 0:05

Solution Exercice 9
Itération0 : Démarrage
a0 = 0:2; b0 = 0:8;
= 0:61; 1
= 1 0:61 = 0:39; ` = 10
longueur f inale de [ak ; bk ]
)(b0 a0 ) = 0:2 + 0:39(0:6) = 0:434
0 = a0 + (1
a0 ) = 0:2 + 0:61(0:6) = 0:566
0 = a0 + ( )(b0
' ( 0 ) = ' (0:434) = 0:4356

4

=

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES49
' ( 0 ) = ' (0:566) = 0:4356
' ( 0 ) = ' ( 0 ) :Donc on supprime [ 0 ; b0 ] : Par conséquent
Itération1
a1 = a0 = 0:2
b1 = 0 = 0:566
b1 a1 = 0:566 0:2 = 0:366 : Donc
1 = 0 = 0:434
)(b1 a1 ) = 0:2 + 0:39(0:566 0:2) = 0:342 74
1 = a1 + (1
' ( 1 ) = ' (0:34274) = 2:473
' ( 1 ) = ' (0:434) = 0:4356
' ( 1) > ' ( 1)
Donc l’intervalle à supprimer est l’intervalle [a1 ; 1 ]
Itération2
a2 = 1 = 0:34274
b2 = b1 = 0:566
b2 a2 = 0:566 0:34274 = 0:223 26: Donc on calcule
2 = 1 = 0:434
a2 ) = 0:34274 + 0:61(0:566 0:34274) = 0:478 928 6
2 = a2 + ( )(b2
' ( 2 ) = ' (0:434) = 0:4356
' ( 2 ) = ' (0:4789286) = 0:0444
' ( 2) > ' ( 2)
Donc l’intervalle à supprimer est l’intervalle [a2 ; 2 ]
Itération3
a3 = 2 = 0:434
b3 = b2 = 0:566
b3 a3 = 0:566 0:434 = 0:132
Donc on calcule
3 = 2 = 0:478 928 6
a3 ) = 0:434 + 0:61(0:566 0:434) = 0:514 52
3 = a3 + ( )(b3
' ( 3 ) = ' (0:478 928 6) = 0:044 400 389 796
' ( 3 ) = ' (0:514 52) = 0:021 083 04
' ( 3) > ' ( 3)
Donc l’intervalle à supprimer est l’intervalle [a3 ; 3 ]
Itération4
a4 = 3 = 0:478 928 6
b4 = b3 = 0:566
b4 a4 = 0:566 0:478 928 6 = 0:087 071 4


Documents similaires


professeur benzine rachid cours optimisation sans contraintes tome1
professeur benzine rachid optimisation sans contraintes tome1
livres mathematique
gradient conjugue cas quadratique et non quadratique
examen s1 optimisation 2015 2016
methodes quasi newton


Sur le même sujet..