PrOFESSEUR BENZINE RACHID. OPTIMISATION SANS CONTRAINTES. TOME1 .pdf



Nom original: PrOFESSEUR BENZINE RACHID. 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 22/02/2016 à 04:18, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 590 fois.
Taille du document: 34.9 Mo (145 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
20 février 2016

1

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

1.5
1.6

1.7
1.8

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é . . . . . . . . . . . . . . .
Convergence des algorithmes et fonctions multivoques . . . .
1.6.1 Notion d’algorithme en optimisation . . . . . . . . .
1.6.2 Un modèle général des algorithmes : application multivoque . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.3 Convergence globale . . . . . . . . . . . . . . . . . .
1.6.4 Applications multivoques fermées . . . . . . . . . . .
1.6.5 Composition d’applications mutivoques . . . . . . . .
1.6.6 Le Théorème de Zangwill . . . . . . . . . . . . . . . .
Les modes de convergence . . . . . . . . . . . . . . . . . . .
EXERCICES . . . . . . . . . . . . . . . . . . . . . . . . . .

8

. 8
. 8
. 8
. 8
. 9
. 10
. 10
.
.
.
.
.
.
.

11
11
12
13
13
15
15

2 OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES 26
2.1 Introduction. Méthodes à directions de descente . . . . . . . . 26
2.1.1 Choix optimal du pas k . . . . . . . . . . . . . . . . . 27
2.2 Recherches linéaires exactes . . . . . . . . . . . . . . . . . . . 35
2.2.1 L’intervalle d’incertitude . . . . . . . . . . . . . . . . . 35
2.2.2 La méthode progressive-retrogressive ou ForwardBackward Algorithm . . . . . . . . . . . . . . . . . 36
2

TABLE DES MATIÈRES
2.2.3
2.3 Deux
2.3.1
2.3.2

3

Fonctions unimodales . . . . . . . . . . . . . . . . . . .
méthodes d’optimisation unidimensionnelle sans dérivées.
La méthode de dichotomie. . . . . . . . . . . . . . . . .
La méthode du nombre d’or ( golden section ). . . . . .

42
44
44
46

3 OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES
54
3.1 Introduction et rappels . . . . . . . . . . . . . . . . . . . . . . 54
3.2 Descente su¢ sante. Recherche linéaire inexacte d’Armijo . . . 62

3.3

3.4

3.5

3.6

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 . . .
Recherche linéaire inexacte de Goldstein . . . . . . . . . . .
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 L’Algorithme de Goldstein . . . . . . . . . . . . . . .
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 . . . . . . . . . . .
Théorèmes de convergence associés aux méthodes à directions
de descente et rechreches linéaires inexactes . . . . . . . . .
3.5.1 Algorithme général des directions de descente . . . .
3.5.2 Convergence globale . . . . . . . . . . . . . . . . . .
3.5.3 Le théorème de Zoudentijk . . . . . . . . . . . . . . .
Problèmes résolus . . . . . . . . . . . . . . . . . . . . . . . .

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

62
64
67
69
69
71
73
73
75
79
80
81
82

.
.
.
.
.

82
83
84
84
88

3.7 programmes en Fortran pour les recherches linéaires d’Armijo,
de Goldstein et de Wolfe . . . . . . . . . . . . . . . . . . . . . 101
3.7.1 Programme en Fortran pour la recherche linéaire d’Ar3.7.2
3.7.3

mijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
programme en Fortran pour la règle Goldstein . . . . . 102
Programme en fortran 77 pour la recherche linéaire de
wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

TABLE DES MATIÈRES
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.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 . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1 Changement de direction . . . . . . . . . . . . . . . .
4.5.2 Accéleration de la convergence . . . . . . . . . . . . .
4.6 Convergence de la méthode de la plus forte pente . . . . . .
4.6.1 Cas des recherches linéaires exactes . . . . . . . . . .
4.6.2 Cas de la recherche linéaire inexacte d’Armijo . . . .
4.6.3 Cas de la recherche linéaire inexacte de Wolfe . . . .
4.7 Programme en fortran 90 de la méthode de la plus forte pente
et tests numériques . . . . . . . . . . . . . . . . . . . . . . .
4.7.1 Programme en fortran 90 . . . . . . . . . . . . . . . .
4.7.2 Tests numériques . . . . . . . . . . . . . . . . . . . .
4.8 PROBLEMES . . . . . . . . . . . . . . . . . . . . . . . . . .
5 LA METHODE DE NEWTON
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . .
5.1.2 Etude de la convergence . . . . . . . . . . . . . . . .
5.1.3 Avantages et Inconvénients de la méthode de Newton
5.2 Programme en fortran et tests numériques . . . . . . . . . .

105
. 105
. 107
. 107
. 107
. 109
. 110
.
.
.
.
.
.
.
.
.

110
111
111
111
111
112
112
115
119

.
.
.
.

120
120
122
124

.
.
.
.
.

137
137
138
138
139
140

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^:

5

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
1.6.1

Convergence des algorithmes et fonctions
multivoques
Notion d’algorithme en optimisation

La plus part des méthodes de résolution d’optimisation sont de nature
itérative, c’est à dire qu’à partir d’un point initial x0 , elles engendrent une
suite in…nie x1 ; x2 ; ::::; xk ; :::dont on espère qu’elle converge vers la solution
optimale.
Dé…nition 3.
Un algorithme de résolution est un procédé itératif qui permet à partir
d’un point initial x0 d’engendrer la suite x0 ; x1 ; x2 ; ::::; xk ; :::
Un algorihtme est parfaitement dé…ni par la donnée de l’application a
qui à xk associe xk+1 = a(xk ): L’étude de la convergence de l’algorithme se
ramène à l’étude des propriétés de a.
Exemple1 :
a : x ! a(x) = x
rf (x)
a représente la méthode du gradient

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

1.6.2

Un modèle général des algorithmes : application
multivoque

Considérons le problème ( P ) :
( P ) : min f (x)
x2S

On sait qu’on peut générer plusieurs classes d’algorithmes qui ont pour
but de résoudre le problème ( P ) ou d’atteindre des points véri…ants les
conditions nécessaires d’optimalité. Il serait alors logique au lieu d’étudier la
convergenced’un algorithme, il serait préférable d’établir une théorie ou un
modéle assez général qui étudie la convergence d’une classe d’algorithmes au
lieu d’un seul algorithme.
Soient a1 ; a2 ; a3 ; ::::; ap des applications qui générent p algorithmes , c’est à
dire qu’à un point xk on associe les p points di¤érents a1 (xk ); a2 (xk ); a3 (xk ); ::::; ap (
xk ): C’est à dire qu’on peut considérer l’application qui à xk fait correspondre
A(xk ) = (a1 (xk ); a2 (xk ); a3 (xk ); ::::; ap ( xk )): Ceci conduit naturellement à un
modélé dans lequel les algorithmes sont représentés par des applications multivoques, c’est à dire des applications de Rn dans P( Rn ) qui à x 2 Rn fait
correspondre une partie de Rn :
D’une façon générale on notera :
m
A:X!Y
une application multivoque de X dans Y:
Exemple 2 :
minimiser x2
(P )
x 1
x
b = 1; a(x) = 21 (x + 1)
voir …gure 1.1

Exemple 3
minimiser x2
(P )
x 1
1; 21 (x + 1) si x 1
A(x) =
1
(x + 1); 1 si x < 1
2
voir …gure1.2

1.6.3

Convergence globale

Dé…nition 4
Nous dirons qu’un algorithme décrit par une application multivoque A, est
globalement convergent si quelque soit le point de départ x0 choisi, la suite

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
xk engendrée par xk+1 2 A( xk ) (ou une sous-suite) converge vers un point
satisfaisant les conditions nécessaires d’optimalité (ou solution optimale).
Notation :
x : x satisfait une condition nécessaire d’optimalité
=
:
ou x est solution optimale locale ou globale
s’appelle ensemble des solutions.

1.6.4

Applications multivoques fermées

Cette notion généralise la notion de continuité pour les fonctions univoques.
Dé…nition 5.
m
Soit A : X ! Y une application mutivoque.
On dit que A est fermée en x 2 X si et seulement si :
9
pour toute suite xk k2N ; xk ! x dans X =
et pour toute suite y k k2N ; y k ! y dans Y
=) y 2 A(x)
;
k
avec y 2 A(x)

A est dite fermée sur S
x 2 S:

X si et seulement si A est fermée en tout point

Remarque 1.
Si A est univoque continue, alors A est fermée.
En e¤et, soit A : X ! Y continu en x et soit
xk ! x dans X
A(xk ) = y k ! y dans Y

=) A(x) = y d’après la continuité de A.

Exemple 4 exemple d’application non fermée.
= f1g
3
+ 14 x; 1 + 12 x si x 2
2
A(x) =
1
(x + 1) si x < 2
2
voir …gure 1.3
Si x0 2; l’algorithme génère une suite xk qui tend vers 2.
Si x0 < 2; l’algorithme génère une suite xk qui tend vers 1.
Démontrons que A n’est pas fermée en x
e = 2:
k
k
En e¤et, considérons x tel que x = 2 k1 ! 2; A(2) = 2
1
A(xk ) = 21 2 k1 + 1 = 32 2k
! 32
3
6= A(2) A est non fermée au point x
e = 2:
2

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

1.6.5

Composition d’applications mutivoques

Dé…nition 6.
m
m
Soient A : X ! Y et B : Y ! Z( X; Y; Z fermés non vides). La
m
composée B A est l’application mutivoque C : X ! Z dé…nie par : C(x) =
[ B(y)

y2A(x)

Théorème 5 (composition des applications multivoques fermées).
m
m
Soit A : X ! Y et B : Y ! Z: On suppose que :
1- A est fermée en x 2 X et que B est fermée sur A(x):
2- toute suite y k telle que y k 2 A(xk ) avec xk ! x; admet une soussuite convergente.
Alors l’application multivoque C = B A est fermée en x:
Corollaire 1
m
Soit A : X ! Y une application univoque et B : Y ! Z une application
multivoque.
Si A est continue en x et si B est fermée en A(x), alors B A est fermée
en x.
Preuve :
Les conditions 1 et 2 du théorème 1 sont véri…ées car A est continue
en x, B est fermé en A(x) et y k est tel que y k = A(xk ); xk ! x donc
A(xk ) ! A(x) et y k est convergente. D’où B A est fermée.

1.6.6

Le Théorème de Zangwill

Dé…nition 7.
On dit que h : X ! R est une fonction de descente (relativement à une
application) si elle est continue et possède les propriétés suivantes :
1- x 2
= =) h(y) < h(x); (8y 2 A(x))
2- x 2 =) h(y) h(x); (8y 2 A(x))
Théorème 6.(Zangwill 1969)
Soit (P ) le problème d’optimisation suivant :
(P ) : min f (x)
x2X

et l’ensemble des solutions
m
Soit A : X ! X une application mutivoque et considérons une suite xk
engendrée par l’algorithme, c’est à dire véri…ant xk+1 2 A( xk ):

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Supposons que les trois conditions suivantes soient véri…ées :
C1- Les points xk sont tous contenus dans un ensemble compact K
X:
C2- Il existe une fonction de descente h.
C3- L’application multivoque A est fermée dans X n et 8x 2 X n
,A(x) =6= ;:
Alors :
pour tout x limite d’une sous-suite convergente de la suite xk ; on a
x 2 et h(xk ) ! h(x):
k!1
k2N

Exemple de la condition C1 :
Si f est une fonction de descente, on suppose que l’ensemble :
Xf (x0) ) = fx=x 2 X : f (x)

f (x0 )g est borné

Exemple de la condition C2 :
On peut prendre la fonction de descente égale à f (x) ou jOf (x)j :
Démonstration :
Soit xk k2N une suite engendrée par l’algorithme telle que xk k2N
il existe alors une sous-suite xk k2N1 convergente :
N1

x

K;

N

k k2N1

! x; x 2 K

k!1

La continuité de h donne :
k2N

h(xk ) !1 h(x)
k!1

8" > 0; 9 (") : 8k

Pour tout k

h(xk )

("); k 2 N1 on a h(xk )

h(x)

"

("); k 2 N on a :
h(x) = h(xk )

h(x ) + h(x )

h(x)

"

car h(xk ) h(x ) 0 pour tout k
(") et h(x ) h(x) ":
Montrons que x 2 :
Pour cela considérons la suite xk+1 k2N1 : Comme xk+1 k2N1
N1

existe alors une sous-suite xk+1

N

N1

k2N

k2N2

N2

N1

telle que xk+1 !2 x0
k!1

Donc :
k2N

xk !2 x
x

k!1
k+1 k2N2

! x0

k!1

N

K; il

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Supposons que x 2
= :
A étant fermée en x; on en déduit que x0 2 A(x):
k2N
k2N
Comme h(xk ) ! h(x) et en particulier : h(xk+1 ) !2 h(x0 ); l’inégalité
k!1

k!1

stricte h(y) < h(x) pour y = x0 n’est pas véri…ée. Ceci est en contrediction
avec la dé…nition de la fonction de descente donc x 2 :

1.7

Les modes de convergence

Dé…nition 8
Soit xk k2N une suite dans Rn convergeant vers x :
kxk+1 x k
1- Si lim sup xk x
=
< 1; on dit que xk k2N converge vers
k
k
k!1
x linéairement avec le taux :
xk x , la convergence est dite linéaire asympLorsque xk+1 x '
totique.
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.

1.8

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)).

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
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
c) Si @@xf2 (b
x; yb) : @@yf2 (b
x; yb)
(b
x; yb) < 0 alors (b
x; yb) n’est ni une
@x@y
solution minimale locale ni une solution maximale locale.
2
2
2
@2f
d) Si @@xf2 (b
x; yb) : @@yf2 (b
x; yb)
(b
x
;
y
b
)
= 0. On ne peut pas conclure ;
@x@y
l’étude doit continuer ; (b
x; yb) peut être une solution optimale ou ne pas l’être.

Solution Exercice 2
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
)
2
@x
@x@y
H (b
x; yb) =
@2f
@2f
(b
x; yb)
(b
x
;
y
b
)
@y@x
@y 2
Soit

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

Posons

a=

x
y

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

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

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

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

a) si 4 = b2
or
b2

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

4y 2
2

@2f
@2f
(b
x
;
y
b
)
:
(b
x; yb)
@x2
@y 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
2
2
2
@ f
@ f
@ f
(b
x; yb)
(b
x; yb) : 2 (b
x; yb)
2
@x@y
@x
@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
@2f
@2f
(b
x
;
y
b
)
:
(b
x; yb)
si
@x2
@y 2

alors

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

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

2

> 0 et si

x

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

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

et (b
x; yb) est une solution minimale locale stricte
b)
@2f
@2f
(b
x
;
y
b
)
:
(b
x; yb)
si
@x2
@y 2

alors

x y

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

H (b
x; yb)

x
y

2

> 0 et si

<0

et (b
x; yb) est une solution maximale locale stricte

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

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
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)

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

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
Trouvez tous les points stationnaires de
f : R2 ! R; f (x; y) = x2 + y 2
Solution exercice 4
(x; y) stationnaire si et seulement @f
(x; y) = 0 et @f
(x; y) = 0; c’est à
@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

@2f
@f
@ 2f
@ 2f
@f
(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
(x; y) H (b
x; yb)

x
y

H (b
x; yb) =

= (x; y)

2 0
0 2
2x
2y

= 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; yb) est semi dé…nie positive, mais (b
x; yb) 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

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
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)
2
@x
@x@y
=
H(x; y) =
@2f
@2f
(x;
y)
(x; y)
@y@x
@y 2

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)
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

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
On peut choisir par exemple
x
e=

On a bien sur

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
> 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.
f (e
x; ye) = f (e
x; 0) =

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.
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.

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
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
2
@x
@x@y
=
@2f
@2f
0 2
(0; 0) @y2 (0; 0)
@y@x
,

(x; y) H (0; 0)

x
y

= 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

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
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

4
3

Calculons
@2f
@x2

4 1
;
3 3

;

@2f
@y 2

4 1
;
3 3

et

@2f
@x@y

4 1
;
3 3

On a
8(x; y) 2 R2 :

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

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

1

Par conséquent
@2f
@x2

4 1
;
3 3

:

@2f
@y 2

4 1
;
3 3

@2f
@x@y

4 1
;
3 3

D’autre part :
@2f
@x2

4 1
;
3 3

= 2 > 0:

2

=4

1=3>0

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
4 1
;
3 3

Donc le point (b
x; yb) =

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

3

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

2

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

=0

9=

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

9<0

et (0; 0) n’est pas

@2f
@2f
(1;
1)
=
6;
(1; 1) =
@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

CHAPITRE 1. OPTIMISATION SANS CONTRAINTES. NOTIONS DE BASE ET CONDITION
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.
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

26

;

k

2 R+

(2)

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES27

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 EXACTES28
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 EXACTES29
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 EXACTES30
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 EXACTES31
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 EXACTES32
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 EXACTES33

'( ) = 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 EXACTES34
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 EXACTES35
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 EXACTES36
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 EXACTES37
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 EXACTES38
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 EXACTES39
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 EXACTES40
' ( 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 EXACTES41
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 EXACTES42
+ 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 EXACTES43
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 EXACTES44
(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 EXACTES45
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 EXACTES46

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 EXACTES47
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 EXACTES48
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 EXACTES49
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 ]



Documents similaires


professeur benzine rachid cours optimisation sans contraintes tome1
professeur benzine rachid optimisation sans contraintes tome1
gradient conjugue cas quadratique et non quadratique
tp n7
livres mathematique
methodes quasi newton


Sur le même sujet..