Optimisation Par La Méthode de Newton

Approche mathématique de l’optimisation sans contrainte
1.Optimisation par la méthode de la section Dorée

1. Définition : Triplet de points admissibles.
Soit f une fonction continue sur un intervalle I, et trois réels a < c < b de I. On dit que le triplet
est admissible pour la minimisation de f si on a f (a)  f (c)  f (b).
Dans ce cas la fonction admet un minimum local sur ]a; b[ : elle admet un minimum global
sur le compact [a ; b], et ce minimum ne peut être ni en a ni en b, sauf si f (a) = f (c) ou f (b) =
f (c), mais dans ce cas il y a bien un minimum local en c.
La méthode de la section dorée consiste à s’arranger à réduire constamment la taille du triplet
en utilisant le ratio d’or.
l 0=l 1 +l 2 (1)
l1 l2
= (2)
l0 l1
L’équation (2) peut s’écrire :

l1 l2
=
l 1 +l 2 l 1
l2
Posons : R=
l1
On aura l’équation suivante :

1
1+ R=
R
D’où :
2
R + R−1=0
La résolution de cette équation conduit à la racine positive :
−1+ √ 1−4 (−1 ) √ 5−1

R= = =0,6180
2 2
Cette valeur constitue le nombre d’or, il permet de déterminer l’optimum de façon
efficace.
Cette méthode commence par deux valeurs initiales xl et xu, de l’intervalle [xl , xu] au sein
duquel un extremum local de f(x) existe. Ensuite, deux points de l’intervalle [x l , xu] seront
choisis comme suit :
f :[xl, xu] IR
La fonction est évaluée en ces deux points. Les cas qui se présentent :
1. Si f (x1) > f (x2), alors le domaine à gauche de x2, à partir de xl

et x2, peut être éliminé car il ne contient pas le maximum. Dans ce cas, x2
devient le nouveau xl pour l’itération suivante (x2 = xl).
2. Si f (x2) > f (x1), alors le domaine à droite de x1, càd de x1 à xu peut être éliminé. Dans
ce cas, x1 devient le nouveau xu pour l’itération suivante (x1 = xu).
3. f (x1) = f (x2), alors le domaine à droite de x1, càd de x1 à xu peut être éliminé ainsi que
de gauche de x2, à partir de xl et x2. Dans ce cas :
{xxu=x
l=x 2
1
Exemple
Utiliser la méthode de la section Dorée pour déterminer le maximum de la fonction suivante
dans l’intervalle [0, 4] :
2
x
f ( x )=2 sinx−
10
Corrigé
x l=0 et x u=4
f ( x l )=f ( 0 ) =0
f ( x u )=f ( 4 )=−3,1136
Calculons le ratio d’or :
d= √
5−1
(4−0) = 2,4720
2
x 1=xl +d = 0+2,472 = 2,4720
x 2=x u−d=4−2,472=1,5280
Calculons les fonctions f(x1) et f(x2) :

2
1,528
f ( x 2 )=f ( 1,528 )=2 sin ( 1,528 )− =1,7650
10
f ( x 1 )=f ( 2,472 )=0,6300
Comme f ( x 2 ) >¿ f ( x1 )
1,7650
0,6300
x 1=2,472 0
xl
x 2=1,528 xu
-3,1136
Le nouvel intervalle : xl = 0 et x 1=xu =2,472

1,7650
f ( x l )=f ( 0 ) =0
f ( x u )=f ( 2,472 )=0,6300 1,5310

0,6300
D’où :
x u=2,472 0
d= √
5−1
(2,472−0) = 1,5280 xl
2
2=¿ x 1=1,528
x 2=x u−d=2,472−1,5280=0,9440 ¿ 0,944
x¿
x 1=xl + d=0+1,5280=1,5280
f ( x 2 )=f ( 0,9440 )=1,5310
Les résultats obtenus sont récapitulés dans le tableau suivant :
i xl f (xl ) x2 f ( x2 ) x1 f (x1 ) xu f ( xu ) d
1 0 0 1,5279 1,7647 2,4721 0,6300 4,0000 -3,1136 2,4721
2 0 0 0,9443 1,5310 1,5279 1,7647 2,4721 0,6300 1,5279
3 0,9443 1,5310 1,5279 1,7647 1,8885 1,5432 2,4721 0,6300 0,9443
4 0,9443 1,5310 1,3050 1,7595 1,5279 1,7647 1,8885 1,5432 0,5836
5 1,3050 1,7595 1,5279 1,7647 1,6656 1,7136 1,8885 1,5432 0,3607
6 1,3050 1,7595 1,4427 1,7755 1,5279 1,7647 1,6656 1,7136 0,2229
7 1,3050 1,7595 1,3901 1,7742 1,4427 1,7755 1,5279 1,7647 0,1378
8 1,3901 1,7742 1,4427 1,7755 1,4752 1,7732 1,5279 1,7647 0,0851
La convergence est atteinte après 8 itérations lorsque x = 1,4427 à la valeur 1,7755.
2. Optimisation par la méthode de Newton

Cette méthode peut être utilisée pour déterminer le minimum ou le maximum d’une fonction.
La méthode de Newton nécessite l’utilisation de la dérivée f’(f au moins de classe C 2).
Considérons l’approximation quadratique de la fonction f(x) au point x=xi en utilisant le
développement de Taylor.
'
f ( xi ) 1 ''
f ( x )=f ( xi ) + ( x− xi ) + 2 f ( x i ) ( x−x i)
2
(3)
1
En considérant f ' (x )=0 ; dans ce cas les itérés sont donnés par la formule suivante :
f ' (x i )
xi+1 = xi - (4)
f ' '(x i )
Exemple
En utilisant la méthode de Newton, déterminer le maximum de la fonction suivante :
x2
f(x) = 2sinx -
10
avec xo= 2,5
Corrigé
f’(x) = 2cos x – (x/5)
f’’(x) = -2sinx – (1/5)
D’où : xi+1 = xi – ((2cos xi -xi/5)/ (-2sinxi-1/5))
x1 = 2,5 - ((2cos 2,5 -2,5/5)/ (-2sin2,5-1/5)) = 0,99508
i x f(x) f’(x) f’’(x)

0 2,5 0,57194 −2,10229 −1,39694
1 0,99508 1,57859 0,88985 −1,8776
2 1,46901 1,77385 −0,09058 −2,18965
3 1,42764 1,77573 −0,00020 −2,17954
4 1,42755 1,77573 0,00000 −2,17952
Après 4 itérations on atteint la convergence au point x=1,42755 et la valeur maximale

atteinte est de f(x) = 1,77573.

Optimisation Par La Méthode de Newton

Transféré par

Droits d'auteur :

Formats disponibles

Optimisation Par La Méthode de Newton

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Optimisation Par La Méthode de Newton

Transféré par

Droits d'auteur :

Formats disponibles

Approche mathématique de l’optimisation sans contrainte

1.Optimisation par la méthode de la section Dorée

L’équation (2) peut s’écrire :

On aura l’équation suivante :

−1+ √ 1−4 (−1 ) √ 5−1

1. Si f (x1) > f (x2), alors le domaine à gauche de x2, à partir de xl

Calculons le ratio d’or :

Calculons les fonctions f(x1) et f(x2) :

Le nouvel intervalle : xl = 0 et x 1=xu =2,472

f ( x u )=f ( 2,472 )=0,6300 1,5310

f ( x 2 )=f ( 0,9440 )=1,5310

Les résultats obtenus sont récapitulés dans le tableau suivant :

La convergence est atteinte après 8 itérations lorsque x = 1,4427 à la valeur 1,7755.

2. Optimisation par la méthode de Newton

i x f(x) f’(x) f’’(x)

Après 4 itérations on atteint la convergence au point x=1,42755 et la valeur maximale

Vous aimerez peut-être aussi