Professeur Benzine Rachid Cours Optimisation Sans Contraintes Tome1 PDF [PDF]

Zitiervorschau

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 40

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

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


'( ):

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

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

CHAPITRE 2. OPTIMISATION DANS R: RECHERCHES LINEAIRES EXACTES50 Donc on calcule 4 = 3 = 0:514 52 a4 ) = 0:478 928 6 + 0:61(0:087 071 4) = 0:532 042 154 4 = a4 + ( )(b4 ' ( 4 ) = ' (0:514 52) = 0:021 083 04 ' ( 4 ) = ' (0:532 042 154) = 0:102 669 963 295 971 6 ' ( 4) < ' ( 4) Donc l’intervalle à supprimer est l’intervalle [ 4 ; b4 ] Itération5 a5 = a4 = 0:478 928 6 b5 = 4 = 0:532 042 154 b5 a5 = 0:532 042 154 0:478 928 6 = 0:053 113 554 Donc 5 = 4 = 0:51452 )(b5 a5 ) = 0:4789286+0:39(0:053113554) = 0:499 642 886 5 = a5 +(1 06 ' ( 5 ) = ' (0:49964288606) = 0:000 012 753 036 614 232 36 ' ( 5 ) = ' (0:51452) = 0:02108304 ' ( 5) < ' ( 5) Donc l’intervalle à supprimer est l’intervalle [ 5 ; b5 ] Itération6 a6 = a5 = 0:478 928 6 b6 = 5 = 0:51452 b6 a6 = 0:51452 0:478 928 6 : 0:035 591 4 < 0:05 Donc l’algorithme s’arrête. On prend comme valeur approximative de ; le milieu de l’intervalle [a6 ; b6 ] 0:4789286 + 0:51452 a6 + b 6 = = 0:4967243 ' 2 2 Remarque La solution exacte est = 0:5000000 L’erreur commise est donc 0:5

0:4967243 = 0:003

Chapitre 3 OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES 3.1

Introduction et rappels

Soit f : Rn ! R: On concidè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)

Le sucusseur xk+1 de xk est obtenu comme suit : xk+1 = xk +

k dk

;

k

2 R+

(2)

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.

51

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES52 Il existe deux type de rechreches linéaires : i) les rechreches linéaire exactes. ii) les rechreches linéaire inexactes ou économiques. Soit f : Rn ! R di¤érentiable au point xk 2 Rn et dk 2 Rn véri…ant rf (xk )T dk < 0:

(3)

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

(4)

Notons Nous avons vu aux chapitres 1 et 2 que la condition (3) implique 9 > 0 : 8 2]0; [ f (xk + dk ) < f (xk )

(5)

c’est à dire 9 > 0 : 8 2]0; [ 'k ( ) < 'k (0) On a vu aussi au chapitre2(recherches linéaires exactes), qu’on peut choisir = 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 + dk : Ceci est possible si on impose à de véri…er la condition suivante : 8 2]0; +1[:

f (xk +

dk )

f (xk + dk )

(6)

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

8 2]0; +1[

(8)

2]0; +1[g

(9)

est solution optimale de : 'k (

) = minf'k ( ) :

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

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES53 Avantages des recherches linéaires exactes Le principal avantage des recherches linéaires exactes est de calculer optimal, c’est k = ; véri…ant 'k (

k)

En d’autres termes, si point xk au point xk + 8 2]0; +1 [: [f (xk )

= 'k (

) = minf'k ( ) :

k

2]0; +1[g)

= la fonction f décroit le mieux en passant du d = x dk ; c’est à dire k k k +

k

f (xk +

k dk )]

= [f (xk )

f (xk +

dk )]

[f (xk ) f (xk + dk )] (9bis)

Inconvénients des recherches linéaires exactes E¤ectuer une rechreche linéaire exacte à chaque itiration, est di¢ cilement réalisable en pratique et assez couteux en temps et en mémoire. Problème1 Quelle méthode de calcul de k ; pourrait on adopter pour remplacer les recherches linéaires exactes, tout en gardant l’essentiel des avantages des recherches linéaires exactes et éviter leurs inconvénients ? Réponse au problème1 Les nouvelles méthodes de calcul de k adoptées doivent véri…er le conditions suivantes : a) Le calcul de k doit être simple et peu couteux en temps et en mémoire. b) Sachant qu’on ne peut pas obtenir k = (celà exigerait le retour aux recherches linéaires exactes), on essaye donc de s’approcher le plus possible de : Les meilleurs choix de k ; sont les points k assez proches de : Ceci se traduit par les deux conditions suivantes : b1) la fonction f décroit strictement en passant du point xk au point xk + k dk ; i:e: f (xk + k dk ) < f (xk ) (10) b2) la fonction f décroit de façon su¢ sante en passant du point xk au point xk + k dk La décroissance su¢ sante dépend d’une recherche linéaire inexacte à une autre. Si on compare deux recherches linéaires inexactes, celle qui possede la plus grande décoissance sera la meilleure. En d’autre termes, la recherche linéaire inexacte dont le k sera le plus proche de ; sera la meilleure. Ceci nous permet de donner la dé…nition suivante :

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES54 Dé…nition1 Notons par (f; xk ; ; dk ) le taux de décroissance de f , en partant du point xk et arrivant au point xk + dk ; le nombre positif (f; xk ; ; dk ) suivant : (f; xk ; ; dk ) = f (xk ) f (xk + dk ) = 'k (0) 'k ( ) Supposons qu’on a deux recherches linéaires inexactes qu’on note RLI(1)(recherche linéaire inexacte1) et RLI(2)(recherche linéaire inexacte2). On dit que RLI(1) est meilleure que RLI(2) si pour tout nombre produit par la recherche linéaire inexacte RLI(1) et pour tout nombre produit par la recherche linéaire inexacte RLI(2) on a : (f; xk ; ; dk ) > (f; xk ; ; dk ) Remarque1 Il est clair que si une RLI(1) produit des points plus proches de ceux produits par RLI(2), alors RLI(1) est meilleure que RLI(2).

que

001

8 :jpg

f ig1 : representation de (

Comparaison de deux pas k et linéaires inexactes 0 k est meilleur que k si on a : (

k)

0 k;

> (

k)

( )

obtenus par deux recherches

0 k)

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES55 001

9 :jpg

f ig2 : (

k)

> (

0 k)

Avant d’aborder les trois recherches linéaires inexactes, étudions d’abord l’exemple suivant : Exemple1 Considérons la fonction f : R2 ! R, dé…nie par f (x; y) = x2 + y 2 On prend (xk ; yk )T = (3; 4) et dk =

rf (xk ; yk )

a) Calculons 'k ( ); 'k (0); '0k ( ) et le tableau de variation de 'k ( ) On a rf (x; y)T = (2x; 2y)

Si (xk ; yk )T = (3; 4) ; on aura dk = et

rf (xk ; yk ) = ( 6; 8)

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

6 ;4

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

2

100 + 25

8 ) 100 + 25

8 )

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES56 et '0k ( ) = 200

100

On a '0k ( ) = 0 () '0k ( ) > 0 () '0k ( ) < 0 ()

= 0:5 > 0:5 < 0:5

D’autre part lim 'k (x) =

lim 100

2

= +1

lim 100

2

= +1

! 1

! 1

!+1

!+1

lim 'k (x) =

d’où le tableau de variation suivant : 1

0

'( ) '( ) +1 &

0:5 +1 0 + 0 % +1

b) Trouvons le pas optimal k = : On a '0k ( ) = 0 ()

= 0:5

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

= 0:5 est une solution minimale locale

= 0:5 est aussi une valeur minimale globale stricte. En e¤et. D’après le tableau de variation, on a 8 2 R : 'k ( ) > 0 = 'k (0:5) Par conséquent

k

=

= 0:5 est une solution minimale globale. '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 (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)

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES57 (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) Trouvons le plus grand

> 0 tel que :

8 2]0; [: f [(xk ; yk ) + dk ] < f (xk ; yk ) (11) est équivalente à trouver le plus grand

(11)

> 0 tel que : (12)

'k ( ) < 'k (0)

D’après le tableau de variation, le plus grand > 0 véri…ant (12) est solution de l’équation : 'k (0) = 'k ( ): (13) En e¤et. 'k ( ) est strictement croissante sur ]0:5; +1[; donc 8 2] ; +1[: 'k ( ) > 'k ( ) = 'k (0) D’autre part, on a 8 2]0; [: 'k ( ) < 'k ( ) = 'k (0):

(14)

En e¤et. 'k ( ) est strictement décroissante sur ]0; 0:5[: Donc 8 2]0; 0:5[: 'k ( ) < 'k (0) = 'k ( ) D’autre part, 'k ( ) est strictement croissante sur ]0:5; [: Donc 8 2]0:5; [: 'k ( ) < 'k ( ) = 'k (0) Trouvons maintenant .

est solution de l’équation (13), i.e.

25 = 100

2

100 + 25 ()

2

= 0:

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-lineaires1 0:pdf

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES58 Voyons maintenant à travers le tableau suivant, les valeurs de donnent les meilleures décroissances f (x) = 100x2 100x + 25 25 36 = 11:0

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1

'k ( ) = f [(xk ; yk ) + dk )] 25 16 9 4 1 0 1 4 9 16 25 36

k(

) = f (xk ; yk )

2]0; 1[ qui

f [(xk ; yk ) + dk )]

0.00 9 16 21 24 25 : meilleure descente 24 21 16 9 0.00 -11

D’après le tableau précédent, la valeur = 0:5 est la valeur qui donne la meilleure decente k (0:5) = 25: Les valeurs de qui sont proches de = 0:5, donnent des descentes appreciables. Plus on s’apprche de = 0:5; plus la descente est meilleure. Pour = 0:4, la descente est k (0:4) = 24: Elle est meilleure que la descente obtenue au point = 0:2; k (0:2) = 16: Exercice 1 Dans cet exercice, on prend n = 1: Soit f : R ! R dé…nie par f (x) = x2 Considère la suite fxk gk2N dé…nie par x0 = 0 et xk+1 = xk +

k dk

avec dk =

signe (xk )

et k

= 2 + 3(2

k 1

)

1 Montrez par récurence que xk = ( 1)k (1 + 2 k )

(6)

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES59 et jxk+1 j < jxk j

(7)

f (xk+1 ) < f (xk )

(8)

2 Montrez que 3 Montrez que les sous suites paires fx2k gk2N et impaires fx2k+1 gk2N convergent chacune vers +1 et 1 respectivement. 4 On considère le problème de minimisation sans contraintes suivant : min f (x) = x2 : x 2 R

(9)

Trouvez la solution optimale globale du problème (9) en utilisant deux méthodes di¤érentes (dé…nition et condition nécéssaire et su¢ sante d’un problème d’optimisation convexe). 5 Quelle conclusion importante peut on tirer de ce problème.

3.2

Descente su¢ sante. Recherche linéaire inexacte d’Armijo

3.2.1

Principe de la méthode

Comme l’a montré l’exercice précédent, il ne su¢ t pas de choisir à chaque itération k; k tel que f (xk + k dk ) < f (xk ) pour que la suite fxk g converge vers la solution optimale ou vers un point stationnaire. En e¤et si la fonction décroit trés peu en passant du point xk vers le point xk+1 = xk + k dk ; la suite fxk g diverge ou peut converger vers un point qui n’a rien à voir avec la solution optimale. Pour éviter cet inconvénient, il faut imposer une condition caractérisant la notion de descente su¢ sante de la fonction. Il faut choissir k de sorte que la fonction f décroit de façon su¢ sante en passant du point xk au point xk+1 = xk + k dk : L’idée est que la diminution jugée su¢ sante soit proportionnelle à la taille du pas k : Ainsi plus le pas sera grand, plus la diminution de la fonction f sera grande. Donc si > 0; on désire que f (xk )

f (xk +

k dk )

k

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES60 ceci est équivalent à f (xk +

k dk )

k

f (xk )

f (xk )

k

ou encore f (xk +

k dk )

:

Le facteur ne peut pas être choisi de façon arbitraire. Surtout il doit varier d’une itération à l’autre. Il est plus approprié de dé…nir en fonction de la pente de la fonction au point xk dans la direction dk : En l’occurence, nous choisirons = rf (xk )T dk ; 0 < < 1 Dé…nition2 (diminution su¢ sante : condition d’Armijo) Soient f : Rn ! R une fonction di¤erentiable, xk 2 Rn ; dk 2 Rn une direction de descente, i.e. dk véri…ant : rf (xk )T dk < 0: On dit que le pas k > 0 véri…e la condition d’Armijo, si on a f (xk +

k dk )

f (xk ) +

k

T 1 rf (xk ) dk ;

0
0; on a '0k (0)

1

> '0k (0)

soit en rajoutant aux deux membres de l’égalité précédente la même quantité 'k (0); on obtient 'k (0) + '0k (0)

1

> 'k (0) + '0k (0)

(16)

> f (xk ) + rf (xk )T dk

(17)

ou encore f (xk ) +

T 1 rf (xk ) dk

Les relations (14), (15), (16) et (17) impliquent que pour 2]0+1[; la droite > 0 tel M0 se trouve au dessus de la droite TM0 : Par conséquent, il existe

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES62 que, pour tout 2]0; [; le graphe de 'k ( ) se trouve au dessous de la droite M0 : Ecrivons celà de façon analytique 8 2]0; [: 'k ( )

f (xk ) +

Utilisons le fait que 'k ( ) = f (xk + 8 2]0; [: f (xk +

k dk )

k dk );

T 1 rf (xk ) dk

(18)

(18) devient

f (xk ) +

T 1 rf (xk ) dk

(19)

(19) est exactement la condition "Armijo". Conclusion On peut prendre pour

k;

véri…ant la condition "Armijo", tout point

2

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES63 ]0; [ (voir f ig Armijo).

Remarque1 En general, on s’assure dans la règle d’Armijoo que k ne soit pas trop petit car celà va nuire à la convergence de l’algorithme qui pourrait converger prématurément vers un point qui n’est pas stationnaire. Celà se verra

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES64 explicitement dans l’algorithme suivant Algorihtme de la règle d’Armijo. Initialisation Choisir b 2 ]0; +1[ et 0 < 1 < 1: Calculez 'k (b ) = f (xk +b dk ); 'k (0) = f (xk ); '0k (0) = rf (xk )T dk < 0 et allez à Etape principale Etape principale Si 'k (b ) 'k (0) + b 1 '0k (0); choisir le plus grand entier n0 0 tel que : 'k (2n0 b )

'k (0) + 2n0 b

0 1 'k (0);

Sinon choisir le plus petit entier m0 'k Fin

b 2m0

'k (0) +

b 2m0

et prendre

k

0 tel que :

0 1 'k (0);

et prendre

k

= 2n0 b =

b 2m0

Dans le théorème suivant on va assurer l’existence du pas d’Armijo en posant quelques conditions sur la fonction 'k : Théorème1 Considérons la fonction 'k : R+ ! R;dé…nie par 'k ( ) = f (xk + dk ) Supposons que 'k est continue et bornée inférieurement. Si dk est une direction de descente en xk (rf (xk )T dk < 0) et si 1 2 ]0; 1[ ; alors l’ensemble des pas véri…ant la règle d’Armijo est non vide.

3.2.3

Contrainte des petits pas dans la règle d’Armijo

La condition (Armijo) nous permet une diminution su¢ sante de la fonction en s’assurant que la décroissance de la fonction f , en passant du point xk vers le point xk + k dk , soit au moins proportionnelle au point k ; c’est à dire T f (xk ) f (xk + k dk ) k rf (xk ) dk Mais si k devient trés petit, cette décroissance peut devenir petite aussi. Donc les petits pas k peuvent poser problème, comme le montre l’exemple suivant : Exemple1 Dans cet exemple, n = 1 et f : R ! R dé…nie par f (x) = x2

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES65 On prend x0 = 2;

k

=

1 2k+1

; dk =

1

On peut montrer facilement par récurence que : xk = 1 +

1 : k = 0; 1; 2; ::: 2k

Ceci étant, on a 2k+1 > 2k =)

1 2k+1


0, pour tout k: Puisque f (x) = x2 est strictement croissante sur R+ ; donc 8k : f (xk+1 ) < f (xk ) Par conséquent, il s’agit bien d’une méthode à directions de descente. Il est clair que lim xk = 1: k!1

D’autre part f (x) = x2 > 0 = f (0) : 8x 2 R Donc x = 0 est la solution optimale globale du problème min f (x) = x2 : x 2 R = f (0) Conclusion La suite fxk g véri…e bien la condition de descente : f (xk+1 ) < f (xk ); mais ne converge pas vers une solution optimale. D’ailleurs elle ne converge même pas vers un point stationnaire. Cette anomalie a été causée par les petits pas 1 f (xk+1 ); on obtient k ( k = 2k+1 ). Si on calcule la quantité f (xk ) 2

f (xk )

2

1 1 f (xk+1 ) = 1+ k 1 + k+1 2 2 1 1 1 1 = 1 + k 1 + 2k 1 + k + 2k+2 2 2 2 2 1 1 1 1 1 = + 2k + k !0 k 1 k 2k+2 k!1 2 2 2 2 2

Quand k devient tres grand, la décroissance de f devient presque nulle et ceci va perturber la convergence de xk vers une solution optimale ou vers un point stationnaire.

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES66

3.3

Recherche linéaire inexacte de Goldstein

Dans l’exemple1, la raison de l’echec de la méthode réside dans la dégénéréscence des pas k : Ceux ci, bien que strictement positifs, deviennent arbitrairement proches de zéro et la méthode ne peut plus progresser. On va donc rajouter une deuxième condition à la condition d’Armijo qui éliminerait les pas trop petits.

3.3.1

Principe

Supposons qu’à l’iteration k , on ait le point xk 2 Rn , le vecteur de descente dk 2 Rn (rf (xk )T :dk < 0) On cherche le pas k > 0 de Goldstein vérifant les deux conditions suivantes : f (xk +

1 2]0; [ 2

T k rf (xk ) dk ;

f 0 (xk ) +

k dk )

(Goldstein1)

et f (xk +

f 0 (xk ) + (1

k dk )

)

T k rf (xk ) dk ;

1 2]0; [ 2

(Goldstein2)

Si on note 'k ( ) = f (xk + dk ) alors (Goldstein 1) et (Goldstein 2) deviennent 'k (

k)

0 k 'k (0)

'k (0) +

(Goldstein1(bis))

et 'k (

k)

'k (0) + (1

)

0 k 'k (0)

(Goldstein2(bis))

(Goldstein1) assure une décroissance su¢ sante de f . Comme nous l’avons vu dans l’exemple1, les pas k trop petits sont nocifs pour la convergence. La suit {xk } pourrait converger prématurément vers un point x~ qui n’a rien à voir avec le problème d’optimisation. La condition ( Goldstein 2) élimine justement les pas k trop petits. Interprétation graphique (voir …g.Goldstein) < 0 =) 21 < 1 < 1: Donc a) 0 < < 12 =) 12 < 0
'0k (0) =) 'k (0)+ (1

)'0k (0) > 'k (0)+ '0k (0) (22)

Notons par : 0 1 : la droite de coé¢ cient directeur 'k (0) et passant par le point (0; 'k (0)) )'0k (0) et passant par le point 2 : la droite de coé¢ cient directeur (1 (0; 'k (0)) T : la tangente au graphe de 'k ( ), passant par le point (0; 'k (0)): On a '0k (0)g (23) 1 = f( ; y) : y = 'k (0) + 2

= f( ; y) : y = 'k (0) + (1

)'0k (0)g

T = f( ; y) : y = 'k (0) + '0k (0)g

(24) (25)

Les relations (21),(22),(23),(24) et (25) impliquent que : a) La droite 1 est au dessus de la droite 2 pour tout 2 R+ b) Les deux droites 1 et 2 sont au dessus de la tangente T , pour tout 2 R+ Notons par 1 l’abcisse du premier point d’intersection de 2 avec le graphe de 'k ( ) Notons par 2 l’abcisse du premier point d’intersection de 1 avec le graphe de 'k ( ) On a donc c) ]0; 2 [= f : véri…e (Goldstein1) g: Le graphe de 'k est au dessous de la droite 1 de coé¤écient directeur '0 (0) d) ] 1 ; +1[= f : véri…e (Goldstein2) g: Le graphe de 'k est au dessus de la droite 2 d’équation (1 )'0 (0)

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES68 e) ] 1 ; 2 [= f : véri…e (Goldstein1) et (Goldstein2) g: Le graphe de 'k est situé entre les deux droites 1 et 2 de coé¢ cients directeurs '0 (0) et (1 )'0 (0):

001

1 2:jpg

f ig:Goldstein

3.3.2

L’Algorithme de Goldstein

Principe de l’Algorithme L’ Algorithme essaye de trouver k 2] 1 ; 2 [ (voir …g Goldstein ). On demarre avec un intervalle [a0 ; b0 ] assez grand. On prend 0 2 [a0 ; b0 ] Si 0 véri…e Goldstein1 et Goldstein2 alors 0 2] 1 ; 2 [ et on s’arréte . Si 0 ne veri…é pas Goldstein1, alors 0 > 2 a1 + b 1 alors on prend b1 = 0 et a1 = a0 et 1 = 2 et on recommence avec 1 Si 0 ne veri…é pas Goldstein1, alors 0 < 1 a1 + b1 on prend a1 = 0 ; b1 = b0 et 1 = et on teste de nouveau 1 2 A l’itération k

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES69 ak + b k Supposons qu’on ait [ak ; bk ] et k = 2 Si k véri…e Goldstein1 et Goldstein2, k 2] 1 ; 2 [. Stop. Si k ne veri…é pas Goldstein1, alors k > 2 ak+1 + bk+1 On prend bk+1 = k , ak+1 = ak , k+1 = 2 On recommence avec l’intervalle [ak+1 ; bk+1 ] et k+1 Si k ne véri…e pas Goldstein2 alors

k


'k (0) +

'0k (0) =) '0k (

d)

> '0k (0)

(41)

(40) et (41) impliquent que g

Par conséquent

ne verif ie pas W olf e2 d verif ie W olf e2

véri…e : 8 9 '0k ( 1 ) = '0k (0) < = < 1 =) '0k ( ) < '0k (0) : ; > 1 =) '0k ( ) > '0k (0)

(42)

1

et on a par la suite : ]0; 2 [= f : véri…e (Wolfe1) g: ] 1 ; +1[= f : véri…e (Wolfe2) g:

(42)

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES75 ] 1;

2 [=

f :

véri…e (Wolfe1) et (Wolfe2) g:

Montrons maintenant que 2 ] 1; 2[ Théorème 3 Soit > 0 tel que '0k ( ) = 0: Alors il existe 0 < < 1 tel que véri…e (Wolfe1) et Wolfe2), i.e. 2 ] 1; 2[ Preuve On a '0k (0) < 0 = '0k ( ) =) '0k ( ) > '0k (0); donc véri…é wolfe (2) . 0 ' ( ) = 0 véri…é wolfe (1) car Si est su¢ sament petit (on prend en général = 10 4 ), alors la droite '0k (0)g est presque horizontale. Par conséquent 3 = f( ; y) : y = 'k (0) + on peut choisir l’intervalle ]0; 2 [ aussi grand que l’on veuille. Ceci implique qu’il existe 0 < < 1 su¢ samment petit de sorte que 2 ]0; 2 [: Donc véri…e (wolfe (1) ) et par la suite 2 ] 1 ; 2 [.

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES76

3.4.3

Rechreche linéaire inexacte de Wolfe-forte

Comme leur nom l’indique, les conditions de Wolfe-forte sont plus fortes que les conditions de Wolfe. En e¤et les conditions de wolfe-forte impliquent les conditions de Wolfe. Elles sont trés utilisées en théorie et les grands résultats de convergence ont été prouvés en utilisant des recherches linéaires inexactes de Wolf-forte. Dé…nition k véri…e les condition de Wolfe-forte si les deux conditions suivantes sont véri…eés : 'k (

k)

j'0k (

k )j

0 k 'k (0);

'k (0) + '0k (0);

0
0, poser k = 1 et aller à l’étape 1: Etape 1 : 1.1 si 'k ( k ) > 'k (0) + '0k (0) k , alors d;k+1 = k ; g;k+1 = g;k et aller à l’étape 2. 1.3 Sinon ('k ( k ) 'k (0) + '0k (0) k ) ; alors '0k (0) : STOP( = k ). 1.3.1 si '0k ( ) 1.3.2 sinon ('0k ( ) < '0k (0)) d;k+1 = d;k , g;k+1 = k et aller à l’étape 2. Etape 2 : si d;k+1 = +1 déterminer k+1 2] g;k+1 ; +1[ sinon déterminer k+1 2](1 ) g;k+1 + d;k+1 ; ) d;k+1 [ poser k = k + 1 et aller à l’étape 1.

> 1;choisir

g;k+1

+ (1

Théorème5 Considérons la fonction 'k : R+ ! R;dé…nie par 'k ( ) = f (xk + dk ) , 2 ]0; 1[ et 2 ] ; 1[ :Supposons que 'k et dk véri…ent les conditions suivantes : a) 'k est dérivable et bornée inférieurement sur R+ b) dk est une direction de descente en xk i:e: rf (xk )T dk < 0: Alors l’alogorithme de Fletcher-Lemaréchal calcule le pas de Wolfe : (Wolfe1)(Wolfe2), en un nombre …ni d’étapes.

3.5

Problèmes résolus

PROBLEME1 On considère la fonction f (x; y) = x2 + y 4 : On suppose qu’à l’itération k, on a le point (xk ; yk ) = (1; 1) et la direction dk =

rf (xk ; yk )

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES80 1) Calculez 'k ( ) = f (xk + dk ) ; '0k ( ); 'k (0); '0k (0) 2) Calculez

; solution optimale globale du problème min f'k ( ) :

2 ]0; +1[g = 'k (

)

3) Calculez le pas d’Armijo qu’on note Armijo , avec les données initiales suivantes : b = 1; 1 = 0:9 4) Calculez le pas de Goldstein qu’on note initiales suivantes : a0 = 0; b0 = 10100 ;

= 0:1;

5) Calculez l’intervalle de Goldstein [ 1 ; 8 2 [ 1;

2]

Goldstein ,

2]

0

avec les données

=1

: tel que

véri…e Goldstein1 et Goldstein2

:

6) Calculez le pas de Wolfe qu’on note W olf e , avec les données initiales suivantes : = 0:1; = 0:3; a0 = 0; b0 = 1099 ; 0 = 1 7) Calculez l’intervalle de Wolfe qu’on note [ 1 ; 8 2 [ 1;

2]

:

: tel que

véri…e Wolfe1 et Wolfe2

8) Calculez le pas de Wolfe forte qu’on note nées initiales suivantes : = 0:01;

2]

W olf e

= 0:02; a0 = 0; b0 = 0:4;

SOLUTION DU PROBLEME1 Réponse à la question1 Calcul de 'k ( ); '0k ( ); 'k (0); '0k (0) On a 'k ( ) = f [(xk ; yk ) + dk ] f (x; y) = x2 + y 4 rf (x; y) = (2x; 4y 3 ) dk = rf (xk ; yk ) = ( 2xk ; 4yk3 )

0

f orte ,

= 0:3

avec les don-

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES81 (xk ; yk ) = (1; 1) dk = rf (xk ; yk ) = ( 2; 4) (xk ; yk ) + dk = (1; 1) + ( 2; 4) = ( 2 + 1; 4 + 1) 'k ( ) = f [(x0 ; y0 ) + d0 ] = f ( 2 + 1; 4 + 1) = (1 2 )2 + (1 'k ( ) = 256 4 256 3 + 100 2 20 + 2 'k (0) = 2 '0k ( ) = 1024 3 768 2 + 200 20 '0k ( ) = rf [(xk ; yk ) + dk ]T :dk '0k (0) = rf [(xk ; yk )]T :dk = 20 < 0

4 )4

Réponse à la question2 Calcul de ; solution optimale globale du problème min f'k ( ) :

2 ]0; +1[g = 'k (

)

Puisque 2 ]0; +1[ ; donc est une solution optimale locale. Elle véri…e nécessairement '0k ( ) = 0: Calculons donc les points stationnaires de 'k ( ): '0k ( ) = 0 () 1024 3 768 2 + 200 20 = 0 L’équation précédente admet une seule solution réelle : ' 0:354 39 '00k ( ) = 3072 2 1536 + 200 '00k (0:35439) = 41: 476 419 891 2 > 0: Donc ' 0:354 39 est une solution minimale locale stricte. D’autre part, une étude du signe de la dérivée montre que 2 ] 1; 0:35439[ : '0k ( ) < 0 2 ]0:35439; +1[ : '0k ( ) > 0 Donc 2 ] 1; 0:35439[ : 'k ( ) est strictement décroissante 2 ]0:35439; +1[ : 'k ( ) est strictement croissante. et lim 'k ( ) = lim (256

4

) = +1

lim 'k ( ) = lim (256

4

) = +1

! 1

! 1

! 1

! 1

'k (0:35439) ' 0:115: On obtient le tableau de variation suivant x 1 0:35439 +1 '0k ( ) 0 + 'k ( ) & 0:115 %

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES82 D’après ce tableau de variation, on peut conclure 2 ] 1; 0:35439[ =) 2 ]0:35439; +1[ =)

< 0:35439 =) 'k ( ) > 'k (0:35439) > 0:35439 =) 'k ( ) > 'k (0:35439)

Par conséquent 8 2 ]0; +1[ ; Donc

6= 0:35439 : 'k ( ) > 'k (0:35439)

= 0:35439 est la solution optimale globale.

'k (

' 0:35439 ) ' 'k (0:35439) ' 0:11521

3) Réponse à la question3 : Calcul du pas d’Armijo : Armijo , avec les données initiales : b = 1; 1 = 0:9 D’après la question1, on a 'k ( ) = 256 4 256 3 + 100 2 20 + 2 f (x; y) = x2 + y 4 (xk ; yk ) = (1; 1) f (xk ; yk ) = f (1; 1) = 2:0 rf (x; y) = (2x; 4y 3 ) 2 krf (xk ; yk )k2 = k(2xk ; 4yk3 )k = 4x2k + 16yk6 = 20 Notons : 2 T k ( ) = f (xk ; yk ) + 1 rf (xk ; yk ) dk = f (xk ; yk ) 1 krf (xk ; yk )k 18 k( ) = 2 On démarre du point b = 1 Avec ces données, on a 'k (b ) = 'k (1) = 82:0 16:0 k (b ) = k (1) = On a 'k (b ) > k (b ): Alors on divise b pas 2 , on prend b 1 = 0:5 on obtient alors : 'k (b 1 ) = 'k (0:5) = 1:0 7:0 k (b 1 ) = k (0:5) = 'k (b 1 ) > k (b 1 ) alors on divise b 1 par 2 , on prend b 2 = 0:25 'k (b 2 ) = 'k (0:25) = 0:25 2: 5 k (b 2 ) = k (0:25) = 'k (b 2 ) > k (b 2 ) alors on divise b 2 par 2 , on prend b 3 =

'k (b 3 ) = 'k (0:125) = 0:625

0:25 2

= 0:125

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES83 k (b 3 )

= k (0:125) = 0:25 'k (b 1 ) > k (b 1 ) alors on divise b 3 par 2 , on prend b 4 = 'k (b 4 ) = 'k (0:0625) = 1: 082 031 25 k (b 4 ) = k (0:0625) = 0:875 'k (b 4 ) > k (b 4 ) alors on divise b 4 par 2 , on prend b 5 =

0:125 2

= 0:062 5

0:0625 2

= 0:031 25

'k (b 5 ) = 'k (0:03125) = 1: 465 087 890 625 k (b 5 ) = k (0:03125) = 1: 437 5 'k (b 5 ) > k (b 5 ) alors on divise b 5 par 2 , on prend b 6 =

0:03125 2

=

0:015 625 'k (b 6 ) = 'k (0:015625) = 1: 710 952 758 789 062 5 k (b 6 ) = k (0:015625) = 1: 718 75 'k (b 6 ) < k (b 6 ) alors on arrête et on prend b 6 = 0:015625 comme pas d’Armijo. Conclusion : Armijo = 0:015625 4) Réponse à la question4 : Calcul du pas Goldstein , avec les données initiales suivantes : a0 = 0; b0 = 10100 ; = 0:1; 0 = 1 On a déja calculé dans la question 3, la fonction 'k ( ) 'k ( ) = f [(x0 ; y0 ) + d0 ] = f [(x0 ; y0 ) + rf (x0 ; y0 )] 'k ( ) = 256 4 256 3 + 100 2 20 + 2 20 '0k ( ) = 1024 3 768 2 + 200 0 'k (0) = +2; 'k (0) = 20 Notons par g( ) et h( ) les 2 fonctions a¢ nes intervenant dans l’Algorithme de Goldstein g( ) = 'k (0) + '0k (0) = 2 2 h( ) = 'k (0) + (1 )'0k (0) = 2 18 ETAPE1 On démarre avec 0 = 1; 'k ( 0 ) = 'k (1) = 82 g( 0 ) = g(1) = 0:0 'k ( 0 ) > 'k (0) + 0 '0k (0) = g( 0 ) ) 0 ne véri…é pas Goldstein1 Poser a1 = a0 = 0; b1 = 0 = 1 et allez à ETAPE4 ETAPE4 Calculer a1 + b 1 = 0:5; Poser k = 1 et allez à ETAPE2 1 = 2 ETAPE2 'k ( 1 ) = 'k (0:5) = 1:0

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES84 'k (0) + 1 '0k (0) = g( 1 ) = g(0:5) = 1:0 'k ( 1 ) = 'k (0) + 1 '0k (0) ) 1 = 0:5 véri…é Goldstein1. Allez à ETAPE3 ETAPE 3 'k ( 1 ) = 'k (0:5) = 1:0 'k (0) + 1 (1 )'0k (0) = h( 1 ) = h(0:5) = 7:0 'k ( 1 ) > 'k (0) + 1 (1 )'0k (0) Donc 1 = 0:5 véri…é Goldstein2 Stop = 1 = 0:5 Conclusion goldstein = 0:5 5) Réponse à la question5 : Calcul de l’intervalle de Goldstein [ 1 ; 8 2 [ 1;

2]

2]

tel que :

véri…e Goldstein1 et Goldstein2

:

18 avec 2 est l’abcisse du point d’intersection de la droite h( ) = 2 le graphe de 'k ( ) = 256 4 256 3 + 100 2 20 + 2. Donc 2 est solution de l’équation h( ) = 'k ( ), ce qui donne l’équation : 2

18 = 256

4

256

3

+ 100

2

20 + 2

ou encore 256

4

256

3

2

+ 100

2 = 0:

La seule solution dans R+ est 2

' 2:111

2 avec le 1 est l’abcisse du point d’intersection de la droite g( ) = 2 graphe de 'k ( ) = 256 4 256 3 + 100 2 20 + 2. Donc 1 est solution de l’équation g( ) = 'k ( ), ce qui donne l’équation : 2

2 = 256

4

256

3

+ 100

2

20 + 2

ou encore 256

4

256

3

+ 100

La seule solution dans R+ est 1

= 0:5

2

18 = 0:

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES85 Donc [ 1;

2]

= [0:5 ; 2:111]

6) Réponse à la question6 : Calcul du pas W olf e , avec les données initiales suivantes : = 0:3; a0 = 0; b0 = 1099 ;

= 0:1;

0

=1

Etape1 : Initialisation On a déja calculé dans la question 3, la fonction 'k ( ) 'k ( ) = f [(x0 ; y0 ) + d0 ] = f [(x0 ; y0 ) + rf (x0 ; y0 )] 'k ( ) = 256 4 256 3 + 100 2 20 + 2 20 '0k ( ) = 1024 3 768 2 + 200 'k (0) = +2; '0k (0) = 20 Notons par k( ) et q( ) les 2 fonctions intervenant dans l’Algorithme de Wolfe k( ) = 'k (0) + '0k (0) = 2 2 (fonction a¢ ne intervenant dans la condition Wolfe1) q( ) = '0k (0) = 0:3 ( 20) = 6:0 (fonction constante intervenant dans la condition Wolfe2) Etape2 : Tester Wolfe1 pour 0 = 1 'k ( 0 ) = 'k (1) = 82:0 'k (0) + 0 '0k (0) = k( 0 ) = k(1) = 0:0 'k ( 0 ) > 'k (0) + 0 '0k (0) =) (W olf e1) n’est pas véri…ée 0 On pose a1 = a0 = 0; b1 = 0 = 1 [a1 ; b1 ] = [0; 1] : Aller à Etape 4 Etape 4 : Calcul de

1

0+1 a1 + b 1 = = 0:5 2 2 k = 0 + 1 = 1: Aller a Etape 2(bis) 1

=

Etape2 (bis) tester Wolfe(1) pour 1 = 0:5 'k ( 1 ) = 'k (0:5) = 1:0 'k (0) + 1 '0k (0) = k( 1 ) = k(0:5) = 1:0 'k ( 1 ) = 'k (0) + 1 '0k (0) =) (W olf e1) est véri…ée pour Aller à Etape3

1

= 0:5

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES86 Etape3 : Tester Wolfe(2) pour 1 = 0:5 Pour tester Wolfe2, on a besoin des expressions de '0k ( ) et de q( ) = 0 'k (0): On a 20 '0k ( ) = 1024 3 768 2 + 200 0 0 'k ( 1 ) = 'k (0:5) = 16 '0k (0) = 6:0 '0k ( 1 ) > '0k (0) =) (W olf e2) est verif iee pour 1 = 0:5 L’Algorithme s’arrête Conclusion W olf e = 0:5 7) Réponse à la question7 : Calcul de l’intervalle de Wolfe [ 1 ; 2 ] tel que : 8 2 [ 1;

2]

:

véri…e Wolfe1 et Wolfe2

Considérons la tangente au graphe de coé¢ cient directeur '0k (0) '0k (0) = 0:3 ( 20) = 6:0 On va chercher quel 1 > 0 qui véri…e : '0k ( 1 ) = 6 Résolvons donc l’équation : '0k ( ) = 6; c’est à dire : 1024

3

768

2

+ 200

20 =

6

Cette équation admet une seule solution réelle ' 0:108 98: Donc 1 ' 0:10898 On a '0k ( 1 ) = 6 'k ( 1 ) = 'k (0:108 98) = 0:712 829 048 998 121 512 96 y 0:712 709 065 2 = 6(x 0:10898) l’équation de la tangente au graphe de 'k ( ); de coé¢ cient directeur '0k (0) et qui passe par le point ( 1 ; 'k ( 1 )) est f( ; y) : y 'k ( 1 ) = '0k ( 1 )( 1 )g = f( ; y) : y 0:71282 = 6( 0:10898)g ( ; y) : y = 6 + 1:3667 Conclusion : 1 = 0:108 98; L’équation de la tangente au point y = 6 + 1:3667 Calcul de 2 Considérons la droite d’équation y = 'k (0) +

'0k (0) = 2 + (0:1 ( 20)) = 2

2

1

est

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES87 est l’abscisse du point d’intersection de 'k ( ) et de la droite y = 2 c’est à dire solution de l’équation : 2

'k ( ) = 2

2 () 256

4

256

3

+ 100

2

20 + 2 = 2

2 ;

2

Cette équation admet une seule solution réelle = 0:5 dans l’intervalle ]0; +1[ Conclusion : 2 = 0:5 Conclusion générale : L’intervalle dans lequel se trouve véri…ant (Wolfe1) et (Wolfe2) est : [ 1 ; 2 ] = [0:1 ; 0:5] Remarque : La solution optimale = 0:354 se trouve dans l’intervalle [ 1 ; 2 ] = [0:1; 0:5] 8) Réponse à la question8 Calcul du pas W olf e f orte , avec les données initiales suivantes : = 0:01;

= 0:02; a0 = 0; b0 = 0:4;

0

= 0:3

Remarquons que 0 < < < 1: Donc les conditions de Wolfe sont bien véri…ées. Calcul du pas W olf e f orte , avec les données initiales suivantes : = 0:01;

= 0:02; a0 = 0; b0 = 0:4;

0

= 0:3

Etape1 : Initialisation On a déja calculé dans le problème1, la fonction 'k ( ) 'k ( ) = f [(x0 ; y0 ) + d0 ] = f [(x0 ; y0 ) + rf (x0 ; y0 )] 'k ( ) = 256 4 256 3 + 100 2 20 + 2 '0k ( ) = 1024 3 768 2 + 200 20 'k (0) = +2; '0k (0) = 20 '0k (0) = (0:01) ( 20) = 0:2 '0k (0) = (0:02) ( 20) = 0:4 Notons par g( ) et h( ) et k( ) les 3 fonctions intervenant dans l’Algorithme de Wolfe-forte g( ) = 'k (0) + '0k (0) = 2 0:2 (fonction a¢ ne intervenant dans la condition Wolfe-forte1) g( ) = 2 0:2 h( ) = '0k (0) = 0:4 (fonction constante intervenant dans la condition Wolfe2) k( ) = '0k (0) = 0:4

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES88 Etape2 : Tester Wolfe-forte1 pour 'k ( 0 ) = 'k (0:3) = 0:161 6 g( 0 ) = g(0:3) = 1: 94 'k ( 0 ) < 'k (0) + 0 '0k (0) =) (W olf e

0

= 0:3

f orte1) est véri…ée pour

0

=

0:3 Aller à Etape3 Etape3 : Tester Wolfe-forte(2) pour 0 = 0:3 Pour tester Wolfe-forte2, on a besoin des expressions de '0k ( ) et de h( ) = '0k (0) et de k( ) = '0k (0): On a 0 3 2 'k ( ) = 1024 768 + 200 20 3 2 d( ) = 1024 768 + 200 20 d(0:3) = 1: 472 '0k ( 0 ) = '0k (0:3) = 1:472 '0k (0) = 0:4 '0k (0) = 0:4 Wolfe-forte(2) n’est pas véri…ée pour 0 = 0:3 car on a '0k (0:3) =

1:472 < '0k (0) =

0:4

L’Algorithme continue. Posez a1 = 0 = 0:3; b1 = b0 = 0:4 et aller à Etape4 Etape4(calcul de 1 ) 1 = 0:4+0:3 = 0:35 Calculer 1 = a1 +b 2 2 Allez à Etape2(bis) Etape2(bis) : Tester Wolfe-forte1 pour 1 = 0:35 'k ( 1 ) = 'k (0:35) = 0:115 6 g( 1 ) = g(0:35) = 1: 93 'k ( 1 ) < 'k (0) + 1 '0k (0) =) (W olf e f orte1) est véri…ée pour 1 Aller à Etape3 (bis) Etape3(bis) : Tester Wolfe-forte(2) pour 1 = 0:35 On a '0k ( 1 ) = '0k (0:35) = 0:176 '0k (0) = 0:4 '0k (0) = 0:4 Wolfe-forte(2) est véri…ée pour 1 = 0:35; car on a '0k (0) =

'0k (0:35) =

0:4

0:176

L’Algorithme s’arrête et W olf e f orte

=

1

= 0:35

'0k (0) = 0:4

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES89 PROBLEME2 On considère la fonction f (x; y) = x2 + y 4 : 1) Calculez le pas de Wolfe W olf e avec les données initiales suivantes : Paramètres de Wolfe : (x0 ; y0 ) = (1; 1); = 0:1; = 0:3; a0 = 0; b0 = 99 10 ; 0 = 10 2) En partant du point initial (x0 ; y0 ) = (1; 1); calculez (x1 ; y1 ) = (x0 ; y0 )

W olf e rf

(x0 ; y0 )

3) Comparez les résultats obtenus avec les résultats obtenus au problème1 SOLUTION DU PROBLEME2 Il est important de remarquer que dans le problème2, 0 = 10 1) Réponse à la question1 Calcul du pas W olf e avec 0 = 10 Etape1 Initialisation On prend 0 = 10; a0 = 0; b0 = 1099 ; = 0:1; = 0:3; k = 0: Calcul de '( ); '0 ( ); '(0); '0 (0) '( ) = f [(x0 ; y0 ) + d0 ] f (x; y) = x2 + y 4 rf (x; y) = (2x; 4y 3 ) d0 = rf (x0 ; y0 ) = ( 2x0 ; 4y03 ) (x0 ; y0 ) = (1; 1) d0 = rf (x0 ; y0 ) = ( 2; 4) (x0 ; y0 ) + d0 = (1; 1) + ( 2; 4) = ( 2 + 1; 4 + 1) '( ) = f [(x0 ; y0 ) + d0 ] = f ( 2 + 1; 4 + 1) = (1 2 )2 + (1 4 )4 '( ) = 256 4 256 3 + 100 2 20 + 2 '(0) = 2 '( 0 ) = '(10) = 2313 802 '0 ( ) = ( ) = 1024 3 768 2 + 200 20 0 T ' ( ) = rf [(x0 ; y0 ) + d0 ] :d0 '0 (0) = 20 '0 ( ) = 0 () 1024 3 768 2 + 200 20 = 0 () [ = 0:354 39] '( ) = min '( ) : 2 [0; +1[ = '(0:354 39) = 0:115 21 Calcul de [ 1 ; 2 ] : intervalle dans lequel se trouve véri…ant (Wolfe1) et (Wolfe2) Considérons la tangente au graphe de coé¢ cient directeur '0 (0) '0 (0) = 0:3 ( 20) = 6:0 On va chercher quel 1 > 0 qui véri…e : '0 ( 1 ) = 6

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES90 Résolvons donc l’équation : '0 ( ) = 1024

3

768

2

6; c’est à dire :

+ 200

20 =

6

1024 3 768 2 + 200 20 = 6, Solution is : [ = 0:108 98] '(0:108 98) = 0:712 829 049 0 y 0:712 709 065 2 = 6(x 0:10898) l’équation de la tangente est y=

6x + 1:366589

Conclusion : 1 = 0:108 98 Calcul de 2 Considérons la droite d’équation '0 (0) = 2 + (0:1 ( 20)) = 2

y = '(0) +

2

est l’abscisse du point d’intersection de '( ) et de la droite y = 2 c’est à dire solution de l’équation : 2

'( ) = 2

2 () 256

4

256

3

+ 100

2

20 + 2 = 2

2 ;

2

256 4 256 3 + 100 2 20 + 2 = 2 2 , Solution is : [ = 0:5] Conclusion : 2 = 0:5 Conclusion générale : L’intervalle dans lequel se trouve véri…ant (Wolfe1) et (Wolfe2) est : [ 1 ; 2 ] = [0:1; 0:5] Remarque : La solution optimale = 0:354 se trouve dans l’intervalle [ 1 ; 2 ] = [0:1; 0:5] Etape2 : Tester Wolfe1 pour 0 = 10 '( 0 ) = '(10) = 2313 802 '(0) + 0 '0 (0) = '(0) + (0:1) (10) ( 20) = 18:0 '( 0 ) > '(0) + 0 '0 (0) =) (W olf e1) n’est pas véri…ée =) 0 > 2 On pose a1 = a0 = 0; b1 = 0 = 10 [a1 ; b1 ] = [0; 10] : Aller à Etape 4 Etape 4 : Calcul de

1

0 + 10 a1 + b 1 = =5 2 2 k = 0 + 1 = 1: Aller a Etape 2(bis) 1

=

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES91 Etape2 (bis) tester Wolfe(1) pour

1

=5

'( 1 ) = '(5) = 130 402 '(0) + 1 '0 (0) = '(0) + (0:1) (5) ( 20) = 8:0 '( 1 ) > '(0) + 1 '0 (0) =) (W olf e1) n’est pas véri…ée =) On pose a2 = a1 = 0; b2 = 1 = 5 [a2 ; b2 ] = [0; 5] : Aller à Etape 4(bis) Etape 4(bis) : Calcul de

1

>

2

2

>

2

3

>

2

2

a2 + b 2 0+5 = = 2:5 2 2 k = 1 + 1 = 2: Aller a Etape 2(tris) 2

=

Etape2 (tris) tester Wolfe(1) pour

2

= 2:5

'( 2 ) = '(2:5) = 6577:0 '(0) + 2 '0 (0) = '(0) + (0:1) (2:5) ( 20) = 3:0 '( 2 ) > '(0) + 2 '0 (0) =) (W olf e1) n’est pas véri…ée =) On pose a3 = a2 = 0; b3 = 2 = 2:5 [a3 ; b3 ] = [0; 2:5] : Aller à Etape 4(tris) Etape 4(tris) : Calcul de

3

0 + 2:5 a3 + b 3 = = 1:25 2 2 k = 2 + 1 = 3: Aller a Etape 2(quatro) 3

=

Etape2 (quatro) tester Wolfe(1) pour

3

= 1:25

'( 3 ) = '(1:25) = 258: 25 '(0) + 3 '0 (0) = '(0) + (0:1) (1:25) ( 20) = 0:5 '( 3 ) > '(0) + 3 '0 (0) =) (W olf e1) n’est pas véri…ée =) On pose a4 = a3 = 0; b4 = 3 = 1:25 [a4 ; b4 ] = [0; 1:25] : Aller à Etape 4(quatro) Etape 4(quatro) : Calcul de 4

=

4

a4 + b 4 0 + 1:25 = = 0:625 2 2

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES92 k = 3 + 1 = 4: Aller a Etape 2(cinquo) Etape2 (cinquo) tester Wolfe(1) pour

4

= 0:625

'( 4 ) = '(0:625) = 5: 125 '(0) + 4 '0 (0) = '(0) + (0:1) (0:625) ( 20) = 0:75 '( 4 ) > '(0) + 4 '0 (0) =) (W olf e1) n’est pas véri…ée =) On pose a5 = a4 = 0; b5 = 4 = 0:625 [a5 ; b5 ] = [0; 0:625] : Aller à Etape 4(cinquo) Etape 4(cinquo) : Calcul de

4

>

2

5

a5 + b 5 0 + 0:625 = = 0:3125 2 2 k = 4 + 1 = 5: Aller a Etape 2(sixo) 5

=

Etape2 (sixo) tester Wolfe(1) pour

5

= 0:3125

'( 5 ) = '(0:3125) = 0:144 53 '(0) + 5 '0 (0) = '(0) + (0:1) (0:3125) ( 20) = 1: 375 '( 5 ) < '(0) + 5 '0 (0) =) (W olf e1) est véri…ée pour =) 5 < 2

5

= 0:3125

Aller à Etape3 Etape3 : Tester Wolfe(2) pour 5 = 0:3125 '0 ( 5 ) = '0 (0:3125) = 1:25 '0 (0) = 0:3 ( 20) = 6:0 '0 ( 5 ) > '0 (0) =) (W olf e2) est verif iee pour

5

= 0:3125

CONCLUSION =

5

= 0:3125

et (x1 ; y1 ) = (x0 ; y0 ) + d0 = (1; 1) + (0:3125) ( 2; 4) = (0:375 ; 0:25) f (x0 ; y0 ) = f (1; 1) = 2 f (x1 ; y1 ) = f (0:375 ; 0:25) = 0:144 53 f (x1 ; y1 ) < f (x0 ; y0 )

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES93 Il y’a décroissance de la fonction en passant du point (x0 ; y0 ) au point (x1 ; y1 ): Trouvons l’équation de la droite de coé¢ cient directeur '0 (0) = 6:0 et tangente au graphe au point 1 = 0:108 98: L’équation de cette droite sera de la forme: y = 6 +b La droite passe par le point ( 1 ; '( 1 )) = (0:10898; 0:71283): Donc 0:71283 =

6 (0:10898) + b

Donc b = 0:71283 + 6 0:10898 = 1: 366 7 Finalement y=

6 + 1:3667

PROBLEME3 On considére la fonction f (x; y) = x2 + y 2 ; (x0 ; y0 ) = (1; 1), d0 = rf (x0 ; y0 ): Calculez le pas de Wolfe forte W olf e f orte avec les paramètres suivants : = 0:01; = 0:02; a0 = 0; b0 = 0:4; 0 = 0:3 SOLUTION DU PROBLEME3

3.6 3.6.1

programmes en Fortran pour les recherches linéaires d’Armijo, de Goldstein et de Wolfe Programme en Fortran pour la recherche linéaire d’Armijo

c********************************************** Programme en fortran 77 d’Armijo c********************************************** real x(2),xp(2),g(2),gp(2),f0,alph,f,p,s,a,b,pf,t,y,phopt integer i,k,test,n sig=0.3 ;ro=0.1 ;b=10000000 ;alph=10 ;test=0 ;k=0 print*,’le dimontion n=’;read*,n do i=1,n print*,’x0(’,i,’)=’;read*, xp(i) end do 10 if (test==0.and.k.le.10) then call fonc(f0,gp,xp) do i=1,n x(i)=xp(i)-alph*gp(i) end do call fonc(f,g,x) ;p=0 do i=1,n p=p+gp(i)*gp(i) end do

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES94 s=f0-ro*alph*p if (f.gt.s) then b=alph else phopt=alph ;test=1 endif print*,’alpha(’,k,’)=’, alph ;alph=b/2 ;k=k+1 go to 10 end if print*,’alpha optimal=’, phopt end c************************************* subroutine fonc(f,g,x) real f,g(2),x(2) f=(x(1))**2+(x(2))**4 ;g(1)=2*x(1) ;g(2)=4*(x(2))**3 end c************************************* c**************************************

3.6.2

programme en Fortran pour la règle Goldstein

c********************************************* Programme en fortran 77 de Goldschtien c******************************************** real x(2),xp(2),g(2),gp(2),f0,alph,f,p,s,a,b,pf,t,y,phopt integer i,k,test,n ro=0.1 ;delt=0.3 ;b=10000000 ;alph=10 ;test=0 ;k=0 print*,’le dimontion n=’;read*,n do i=1,n print*,’x0(’,i,’)=’;read*, xp(i) end do 10 if (test==0.and.k.le.1000) then call fonc(f0,gp,xp) do i=1,n x(i)=xp(i)-alph*gp(i) end do call fonc(f,g,x) ;p=0 do i=1,n p=p+gp(i)*gp(i) end do s=f0-ro*alph*p ;y=f0-delt*alph*p if (f.gt.s) then b=alph else if (f.lt.y) then a=alph else phopt=alph ;test=1 endif endif print*,’alpha(’,k,’)=’, alph ;alph=(a+b)/2 ;k=k+1 go to 10 end if print*,’alpha optimal=’, phopt end c******************************* subroutine fonc(f,g,x)

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES95 real f,g(2),x(2) f=(x(1))**2+(x(2))**4 ;g(1)=2*x(1) ;g(2)=4*(x(2))**3 end c************************************ c************************************

3.6.3

Programme en fortran 77 pour la recherche linéaire de wolfe

c************************************ Programme en fortran 77 de wolfe c************************************ real x(2),xp(2),g(2),gp(2),f0,alph,f,p,s,a,b,pf,t,y,phopt integer i,k,test,n sig=0.3 ;ro=0.1 ;b=10000000 ;alph=10 ;test=0 ;k=0 ;print*,’le dimontion n=’ read*,n do i=1,n print*,’x0(’,i,’)=’; read*, xp(i) end do 10 if (test==0.and.k.le.10) then call fonc(f0,gp,xp) do i=1,n x(i)=xp(i)-alph*gp(i) end do call fonc(f,g,x) ;p=0 do i=1,n p=p+gp(i)*gp(i) end do s=f0-ro*alph*p if (f.gt.s) then b=alph else pf=0 do i=1,n pf=pf+g(i)*gp(i) end do t=-pf ;y=sig*(-p) if (t.lt.y) then a=alph else phopt=alph ;test=1 endif endif print*,’alpha(’,k,’)=’, alph ;alph=(a+b)/2 ;k=k+1 go to 10 end if print*,’alpha optimal=’, phopt ;x=xp end c*********************** subroutine fonc(f,g,x) real f,g(2),x(2) f=(x(1))**2+(x(2))**4 ;g(1)=2*x(1) ;g(2)=4*(x(2))**3 end c**************************

CHAPITRE 3. OPTIMISATION DANS R: RECHERCHES LINEAIRES INEXACTES96 c***************************

Chapitre 4 METHODE DE LA PLUS FORTE PENTE 4.1

Introduction

Cette méthode fut découverte par Cauchy en 1847. Il est naturel de se demander l’origine ou la justi…cation d’une telle appelation (méthode de la plus forte pente). Considérons un point xk 2 Rn ; si rf (xk ) 6= 0; alors la direction dk = rf (xk ) est une direction de descente (voir Chapitre1) Le Théorème qui suit va nous montrer que c’est en fait la meilleure direction de descente. En d’autres termes la décroissance de la fonction sera la plus forte en suivant la direction : rf (xk ): Théorème1 Supposons que f : Rn ! R; soit di¤érentiable au point x, et supposons que rf (x) 6= 0: Considérons le problème optimal M inimiser f 0 (x; d) kdk 1

où f 0 (x; d) est la dérivée directionnelle de f au point x et dans la direction d. Alors La solution optimale de ce problème est donnée par d~ =

rf (x) krf (x)k

Preuve Puisque f 0 (x; d) = lim

f (x + d)

!0+

97

f (x)

= rf (x)t d:

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE

98

Notre problème revient donc à minimiser rf (x)t d dans fd : kdk L’inégalité de shwartz donne rf (x)t d

Si

krf (x)k kdk :

rf (x)t d

on a bien sur

rf (x)t d

Si

rf (x)t d

1; on a

krf (x)k kdk

Donc : 8d : kdk

rf (x)t d

0;

krf (x)k kdk :

krf (x)k )

1 on a

D’autre part on a :

0;

krf (x)k kdk ;

Par conséquent on a toujours Pour kdk

(1)

krf (x)k kdk :

rf (x)t d

(1) implique que

1g :

rf (x)t d

krf (x)k kdk

krf (x)k :

krf (x)k :

d~ = 1 et d~ véri…e :

rf (x)t d~ = rf (x)t (

rf (x) )= krf (x)k

krf (x)k :

Interprétation du théorème1 : Nous allons à partir du théorème 7.1 donner une idée intuitive sur l’appelation méthode de la plus forte pente. En e¤et d’après le théorème1 on a : ~ : 8d; kdk 1: f 0 (x; d) f 0 (x; d) Soit en utilisant la dé…nition de la dérivée directionnelle. ~ f (x) f (x + d) f (x) f (x + d) lim lim : !0+

!0+

Cette dernière inégalité implique qu’il existe > 0 tel que h i ~ f (x) [f (x + d) f (x)] f (x + d) 0; 8 2 ]0; + [ ; ou encore

f (x + d)

~ f (x + d);

8 2 ]0; + [ et 8d; kdk

1:

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE

4.2

99

Algorithme de la méthode de la plus forte pente

Cet algorithme est tres simple.

Algorithme de la méthode de la plus forte pente Etape intiale Choisir un " > 0: Choisir un point initial x1 : Poser k = 1 et aller à l’étape principale. Etape principale Si krf (x)k < " stop. Sinon poser dk = rf (xk ) et soit k la solution optimale de la recherche linéaire exacte suivante M in ff (xk + dk );

> 0g :

ou k obtenue par une recherche linéaire inexacte. Poser xk+1 = xk + k dk : Remplacer k par k + 1 et répéter l’étape principale.

4.3 4.3.1

Lignes de niveau et méthode du gradient Dé…nitions

Dé…nition Soit f : Rn ! R et k 2 R: On appelle ligne de niveau d’ordre k associée à f et on la note Ck l’ensemble de points de Rn suivant : Ck = fx 2 Rn : f (x) = kg Exemple 1 (…g1) Soit f : R2 ! R : f (x; y) = x2 + y 2 Prenons k > 0: Alors Ck = (x; y) 2 R2 : x2 + y 2 = k

(a)

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE c’est le cercle de centre (0; 0) est de rayon

p

100

k:

Exemple 2 (…g2) Soit f : R2 ! R : 1 f (x; y) = x2 + y 2 5 Prenons k > 0: Alors Ck =

1 (x; y) 2 R2 : x2 + y 2 = k 5

(b)

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE

101

Transformons (b) sous la forme suivante : Ck =

x2 y2 (x; y) 2 R2 : p + p =1 ( 5k)2 ( k)2

(bbis)

C’est l’équation d’une p ellipse de grand axepl’axe des x; de petit axe, l’axe des y; de grand rayon 5k et de petit rayon k: Pour le cas particulier k = f (1; 1) = 1:2; on obtient la courbe de niveau 1 (x; y) 2 R2 : x2 + y 2 = 1:2 5 2 x y2 2 (x; y) 2 R : + =1 (2:449)2 (1:09)2

Cf (1;1) = C1:2 = = 001

1 5:jpg

f ig: lignes de niveaux : Cf (1:1) =

4.3.2

(x; y) :

x2 y2 + =1 (2:449)2 (1:09)2

Lignes de niveau et direction du gradient

Nous nous limiterons au cas n = 2 Théorème Soit Soit f : R2 ! R di¤érentiable, et (x0 ; y0 ) 2 R2 : Considérons la ligne de niveau Cf (x0 ;y0 ) Cf (x0 ;y0 ) = (x; y) 2 R2 : f (x; y) = f (x0 ; y0 )

(c)

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE

102

Soit T(x0 ;y0 ) la tangente à la courbe Cf (x0 ;y0 ) et passant par le point (x0 ; y0 ): Alors T(x0 ;y0 ) est orthogonale à la direction du gradiant Preuve Il est connu que l’équation de T(x0 ;y0 ) T(x0 ;y0 ) =

(x0 ; y0 ) (x x0 ) (x; y) 2 R2 : @f @x + @f (x ; y ) y0 ) = 0 0 0 (y @y

(d)

ou encore T(x0 ;y0 ) =

(

(x; y) 2 R2 : @f @x

@f @x

(x0 ; y0 ) :x +

(x0 ; y0 ) :x0 +

@f @y

@f @y

(x0 ; y0 ) :y

(x0 ; y0 ) :y0 = 0

)

c’est de la forme (e)

ax + by + c = 0:

La droite (d) admet comme vecteur directeur, le vecteur ! u ( b; a) et comme ! vecteur normal le vcteur v (a; b): Par conséquent la droite T(x0 ;y0 ) a comme ! (x0 ; y0 ) ; @f (x0 ; y0 )) et comme vecteur vecteur directeur le vecteur d ( @f @y @x @f @f ! normal, le vecteur n ( @x (x0 ; y0 ) ; @y (x0 ; y0 )) = rf (x0 ; y0 ) :

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

Cette méthode travaille de façon performante dans les premières étapes de l’algorithme. Malheuresement, dès qu’on s’approche du point stationnaire, la methode devient trés lente. On peut expliquer intuitivement ce phénomène par les considérations suivantes f (xk + d) = f (xk ) + rf (xk )t d + où (xk ; d) ! 0 quand d ! 0: Si d = rf (xk ); on obtient : xk+1 = xk f (xk+1 )

f (xk ) =

kdk (xk ; d);

rf (xk ) et par conséquent

krf (xk )k2 + krf (xk )k (xk ; rf (xk )) :

D’après l’expression précedente, on voit que lorsque xk s’approche d’un point stationnaire, et si f est continuement di¤érentiable, alors krf (xk )k est proche

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE

103

de zéro. Donc le terme à droite s’approche de zéro, indépendemment de , et par conséquent f (xk+1 ) ne s’éloigne pas beaucoup de f (xk ) quand on passe du point xk au point xk+1 :

4.4.2

Le phénomène de Zigzaguing

Il n’est pas facile de véri…er que pour la méthode du gradient on a toujours dtk :dk+1 = 0; c’est à dire que la suite fxk g engendrée par l’algorithme de la méthode du gradient, zigzague. Ceci crée un phénomène de ralentissement dans l’acheminement des points xk vers la solution optimale.

4.5 4.5.1

Quelques remèdes Changement de direction

Au lieu de prendre comme direction de descente, la direction : rf (xk );

dk = on prend des directions de la forme dk =

D:rf (xk );

où D est une matrice choisie convenablement (D pourrait être par exemple l’nverse de la matrice héssienne au point xk c’est à dire (H(xk )) 1 ): Un autre choix pourrait s’operer de la façon suivante : dk =

rf (xk ) + gk ;

où gk est un vecteur approprié.

4.5.2

Accéleration de la convergence

On peut aussi accelerer la convergence de la méthode du gradient. Pour celà on transforme grace à un algorithme d’acceleration de la convergence la suite fxk g en une suite fyk g qui convergerait vers la même limite que la suite fxk g ; mais convergerait plus rapidement. Si on note par x cette limite commune on exprime cette rapidité par la limite suivante : k

yk !1 xk

lim

x =0 x

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE

4.6 4.6.1

104

Programme en fortran 90 de la méthode de la plus forte pente et tests numériques Programme en fortran 90

On présente dans cette partie le programme en Fortran 90 de l’algorithme steepest descent avec la recherche linéaire d’Armijo. On utilise le choix des paramètres suivants : " = 10 5 ; mu = 0; 2; be = 0; 5 Programme en fortran 90 de la méthode du gradient program steepest implicit none integer, parameter : :n=1000 double precision yc(n),pk(n) double precision eps,s,be,f1,f0,mu,f2 integer k,l,m,i k=0 ;m=0 print*,’enter the initial point’ do i=1,n yc(i)=1. enddo print*,’enter eps’ read*,eps be=0.5 ;mu=0.2 do if(sqrt(dot_product(df(yc),df(yc)))=500)exit pk=-df(yc) f0=f(yc) !recherche d’Armijo l=1 ;s=1 f1=f(yc+s*pk) if(f1f0+mu*s*dot_product(df(yc),pk))exit s=s/be f1=f2 ;l=l+1 enddo s=s*be

CHAPITRE 4. METHODE DE LA PLUS FORTE PENTE yc=yc+s*pk k=k+1 print*,s else s=s*be do f1=f(yc+s*pk) if(f1 0 tel que krf (x) rf (y)k M kx yk : 8x; y 2 Rn (Lipshitz)

Soit un algorithme itératif qui génère une suite fxk gk2N dans Rn dé…nie par x0 2 Rn quelconque et les itérations xk+1 = xk +

k dk ;

k = 0; 1; 2; :::

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G avec dk direction de descente (c’est à dire rf (xk )T dk < 0) et conditions de (Wolfe1) et (Wolfe2). Alors on a 1 X k=0

cos2 ( k ) krf (xk )k2 < +1

k

véri…ant les

(Zoutendijk)

Conséquences tirées du théorème de Zoutendijk P1 2 cos ( ) krf (xk )k2 < +1 implique k k=0 lim cos2 ( k ) krf (xk )k2 = 0

k!1

(47)

La relation (47) n’implique pas en général que lim krf (xk )k2 = 0:

k!1

(48)

Si cos( k ) tend vers zéro quand k tend vers l’in…ni, krf (xk )k peut ne pas tendre vers zéro. Il faut donc éviter que k tende vers 2 ; pour s’assurer que : lim krf (xk )k = 0: C’est le but de la dé…nition suivante :

k!1

Dé…nition3 Soit f : Rn ! R, une fonction bornée inférieurement, di¤érentiable. Soit un algorithme itératif qui génère une suite fxk gk2N dans Rn dé…nie par x0 2 Rn quelconque et les itérations xk+1 = xk +

k dk ;

k = 0; 1; 2; :::

La suite fdk gk2N est dite en relation gradient avec la suite fxk gk2N si on a 9 > 0 : cos( k )

: 8k 2 N

(46tris)

Sens géométrique de la condition (46tris) La condition (46tris) veut dire que la suite fcos( k )gk2N est minorée par un nombre strictement positif . La condition (46tris) n’est pas garantie, si la suite cos( k ) ! 0 quand k ! 1: Géométriquent, cette condition veut dire que la suite des angles n o \ rf (xk ); dk k = k2N

ne doit pas tendre vers 2 quand k tend vers l’in…ni ou en d’autre termes termes, il ne faut pas que les deux suites de directions fdk gk2N et f rf (xk )gk2N

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G …nissent par devenir orthogonales quand k ! 1: Dans la …gure qui suit, on suppose que rf (xk ) a la même valeur pour tout k: La partie du plan coloriée en mauve, représente un ensemble de vecteurs fdk gk2N véri…ant la condition 9 > 0 : cos( k )

: 8k 2 N:

Si rf (xk ) change pour tout k; une telle représentation est plus di¢ cile. :/Users/sony/AppData/Local/Temp/graphics/zoutendijk21 8:jpg Si la suite fdk gk2N est en relation gradient avec la suite fxk gk2N . On obtient le théorème suivant qui assure la convergence globale de la suite fxk gk2N Théorème7 (de Zoudentijk-bis) Soit f : Rn ! R, une fonction bornée inférieurement, di¤érentiable, dont le gradient est continu au sens de Lipshitz, c’est à dire qu’il existe M > 0 tel que krf (x) rf (y)k M kx yk : 8x; y 2 Rn

Soit un algorithme itératif qui génère une suite fxk gk2N dans Rn dé…nie par x0 2 Rn quelconque et les itérations xk+1 = xk +

k dk ;

k = 0; 1; 2; :::

avec dk direction de descente (c’est à dire rf (xk )T dk < 0) et conditions de (Wolfe1) et (Wolfe2). Si on plus on a 9 > 0 : cos( k ) où

k

: 8k 2 N

k

véri…ant les (49)

est l’angle dé…ni par cos( k ) =

rf (xk )T dk krf (xk )k kdk k

Alors on a lim krf (xk )k = 0:

k!1

Preuve du Théorème de Zoutendijk-bis D’après le théorème de Zoutendijk, on a 1 X k=0

cos2 ( k ) krf (xk )k2 < +1

(49bis)

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G Ceci implique lim cos2 ( k ) krf (xk )k2 = 0:

k!1

Notons uk = cos2 ( k ); vk = krf (xk )k2 ; wk = uk vk

(50)

Alors (48) et (49) impliquent uk

2

> 0; vk > 0;

lim wk = 0

k!1

(51)

(50) implique vk =

1 wk uk

(52)

(51) et (52) donnent 0

vk

1 2

wk

(53)

lim wk = 0 et (g) impliquent

k!1

lim krf (xk )k = 0:

k!1

5.2 5.2.1

Convergence de la méthode du gradient. Cas des recherches linéaires inexactes Cas de la recherche linéaire inexacte de Wolfe

Théorème 5 ( convergence de la méthode de la plus forte pente avec la recherche linéaire de Wolfe). Soit f : Rn ! R, une fonction bornée inférieurement, di¤érentiable, dont le gradient est continu au sens de Lipshitz, c’est à dire qu’il existe G > 0 telle que krf (x) rf (y)k G kx yk : 8x; y 2 Rn dans l’ensemble (x0 ) = fx 2 Rn : f (x) f (x0 )g ; x0 2 Rn quelconque. Considérons l’algorithme de la méthode de la plus forte pente avec la recherche linéaire de Wolfe (voir Chapitre3). Soit fxk g une suite générée par cet algorithme. Alors ou bien l’Algorithme s’arrete après un nombre …ni d’itérations eu n un point xk0 tel que rf (xk0 ) = 0; ou bien il génère une suite in…nie fxk gk2N telle que rf (xk ) ! 0: k!1

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G Preuve du théorème5 C’est une conséquence directe du théorème de Zoudentijk-bis (Voir Chapitre3). En e¤et les hypothèses sur f sont les mêmes hypothèses du théorème de Zoudentijk-bis. Les donnés de notre théorème5 sont : dk =

rf (xk ) =)

k

=

rf (xk\ ); rf (xk ) = 0

donc cos( k ) = 1 : 8k: Par conséquent, en prenant par exemple

= 21 ; on a

1 8k 2 N : cos( k ) > : 2 D’après le théorème de Zoudentijk, on a lim krf (xk )k = 0:

k!1

Puisque k:k est une fonction continue, donc rf (xk ) ! 0: k!1

5.2.2

Cas de la recherche linéaire inexacte d’Armijo

Théorème 4 ( convergence de la méthode de la plus forte pente avec la recherche linéaire d’Armijo). Soit f : Rn ! R, une fonction bornée inférieurement, di¤érentiable, dont le gradient est continu au sens de Lipshitz, c’est à dire qu’il existe G > 0 telle que krf (x) rf (y)k G kx yk : 8x; y 2 Rn

dans l’ensemble (x0 ) = fx 2 Rn : f (x) f (x0 )g ; x0 2 Rn quelconque. Considérons l’algorithme de la méthode de la plus forte pente avec la recherche linéaire d’Armijo, c’est à dire l’algorithme dé…ni comme suit : Initialisation Fixons > 0 , 0 < " < 1 et x0 2 Rn point initial, poser k = 0 et aller à Etape principale. Etape principale A l’iteration k dé…nissons la direction dk = rf (xk ) et considérons la fonction d’Armijo b ( ) = (0) + " 0 (0) (8)

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G où

( ) est la fonction suivante : rf (xk )] :

( ) = f (xk + dk ) = f [xk Si rf (xk ) =0 stop. Sinon Trouver le plus petit entier t

0:

(9)

0 tel que b

2t

(10)

2t

et dé…nir le successeur xk+1 de xk comme suit k rf (xk );

xk+1 = xk avec k

=

2t Poser k = k + 1 et aller à Etape principale. Fin Soit fxk g une suite générée par cet algorithme. Alors ou bien il s’arrete après un nombre …ni d’itérations eu n un point xk0 tel que rf (xk0 ) = 0; ou bien il genere une suite in…nie fxk gk2N telle que rf (xk ) ! 0: k!1

Preuve : Supposons que l’algorithme génère une suite in…nie fxk g : En explicitant la condition d’Armijo (7.10) et en prenant en considération (7.8) et (7.9) on obtient :

2t

= f (xk +

dk ) 2t

= f (xk+1 )

Remarquons que (0) = f (xk ) et

0

b

2t

(0) =

= (0) +

2t

" 0 (0) :

(11)

krf (xk )k2 :

Ceci étant, la relation (7.11) devient f (xk+1 )

f (xk )

2t

" krf (xk )k2 :

(12)

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G D’autre part en développant f au voisinage du point xk ; on obtient f (xk+1 )

xk ) rf (e x); x e = xk + (1

f (xk ) = (xk+1

ou encore en remarquant que xk+1 = xk f (xk+1 )

f (xk ) = = (e x = = (x e =

)xk+1 ;

2 ]0; 1[ ;

k rf (xk );

t x); k rf (xk ) :rf (e t k rf (xk ) [rf (xk )

x e = xk + (1 )xk+1 ; 2 ]0; 1[ ; rf (xk ) + rf (e x)] ; xk + (1 )xk+1 ; 2 ]0; 1[); 2 t rf (e x)] ; k krf (xk )k + k rf (xk ) [rf (xk ) xk + (1 )xk+1 ; 2 ]0; 1[);

soit en utilisant l’inégalité de Cauchy Schwartz f (xk+1 )

krf (xk )k2 + 2 k krf (xk )k + 2 k krf (xk )k + 2 k krf (xk )k + 2 k krf (xk )k [1

f (xk )

k

krf (xk )k : krf (xk ) rf (e x)k x ek k krf (xk )k :G kxk xk k k krf (xk )k :G kxk+1 k krf (xk )k : k :G: krf (xk )k k :G] :

k

Finalement f (xk+1 )

f (xk )

krf (xk )k2 1

2t

2t

:G :

(13)

Choisissons maintenant le plus petit entier t de sorte que

2t

krf (xk )k2 1

:G

2t

2t

" krf (xk )k2 ;

c’est à dire que t véri…e en même temps 1

2t

:G

"

(14)

et :G < ":

(15)

" " (" 1) > : 2t 2G

(16)

1

2t

1

Ceci implique que

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G Bien sur n’oublions pas qu’avec ce choix et avec (7.13) on a aussi (7.12) qui donne en prenant en considération (7.16) f (xk+1 )

" (" 1) krf (xk )k2 : 2G

f (xk )
0: Notons par 1

3

n

= q11 ;

1;

2

2 ; :::

= det

2

q11 q12 4 = det q21 q22 q31 q32 2

q11 6 q21 = det 6 4 qn1

i ; :::

n

les détérminants suivants

q11 q12 (q12 = q21 ); q21 q22 3 q13 q23 5 (q12 = q21 ; q13 = q31 ; q23 = q32 q33 3 q1n q2n 7 7 (qij = qji ) 5 qnn

q12 q22 qn2

Ceci étant, on a le théorème suivant qui caractérise la dé…ni-positivité de Q Théorème1 (Critère de Sylvestère) Soit Q une matrice (n,n) symétrique. Q est dé…nie positive si et seulement si les détérminants i sont strictement positifs i.e. i

> 0; i = 1; 2:::; n

Remarque1 Si Q n’est pas symétrique, alors le critère de Sylvestere n’implique pas la dé…nie positivité de Q: L’exercice suivant le prouve. Exercice1 Considérons la matrice Q=

1 0 4 1

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G a) Calculez 1 et 2 b) Montrez que Q n’est pas dé…nie positive. c) Que peut on conclure ? Solution Exercice1

et

a) On a 1 = 1 > 0 et 2 = 1 > 0 b) Q n’est pas dé…nie positive, car si on prend xT = (1; 1);on a xT 6= (0; 0) xT Qx =

1 1

1 0 4 1

1 1

=

20

Notons gk = rf (xk ) = Qxk

(8)

b

Théorème2 Soit Q est une matrice (n; n) symetrique et de…nie positive et b 2 Rn et f (x) = 21 xT Qx bT x: Considérons le problème (PQSC) 1 T x Qx 2

minn f (x) = min n

x2R

x2R

bT x

(P QSC)

Supposons qu’à l’iteration k on a une direction dk de descente, c’est à dire que dk véri…e gkT dk = (Qxk b)T dk < 0 (9) soit

k

> 0 obtenu par une recherche lineaire exacte cad que f (xk +

k dk )

veri…e

= minf (xk + dk ) >0

Alors k

k

=

gkT dk dTk Qdk

Preuve du théorème2 Considérons '( ) = f (xk + dk ) Donc

k

(10)

(11)

est la solution optimale du problème unidimensionnel suivant '(

k)

= min'( ) >0

(12)

Q de…nie positive. Alors f (x) = 12 xT Qx bT x est strictement convexe sur Rn : Par conséquent '( ) = f (xk + dk ) est strictement convexe sur ]0; +1[ qui est un ouvert convexe. Donc k solution optimale de (12) si et seulement si k veri…e '0 ( k ) = 0: Or '0 ( ) = rf (xk + dk )T dk = [Q(xk + dk ) b]T dk = [Qxk b + Qdk ]T dk = [gk + Qdk ]T dk = gkT dk + dTk Qdk :

CHAPITRE 5. CONVERGENCE ET VITESSE DE CONVERGENCE DE LA METHODE DU G Donc '0 ( ) = 0 () dTk Qdk =

gkT dk

ou encore =

gkT dk : dTk Qdk

Remarque 1 Si Q n’est pas de…nie positive mais seulement semi dé…nie positive, alors f n’est pas strictement convexe, et dTk Qdk peut être égale à zéro. Par conséquent k ne sera plus de…nie par (10).

5.5.3

Etude de la convergence de la méthode du gradient pour les fonctions quadratiques strictement convexes

hbn

5.5.4

jnhb

Etude de la vitesse de convergence de la méthode du gradient pour les fonctions quadratiques strictement convexes

Chapitre 6 LA METHODE DE NEWTON 6.1

Introduction

Soit f : Rn ! R. On supposera dans tout ce chapitre que f 2 C 2 (Rn ): Soit maintenant (P ) le problème d’optimisation sans contraintes que nous avons déja rencontré dans le chapitre1 : Minimiser f f (x) : x 2 Rn g :

La méthode de Newton est attribuée au mathématicien, physicien et astronome anglais Issac Newton (1642-1727 ). Toutefois, comme le dit Durand ([42]) c’est Raphson qui publiait, en 1690, la formule itérative utilisée actuellement. C’est la raison pour laquelle certains auteurs l’appellent méthode de Raphson-Newton.1. L’algorithme de Newton est la généralisation multidimentionnelle de la méthode de Newton Raphson (voir [44], p.p.28,86,90 et 150), appliquée à la recherche des racines de rf (x): C’est certainement, avec la méthode de la plus forte pente (Cauchy 1847, [43] ) l’une des plus anciennes méthodes utilisées pour resoudre le problème (P ): Nous lui avons consacré un chapitre entier car les méthodes qui nous interessent par la suite (Quasi-Newton), s’obtiennent à partir de la méthode de Newton, c’est à dire qu’elles essayent de la generaliser en gardant ses avantages tout en se debarassant de ses inconvénients. Le principe de la méthode de Newton consiste à minimiser successivement les approximations du second-ordre d’une fonction f ; plus précisement si 1 f (x) ' f (xk )+rf (xk )(x xk )+ (x xk )t H(xk )(x xk ) = q(x); 8x 2 V (xk ); 2 H(xk ) étant la matrice hessienne de f au point xk ; alors une condition nécéssaire de minimum pour q est que rq(x) = 0; ou rf (xk ) + H(xk )(x 145

xk ) = 0:

(6.1)

CHAPITRE 6. LA METHODE DE NEWTON

146

Supposons que H est inversible, alors le successeur de xk est donné par xk+1 = xk

H

1

(6.2)

(xk )rf (xk )

Cette équation donne la forme générale des points générés par l’algorithme de Newton. Supposons que rf (x) = 0 et que H(x) est dé…nie positive (x un minimum local), alors H(xk ) reste dé…nie positive en tout point voisin de x: Ceci assure que le seccesseur de xk est bien dé…ni.

6.1.1

Algorithme

Etape initiale :Soit " un paramètre qui determine le critère d’arret. Choisir un point initial. Poser k=1 et aller à l’étape principale . Etape principale : Si krf (xk )k < "; stop ; sinon, poser xk+1 = xk H 1 (xk )rf (xk ) ; remplacer k par k + 1et répéter l’étape principale.

6.1.2

Etude de la convergence

En général la méthode de Newton ne converge pas à cause de la possibilité que H(xk ) soit singulière et donc que le point xk+1 ne soit pas bien dé…ni. Et même si H 1 (xk ) existe, la décroissance de f (x) n’est pas toujours assurée. Cependent ces problèmes peuvent être évités si le point initial est assez voisin du point x, x tel que rf (x) = 0 et H 1 (x) existe. Dans ce cas la méthode de Newton est bien dé…nie et elle converge vers le point x. C’est ce que nous prouverons dans ce théorème. Théorème 3.1 : Soit f : Rn ! R trois fois continuement di¤érentiable. Considérons l’algorithme de Newton dé…ni par l’application A(x) = x H 1 (x)rf (x): Soit x tel que rf (x) = 0 et supposons que H (x) 1 existe. Soit x1 un point initial assez proche de x de sorte que cette proximité implique l’existence de k1 ; k2 > 0; avec k1 k2 kx1 xk < 1 et véri…ant les deux propriétés suivantes : 1: 2: krf (x)

rf (x)

H(x)

1

H(x)(x

k1 x)k

pour tout x satisfaisant kx

xk

kx1

xk :

k2 kx

xk2

CHAPITRE 6. LA METHODE DE NEWTON

147

Alors, l’algorithme converge de façon superlinéaire vers x; avec une vitesse de convergence quadratique. Preuve : Soit l’ensemble de solutions

= fxg et l’ensemble

X = fx : kx

kx1

xk

xkg :

Pour prouver la convergence, on utilise le corrolaire1 du théorème 5. Notons que X est compact et que l’application A dé…nie par : y 2 A(x) , y = x

H

1

(x)rf (x);

est fermée sur X Montrons maintenant que (x) = kx xk est une fonction de descente. Soit x 2 X;et supposons que x 6= x: Soit y 2 A(x); donc y

x = (x x) H 1 (x) [rf (x) = H 1 (x) [rf (x) rf (x)

rf (x)] ; H(x)(x x)]

D’aprés (1),(2),on a H 1 (x) [rf (x) rf (x) H(x)(x x)] ; H 1 (x) krf (x) rf (x) H(x)(x x)k ; H 1 (x) krf (x) rf (x) H(x)(x x)k ; < kx xk :

ky

xk =

Donc on a prouvé que (y) < (x); 8y 2 A(x) et par suite est une fonction de descente. D’aprés le corrolaire 1.1, on conclut que l’algorithme converge vers x: De plus, pour tout xk 2 X; son seccesseur xk+1 satisfait : kxk+1

xk

k1 k2 kx ) lim sup k!+1

kxk+1 xk kxk xk 2 xk k 1 k2 xk 2

xk2 ) kxk+1 kxk

k1 k2

puisque fxk g ! x; donc la vitesse de convergence est quadratique.

6.1.3

Avantages et Inconvénients de la méthode de Newton

Avantages Comme nous l’avons vu au théorème précédent, la méthode de N ewton béné…ce d’une convergence quadratique, et c’est son principal avantage

CHAPITRE 6. LA METHODE DE NEWTON

148

Inconvénients 1. Cette méthode fonctionne trés bien pour les problème de petite dimension, lorsqu’on peut calculer facilement la matrice hessiene et son inverse. Cette procédure nécessite des itérations plus nombreuses et couteuses dans les problèmes de grand taille. 2. Comme xk+1 = xk

H

1

(xk )rf (xk )

on voit que le successeur xk+1 de xk n’est pas toujours bien dé…ni. 3. Même si H 1 (xk ) est inversible, la direction dk = H 1 (xk )rf (xk ) n’est pas toujours une direction de descente. ( Si H(xk ) est dé…nie positive, alors dk est une direction de descente) . 4. En plus, et d’après le théorème1.1, on voit, puisque le pas de la progression es égal à +1, alors on peut bien avoir f (xk+1 )

f (xk ) :

Ceci implique que la méthode de Newton peut converger vers un point stationnaire qui n’est pas un minimum (Maximum ou point selle). Conclusion : Ceci nous ramène à conclure que la méthode de Newton ne genère pas en géneral une suite qui converge vers le minimum de la fonction. Mais sous certaines conditions elle devient tres interessante (Hessien dé…ni positif, point initial assez proche de la solution optimale,...)

6.2

Programme en fortran et tests numériques

================================================ programme en Fortran 90 de la méthode de Newton program newton !— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — ! Ce programme minimise une fonction deux fois continuement di¤erentiable !à plusieurs variables en utilisant la méthode de Newton. !— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — !— — — partie déclaration — — — — — — — — — — — — — — — — — — — — implicit none integer,parameter : :n=2

CHAPITRE 6. LA METHODE DE NEWTON

149

integer i,j,k,s,v doubleprecision x(n),H(n,n),HI(n,n),g(n),eps,t,d(n) print*,’entrer le point initial x0’ print*,’===============’ read*,(x(i),i=1,n) print*,’entrer eps’ print*,’=======’ read*,eps s=1 g=gradf(x) do if(norm(g)pivot)then pivot=A(l2,k)

CHAPITRE 6. LA METHODE DE NEWTON

151

l=l2 endif enddo if(pivot==0)then r=1 goto 11 endif do l1=1,2*n h=A(l,l1) ;A(l,l1)=A(k,l1) ;A(k,l1)=h enddo do j=1,2*n B(k,j)=A(k,j)/pivot enddo do i=1,n if(i/=k)then do j=1,2*n B(i,j)=A(i,j)-A(i,k)*B(k,j) enddo endif enddo do i=1,n do j=1,2*n A(i,j)=B(i,j) enddo enddo enddo do i=1,n do j=1,n AI(i,j)=A(i,j+n) enddo enddo 11 endsubroutine end Exemple 3.1 : Nous allons appliquer maitenant cet algorithme sur un problème test trés classique du à Rosenbrock. La fonction de rosenbrock à minimiser dans Rn est la suivante : f (x1 ; x2 ) = (x1 1)2 + p(x21 x2 )2 ;

CHAPITRE 6. LA METHODE DE NEWTON

152

où p est un paramètre positif, ici égal à 100. Dans les lignes de niveau de cette fonction il y’a une vallée très étroite, en forme de banane, d’où le surnom “Rosenbrock banana”, conduisant au minimum global x = (1; 1); avec f (x ) = 0: Donc seule une méthode e¢ cace permettra de trouver ce minimum (voir [21], p.152) Les resultats obtenus par un programme en fortran 90 sont illustrés dans le tableau 3.1, le point initial est (-1.2,1) et " = 10 5 :

k 1 2 3 4 5 6

tableau f (x) .242000E+02 .473188E+01 .141185E+04 .559655E-01 .313189E+00 .185274E-10

3.1 krf (x)k .232868E+03 .463943E+01 .137079E+04 .473110E+00 .250274E+02 .860863E-05

================================================ Pour atteindre la précision " donnée, il nous a fallu 6 itérations. la solution approchée est x6 = (x1 ; x2 ); x1 = 9.999956956536786E-001, x2 = 9.999913913257368E-001 avec f (x6 ) = f (x1 ; x2 ) = 1.852739725430225E-011 Exemple 3.2 : n = 4; f (x) = 100:(x2 x21 )2 + (1: x1 )2 + 90:(x4 +19:8(x2 1:)(x4 1:)

x23 )2 + (1:

x3 )2 + 10:1[(x2

1:)2 + (x4

1:)2 ]

cette fonction est la fonction de Wood, elle admet le point (1; 1; 1; 1) comme un minimum et le point ( 1; 1; 1; 1) comme un point selle. Nous allons appliquer la méthode de Newton pour minimiser cette fonction en prenant x0 = ( 3; 1; 3; 1) et " = 10 4 : Les resultats obtenues sont illustrés au tableau 3.2, et on remarque bien que la méthode de Newton à convergé vers le point ( 1; 1; 1; 1) qui est le point selle de cette fonction. !====================================================== le nombre d’iterations est s= 15 la solution est x= (-9.679741E-01, 9.471393E-01, -9.695163E-01, 9.512478E01) la valeur de f(x) est 7.876967 !======================================================

CHAPITRE 6. LA METHODE DE NEWTON tableau 3.2 itération f (x) 1 1291.438 2 295.9513 3 67.68565 4 17.33662 5 8.689081 6 7.892798 7 7.876516 8 7.877190 9 7.876882 10 7.876977 11 7.876966 12 7.876967 13 7.876967 14 7.876967

153

krf (x)k 16397.13 1679.932 1003.095 285.0620 106.9116 26.45835 3.768905 0.150338 0.650068 0.198463 0.186190 0.015349 0.007221 0.000112

A cause de ces inconvénients, il existe des modi…cations qui permettent d’assurer la convergence globale de la méthode de N ewton, alliant les avantages de la vitesse de convergence quadratique prés de la solution, et ceux d’une méthode de descente. Parmi ces méthodes, on notera par exemple les méthodes dites quasi-Newton discutées plus tard.