Chapitre II-optimisation Sans Contrainte [PDF]

Zitiervorschau

2

Optimisation sans contraintes

Techniques d’optimisation Sommaire

1.

Bases théoriques

2.

Optimisation sans contraintes 2.1 Méthodes de descente 2.2 Méthode de Newton 2.3 Recherche linéaire 2.4 Région de confiance 2.5 Moindres carrés 2.6 Méthode de Nelder-Mead

3.

Optimisation avec contraintes

215

2

Optimisation sans contraintes

Techniques d’optimisation 2 Optimisation sans contraintes

Problème non linéaire sans contraintes minn f(x) xR

o problème noté (PO)

Méthodes globales • Capacité à localiser plusieurs minima locaux (éventuellement le minimum global) • Algorithmes non déterministes (déplacements aléatoires « organisés ») • Métaheuristiques : algorithmes génétiques, recuit simulé, essaims, colonies de fourmis, recherche tabou,… • Convergence généralement lente, peu précise Méthodes locales • Recherche d’un minimum local à partir d’un point initial fourni par l’utilisateur • Méthodes d’ordre 0 : sans dérivées o Nelder-Mead d’ordre 1 : avec dérivées premières o plus forte pente d’ordre 2 : avec dérivées premières et secondes o Newton • Critères d’efficacité : rapidité de convergence (nombre d’appels de la fonction) précision de convergence robustesse à l’initialisation

216

2 Optimisation sans contraintes 2.1 Méthodes de descente

Techniques d’optimisation Sommaire

1.

Bases théoriques

2.

Optimisation sans contraintes 2.1 Méthodes de descente 2.1.1 Principes 2.1.2 Itérations 2.1.3 Initialisation et arrêt 2.2 Méthode de Newton 2.3 Recherche linéaire 2.4 Région de confiance 2.5 Moindres carrés 2.6 Méthode de Nelder-Mead

3.

Optimisation avec contraintes

217

2 Optimisation sans contraintes 2.1 Méthodes de descente 2.1.1 Principes

Techniques d’optimisation 2.1.1 Méthodes de descente

Problème sans contrainte

’ f(x*) 0 x* minimum local Ÿ ­® 2 xR ¯’ f(x*) t 0 On ne sait pas trouver le minimum global dans le cas général (f quelconque).

minn f(x)

Méthode locale • Initialisation x0 • Itérations • Arrêt

o recherche d’un minimum local au voisinage de x0 o passage du point xk au point xk+1 meilleur o solution x* ou blocage

Initialisation x0

Point initial xk

Modèle local fˆk (x)

Solution x*

Nouveau point xk+1

Amélioration f(xk+p) < f(xk)

218

2 Optimisation sans contraintes 2.1 Méthodes de descente 2.1.2 Itérations

Techniques d’optimisation 2.1.2 Itérations

Modèle local : prédiction • Point courant xk ,fk = f(xk) • Evaluation de gk = ’f(xk) ou approximation (différences finies) Hk = ’2f(xk) ou approximation (quasi Newton) •

Modèle quadratique :

min fˆk ( x k  p) p

fk  ptgk 

1 t p Hkp 2

o Méthodes de Newton ou quasi-Newton Amélioration : correction • Nouveau point xk+1 = xk + p •

o xˆ k 1 x k  pˆ (prédiction)

tel que f(xk+p) < f(xk)

Déplacement p à partir de xk par recherche linéaire suivant par région de confiance dans

d k xˆ k 1  x k x  xk  r

o Méthodes de globalisation •

La méthode de Newton appliquée directement ne converge pas systématiquement. La globalisation est nécessaire pour contrôler la convergence.

219

2 Optimisation sans contraintes 2.1 Méthodes de descente 2.1.3 Initialisation et arrêt

Techniques d’optimisation 2.1.3 Initialisation et arrêt

Initialisation • Les méthodes locales recherchent le minimum au voisinage du point de départ. •

Objectifs :

•

Le minimum local trouvé est le plus proche du point initial x0. o initialisation à modifier pour trouver un autre minimum local

•

Les méthodes « globales » explorent « aléatoirement » les solutions o localisation possible de plusieurs minima locaux

rapidité de convergence précision de convergence o méthodes à base de dérivées

Conditions d’arrêt • Déplacement insuffisant : • Amélioration insuffisante : • Condition d’ordre 1 vérifiée : • Nombre maximal d’itérations ou d’appels fonction :

x k 1  x k  H x f k  f k 1  H f g k  Hg Niter , Nfonc

220

2 Optimisation sans contraintes 2.2 Méthode de Newton

Techniques d’optimisation Sommaire

1.

Bases théoriques

2.

Optimisation sans contraintes 2.1 Méthodes de descente 2.2 Méthode de Newton 2.2.1 Résolution d’équations 2.2.2 Minimisation 2.2.3 Globalisation 2.3 Recherche linéaire 2.4 Région de confiance 2.5 Moindres carrés 2.6 Méthode de Nelder-Mead

3.

Optimisation avec contraintes

221

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Résolution d’équations

‰ Principes ‰ Méthode de Newton ‰ Méthode de quasi-Newton

222

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Résolution d’équations

Système d’équations non linéaires

g(x) 0

avec g : Rn o Rn

o système de n équations à n inconnues

Principe de la méthode de Newton • Linéariser g au point initial x0 o fonction modèle OLQpDLUHƣ© proche » de g • 5pVRXGUHOHV\VWqPHOLQpDLUHƣ[  o nouveau point x1 • Itérer jusqu’à vérifier g(x)=0 o solution x*

Initialisation x0

Point initial xk

Fonction modèle gˆ k (x)

Solution x*

Nouveau point

Résolution gˆ k (x) 0

xk+1

223

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de Newton

Fonction modèle • Développement de Taylor à l’ordre 1 de g en xk

g(x) •

g(x k )  ’g(x k ) T (x  x k )  o x  x k



Modèle linéaire de g en xk :

gˆ k (x)

g(x k ) 

G k (x  x k )

avec G k  R nun

Choix de la matrice Gk • Méthode de Newton o Gk = ’g(xk)T = matrice jacobienne de g en xk • Méthode de quasi-Newton o Gk = approximation de ’g(xk)T Résolution

0 Ÿ g(x k )  G k (x  x k )

•

Système linéaire :

gˆ k (x)

•

Itération :

x k 1

•

Condition d’arrêt :

g(x k )  İ

x k  G k1g(x k )

0

si Gk inversible

224

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de Newton

Illustration à une variable • Equation non linéaire : g(x) = 0 • Point initial : x0, y0 = g(x0) o Tangente en x0 : y = y0 +g’(x0)(x - x0 )

0 Ÿ x1

•

Intersection axe x :

y

•

Nouveau point :

x1, y1 = g(x1)

x0 

y0 g' (x 0 )

x* x2

x1

x0

225

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de Newton

Modèle linéaire de g en xk

gˆ k (x)

g(x k )  G k ( x  x k )

avec G k

’g(x k ) T

Erreur de linéarisation M = constante de Lipschitz sur le gradient | majorant de la courbure

g(x)  gˆ k (x) d

1 M x  xk 2

2

o erreur quadratique

Vitesse de convergence Hypothèses sur la solution x* : ’g(x * ) inversible

’g(x * ) 1 d Ș Suite (xk) : x k 1

1

x k  G k g(x k )

•

(xk) converge vers x* si x0 est « assez proche » de x* : r ! 0 / x 0  x *  r Ÿ lim x k

•

La convergence est quadratique

k of

o x k 1  x * d MȘ x k  x *

x*

2

226

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Exemples

Exemple 1 • Fonction : g(x) x 2  1 • Dérivée : g' (x) 2x • Solution : x = 1 o g’(1) = 2

Iteration

g(x)

1

x

x(k)

g(x)=x**2-1 g'(x)=2x

Erreur

0

4,00000000

1,5E+01

8,0000

3,0E+00

1

2,12500000

3,5E+00

4,2500

1,1E+00

2

1,29779412

6,8E-01

2,5956

3,0E-01

3

1,03416618

6,9E-02

2,0683

3,4E-02

4

1,00056438

1,1E-03

2,0011

5,6E-04

5

1,00000016

3,2E-07

2,0000

1,6E-07

6

1,00000000

2,5E-14

2,0000

1,3E-14

Convergence quadratique g’(x*) inversible

227

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Exemples

Exemple 2 • Fonction : g(x) ( x  1) 2 • Dérivée : g' (x) 2(x  1) • Solution : x = 1 o g’(1) = 0

Iteration 0 1 2 3 4 5 6 7 8 9 10 15 20

g(x)

1

x

x(k) g(x)=(x-1)**2 g'(x)=2(x-1) 4,00000000 9,0E+00 6,0000 2,50000000 2,3E+00 3,0000 1,75000000 5,6E-01 1,5000 1,37500000 1,4E-01 0,7500 1,18750000 3,5E-02 0,3750 1,09375000 8,8E-03 0,1875 1,04687500 2,2E-03 0,0938 1,02343750 5,5E-04 0,0469 1,01171875 1,4E-04 0,0234 1,00585938 3,4E-05 0,0117 1,00292969 8,6E-06 0,0059 1,00009155 8,4E-09 0,0002 1,00000286 8,2E-12 0,0000

Erreur 3,0E+00 1,5E+00 7,5E-01 3,8E-01 1,9E-01 9,4E-02 4,7E-02 2,3E-02 1,2E-02 5,9E-03 2,9E-03 9,2E-05 2,9E-06

Convergence lente g’(x*) non inversible

228

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Exemples

Exemple 3 • Fonction : g(x)

Arc tan( x )

Iteration 0 1 2 3 4 5 6

1 1 x2

•

Dérivée : g' (x)

•

Solution : x = 0 o g’’(1) = 0

g(x)

x1

x(k) g(x)=Arctan(x) g'(x)=1/(1+x**2) 1,300 0,915 0,372 -1,162 -0,860 0,426 0,859 0,710 0,575 -0,374 -0,358 0,877 0,034 0,034 0,999 0,000 0,000 1,000 0,000 0,000 1,000

Erreur 1,3E+00 -1,2E+00 8,6E-01 -3,7E-01 3,4E-02 -2,6E-05 1,2E-14

Convergence

0

x0

x2 x

Iteration 0 1 2 3 4 5 6

x(k) g(x)=Arctan(x) g'(x)=1/(1+x**2) 1,500 0,983 0,308 -1,694 -1,038 0,258 2,321 1,164 0,157 -5,114 -1,378 0,037 32,296 1,540 0,001 -1575,317 -1,570 0,000 3894976,008 1,571 0,000

Divergence

Erreur 1,5E+00 -1,7E+00 2,3E+00 -5,1E+00 3,2E+01 -1,6E+03 3,9E+06

229

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de Newton

Intérêt de la méthode de Newton • Convergence quadratique au voisinage de la solution o très rapide et précise • Méthode à privilégier dans les algorithmes d’optimisation Difficultés • Calcul explicite du gradient ’g(xk) à chaque itération o coûteux (n appels fonctions) • Convergence non garantie o même près de la solution Adaptations • Méthodes de quasi-Newton

•

Techniques de globalisation

o Gk = approximation du gradient ’g(xk) construite à partir des itérations précédentes sans calcul explicite du gradient o Contrôle du point xk+1 (meilleur que xk ?) g(x k 1 )  g(x k )

Si le point xk+1 n’est pas satisfaisant o Méthodes de recherche linéaire ou région de confiance 2 pour minimiser g(x)

230

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de quasi-Newton

Méthode de Broyden On cherche à définir la matrice Gk à partir de la matrice Gk-1 de l’itération précédente. Les matrices Gk-1 et Gk doivent être « proches » au sens de la norme matricielle. Variation de modèle • Modèle linéaire de g en xk-1 :

gˆ k -1 (x)

g(x k -1 )  G k -1 ( x  x k -1 )

•

Modèle linéaire de g en xk:

gˆ k (x)

g(x k )  G k ( x  x k )

•

Différence entre les modèles en xk-1 et xk

gˆ k (x)

 G k (x  x k ) g(x k ) g(x k -1 )  G k ( x k  x k -1 )  G k ( x  x k )  G k ( x  x k -1 ) g(x k -1 ) gˆ k -1 (x)  G k -1 ( x  x k -1 )  G k ( x  x k -1 ) gˆ k -1 (x)  (G k  G k -1 )( x  x k -1 )

Ÿ gˆ k (x)  gˆ k -1 (x)

car g(x k ) g(x k -1 )  G k (x k  x k -1 ) par définition de G k car gˆ k -1 (x) g(x k -1 )  G k -1 ( x  x k -1 ) par définition de gˆ k -1

(G k  G k -1 )(x  x k -1 )

231

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de quasi-Newton

Objectif Conserver un modèle linéaire de g en xk

gˆ k (x)

g(x k )  G k ( x  x k )

avec G k | ’g(x k ) T

sans calculer explicitement Gk Equation de la sécante On choisit une matrice Gk Rnun vérifiant :

g(x k )  g(x k -1 )

G k ( x k  x k -1 ) œ y k -1

G k d k -1

d avec ­® k -1 ¯ y k -1

x k  x k -1 g(x k )  g(x k -1 )

o équation de la sécante entre xk-1 et xk Choix de G Il existe une infinité de matrices G vérifiant l’équation de la sécante : n2 inconnues (composantes de G Rnun ) n équations Chaque ligne de G définit un hyperplan de Rn passant par xk-1 et xk o infinité d’ hyperplans possibles

232

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de quasi-Newton

Illustration à une variable • Equation non linéaire : g(x) = 0 • Points initiaux : x0, y0 = g(x0) x1, y1 = g(x1)

0 Ÿ x2

•

Intersection axe x :

y

•

Nouveau point :

x2, y2 = g(x2)

o Sécante en x1 : y

x0 

x1  x 0 y0 y1  y 0

y0 

y1  y 0 (x  x 0 ) x1  x 0

x* x2

x1

x0

233

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Méthode de quasi-Newton

Mise à jour de Broyden L’écart entre les modèles gˆ k -1 (x) et gˆ k (x) est minimal en choisissant Gk solution de :

minnun G  G k -1 sous y k 1

GR

G d k 1

Formule de Broyden : G k

G k -1

avec

­d k -1 ®y ¯ k -1

x k  x k -1 g(x k )  g(x k -1 )

 y k 1  G k -1d k 1 d Tk 1  d Tk 1d k 1

Convergence • La matrice G ne converge pas forcément vers ’g

o solution optimale

o ne compromet pas la convergence

•

Les méthodes de quasi-Newton et de Newton peuvent converger vers des solutions différentes.

•

La méthode de quasi-Newton converge généralement moins vite que la méthode de Newton, mais nécessite beaucoup moins d’appels de la fonction g (pas de calcul de gradient). o Peu de résultats théoriques o Méthode efficace en pratique, comportement à vérifier et adapter au cas par cas

234

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.1 Résolution d’équations

Techniques d’optimisation 2.2.1 Exemple

Comparaison Newton  Quasi-Newton • Fonction : g(x) x 2  1 • Dérivée : g' (x) 2x • Solution : x = 1 Newton

Quasi - Newton Iteration

x(k)

g(x)=x**2-1

5,00000000

2,4E+01

0

4,00000000

1,5E+01

1

2,33333333

2

dg/dx

Erreur

Iteration

x(k)

g(x)=x**2-1 g'(x)=2x

Erreur

4,0E+00

0

4,00000000

1,5E+01

8,0000

3,0E+00

9,0000

3,0E+00

1

2,12500000

3,5E+00

4,2500

1,1E+00

4,4E+00

6,3333

1,3E+00

2

1,29779412

6,8E-01

2,5956

3,0E-01

1,63157895

1,7E+00

3,9649

6,3E-01

3

1,03416618

6,9E-02

2,0683

3,4E-02

3

1,21238938

4,7E-01

2,8440

2,1E-01

4

1,00056438

1,1E-03

2,0011

5,6E-04

4

1,04716672

9,7E-02

2,2596

4,7E-02

5

1,00000016

3,2E-07

2,0000

1,6E-07

5

1,00443349

8,9E-03

2,0516

4,4E-03

6

1,00000000

2,5E-14

2,0000

1,3E-14

6

1,00010193

2,0E-04

2,0045

1,0E-04

7

1,00000023

4,5E-07

2,0001

2,3E-07

8

1,00000000

2,3E-11

2,0000

1,1E-11

235

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Minimisation

‰ Principes ‰ Méthode de Newton ‰ Méthode de quasi-Newton ‰ Méthode BFGS ‰ Méthode DFP ‰ Méthode SR1

236

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Problème de minimisation

Problème sans contrainte o gradient : g(x) = ’ f(x) minn f(x) xR hessien : H(x) = ’2f(x) Condition nécessaire de minimum local

­g(x*) 0 x* minimum local Ÿ ® ¯H(x*) t 0

(hessien semi-défini positif)

Recherche des points stationnaires Application de la méthode de Newton au système d’équations non linéaires : g(x) = 0 Modèle linéaire de g en xk : • •

Méthode de Newton : Méthode de quasi-Newton :

gˆ k (x)

­g(x ) g(x k )  G k ( x  x k ) avec ® k ¯G k

’f(x k ) ’g(x k ) T

’ 2 f(x k ) H k

G = H o calcul explicite du hessien à chaque itération G = approximation de H construite à partir des itérations précédentes sans calcul explicite du hessien

237

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode de Newton

Modèle linéaire de g=’ ’f en xk

gˆ k (x) • •

g(x k )  G k ( x  x k )

Itération : Condition d’arrêt :

­g(x ) avec ® k ¯G k

’f(x k ) ’g(x k ) T

x k 1 x k  ’ 2 f(x k ) 1 ’f(x k ) ’f(x k ) d İ

’ 2 f(x k )

Hk

o équations de Newton

Difficultés • Calcul explicite et inversion du hessien ’2f(xk) à chaque itération o coûteux • Convergence non garantie même près de la solution o mêmes difficultés que pour la résolution d’équations •

1ère condition nécessaire de minimum : ’f(x*)=0 o point stationnaire x* = minimum local, maximum local ou point selle o 2ème condition nécessaire de minimum à vérifier : ’2f(x*)t0

Adaptations • Méthodes de quasi-Newton • Techniques de globalisation

o Gk = approximation du hessien ’2f(xk) o Contrôle de la décroissance de f

238

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode de Newton

Modèle quadratique de f en xk • Développement de Taylor à l’ordre 2 de f en xk 1 f(x) f(x k )  ’f(x k ) T (x  x k )  (x  x k ) T ’ 2 f(x k )(x  x k )  o x  x k 2 • Modèle quadratique en xk 1 fˆk (x) f k (x k )  g Tk (x  x k )  (x  x k ) T H k (x  x k ) 2 • Lien entre le modèle de f et le modèle de g =’f ’fˆ (x) g  H (x  x ) gˆ (x)



k

k

k

k

2



k

Minimisation du modèle de f en xk

•

­’ fˆk (x*) gˆ k (x*) ˆ Conditions suffisantes de minimum local : min f k (x)  ® 2 ˆ xR ¯’ f k (x*) H k ! 0 Si le hessien de f en xk est défini positif : ’2f(xk) > 0 Minimisation du modèle quadratique de f en xk œ Méthode de Newton en xk pour résoudre ’f(x)=0

•

Sinon la méthode de Newton n’est pas directement applicable pour une minimisation

•

0

n

239

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode de Newton 4 3 2 • Fonction : f ( x )  x  12 x  47 x  60 x •

Dérivée : f ' ( x )

4 x 3  36 x 2  94 x  60 o 3 zéros o 1 minimum local, 2 maxima locaux

20,0 15,0 10,0 5,0 0,0 0,0

1,0

2,0

3,0

4,0

5,0

6,0

-5,0 -10,0 -15,0 -20,0

240

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode de Newton 2 • Modèle quadratique en x0 = 3 : fˆ0 ( x ) 7 x  48x  81 •

Itération de Newton en x0 = 3 : min fˆ0 ( x ) o x 1 x

24 7

o Meilleur que x0 f(x1) = 1.32 < 0 = f(x0)

1,50 1,25 1,00 0,75 0,50 0,25

-0,25

x1

x0

0,00 2,50

2,75

3,00

3,25

3,50

3,75

4,00

4,25

4,50

-0,50 -0,75 -1,00 -1,25 -1,50

241

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode de Newton 2 • Modèle quadratique en x0 = 4 : fˆ0 ( x ) x  4 x •

Itération de Newton en x0 = 4 : min fˆ0 ( x ) x

o x1

o Moins bon que x0 f(x1) = 12 > 0 = f(x0)

2

5,00 4,00 3,00 2,00 1,00

x1

0,00 1,00

1,50

2,00

x0 2,50

3,00

3,50

4,00

4,50

5,00

-1,00 -2,00 -3,00 -4,00 -5,00

242

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode de Newton • Modèle quadratique en x0 = 5 : fˆ0 ( x ) 17 x 2  160 x  375 •

Itération de Newton en x0 = 5 : min fˆ0 ( x ) o x 1 x

81 17

o Moins bon que x0 (maximise f) f(x1) = 1.513 > 0 = f(x0)

2,00 1,50 1,00 0,50

x1

0,00 4,00

4,25

4,50

x0 4,75

5,00

5,25

5,50

-0,50 -1,00 -1,50 -2,00 -2,50 -3,00

243

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode de quasi-Newton

Objectif Conserver un modèle quadratique de f en xk 1 fˆk (x) f k (x k )  g Tk (x  x k )  (x  x k ) T H k (x  x k ) 2 sans calculer explicitement Hk

avec H k | ’ 2 f(x k )

Mise à jour de Broyden On peut appliquer la méthode de Broyden à la résolution de g(x)=’f(x)=0.

Hk

H k -1

 y k 1  H k -1d k 1 d Tk 1  d Tk 1d k 1

avec

­d k -1 ®y ¯ k -1

x k  x k -1 g(x k )  g(x k -1 )

Inconvénients • Hk n’est pas forcément symétrique • Hk n’est pas forcément positive o Modifications de la méthode si l’on souhaite avoir H k | ’ 2 f(x k ) o Formules BFGS, DFP ou SR1

244

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode BFGS

Equation sécante Pour la résolution d’équations, on cherche la matrice Hk : • vérifiant l’équation sécante H k d k 1 y k 1 o formule de Broyden • la plus « proche » possible de Hk-1 • sans condition particulière sur la forme de la matrice • •

Pour une minimisation, on impose de plus à la matrice Hk d’être : symétrique o formule BFGS définie positive

Méthode de résolution La matrice Hk-1 issue de l’itération précédente est symétrique, définie positive. H k -1 L k -1LTk -1 • On part de la factorisation de Cholesky de Hk-1 : • On cherche la matrice Hk à partir de Hk-1 sous la forme : H k A k A Tk Il faut exprimer la matrice Ak en fonction de Lk-1. o On décompose l’équation sécante en 2 équations : ­x A Tk d k 1 T H k d k 1 y k 1 œ A k A k d k 1 y k 1 œ ® ¯A k x y k 1

245

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode BFGS

Méthode de résolution de l’équation sécante

H k d k 1

y k 1 œ A k A d k 1 T k

y k 1

­x A Tk d k 1 œ ® ¯A k x y k 1

1. Pour x donné, on cherche Ak la plus « proche » possible de Lk-1 vérifiant : A k x y k 1 2. On détermine ensuite x en reportant l’expression de Ak dans : x A Tk d k 1 3. On obtient H k A k A Tk que l’on exprime en fonction de Hk-1. Résolution Notations sans indices :

L = Lk-1, A = Ak y = yk-1 , d = dk-1

1. En appliquant la formule de Broyden à L on obtient A en fonction de x : A 2. En reportant : x Il faut résoudre x

T

A d

x ( y  Lx) T L d d xTx T

( y  Lx) T d L d x xTx

( y  Lx ) x T L xTx

T

( y  Lx) T d L d x pour trouver x. T x x T

246

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode BFGS

Résolution de l’équation sécante On cherche xRn vérifiant : •

x

( y  Lx) T d L d x xTx T

Pour qu’une solution existe, le vecteur LTd doit être colinéaire à x :

DLT d Ÿ x T x D 2 d T Hd ( y  Lx) T d T yTd 2 T T T DL d Ÿ D L d En reportant dans l’équation : DL d L d  2 T D d Hd d T Hd 1 § yTd T · T T Pour qu’une solution existe, on doit avoir y d > 0 o A L  T ¨ Dyd L  T Hd d L ¸¸ ¨ y d© d Hd ¹ On obtient H : H A AT x

• •

k

k

k

k

Formule BFGS

y k 1 y Tk -1 H k -1d k 1d Tk 1H k -1  H k -1  T y k -1d k 1 d Tk 1H k -1d k 1

•

Mise à jour de Hk :

• •

Mise à jour symétrique, de rang 2 Mise à jour définie positive si y Tk -1d k 1 ! 0

Hk

d avec ­® k -1 ¯ y k -1

x k  x k -1 g(x k )  g(x k -1 )

247

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode BFGS

Méthode de quasi Newton BFGS • Le déplacement correspondant à une itération de la méthode de Newton est solution de Hkdk

’f ( x k ) Ÿ d k

H -1k’f ( x k )

o La matrice utile pour l’itération de Newton est l’inverse de Hk. •

On inverse les 2 membres de la formule BFGS pour obtenir Hk-1 en fonction de Hk-1-1. H

•

-1 k

§ d k 1 y Tk -1 · -1 § y k 1d Tk -1 · d k 1d Tk -1 ¨ ¸ ¨I  T ¸ ¨ d y ¸H k -1 ¨ I  d T y ¸  d T y k -1 k 1 ¹ k -1 k 1 k -1 k 1 ¹ © ©

­d si y Tk -1d k 1 ! 0 avec ® y k -1 ¯ k -1

x k  x k -1 g(x k )  g(x k -1 )

Méthode élaborée par Broyden, Fletcher, Goldfarb, Shanno à la fin des années 1960 o reconnue comme l’une des plus efficaces en pratique

Limitations • Si la condition yTd > 0 n’est pas vérifiée, on ne fait pas de mise à jour. • Si le hessien n’est pas défini positif, la méthode BFGS ne converge pas vers le hessien o cas d’un hessien indéfini o optimisation avec contraintes (hessien réduit positif z hessien complet)

248

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode BFGS

Algorithme BFGS • Direction de descente à l’itération k : u k 1 •

Minimisation dans la direction uk-1 :

•

Mise à jour de l’inverse du hessien

xk

H -1k -1g ( x k 1 ) x k 1  su k 1

­u k 1  H -1k -1g ( x k 1 ) avec ®s o min f x  su k 1 k 1 s ¯

§ d k 1 y Tk -1 · -1 § y k 1d Tk -1 · d k 1d Tk -1 ­d k -1 x k  x k -1 T ¨I  T ¸H k -1 ¨ I  T ¸ T avec H si y d ! 0 ®y k -1 k 1 ¨ d y ¸ ¨ d y ¸ d y ¯ k -1 g(x k )  g(x k -1 ) k -1 k 1 ¹ k -1 k 1 k -1 k 1 ¹ © © Propriété 1 T La mise à jour BFGS donne une matrice définie positive si d k -1 y k 1 ! 0 Cette condition est réalisée si xk est obtenu par minimisation exacte dans la direction  H -1k -1g ( x k 1 ) -1 k

Propriété 2 Pour une fonction f quadratique : f ( x )

1 T x Qx  c T x 2

­u i Q 1u j 0 , 0 d i z j d k l’algorithme BFGS donne des directions successives vérifiant : ® 1 1 ¯H k Q u i u i , 0 d i d k o directions conjuguées par rapport à Q1 o convergence en n itérations avec à l’itération n : H n Q

249

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode DFP

Méthode de résolution • Résolution de l’équation sécante sous la forme « inverse » : H k d k 1 • •

y k 1 œ H -1k y k 1 d k 1

Mêmes principes que BFGS appliqués à l’équation sécante inverse pour obtenir Hk-1 Première méthode quasi-Newton élaborée par Davidon dans les années 1950

Formule DFP • •

Mise à jour de l’inverse : H Mise à jour du hessien :

-1 k

Hk

H

-1 k -1

d k 1d Tk -1 H -1k -1 y k 1 y Tk 1H -1k -1 ­d k -1  T  avec ®y d k -1 y k 1 y Tk 1H -k1-1 y k 1 ¯ k -1

x k  x k -1 g(x k )  g(x k -1 )

§ d k 1 y Tk -1 · y k 1 y Tk -1 § y k 1d Tk -1 · ¨ ¸ ¨I  T ¸ ¨ y d ¸H k -1 ¨ I  y T d ¸  y T d k -1 k 1 ¹ k -1 k 1 ¹ k -1 k 1 © ©

Comparaison DFP  BFGS • Formules identiques en permutant dk1 et yk1 pour mettre à jour le hessien ou l’inverse • Mise à jour symétrique, de rang 2 • Mise à jour définie positive si d Tk -1 y k 1 ! 0 o condition similaire à BFGS • Méthode DFP en général moins efficace que BFGS

250

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode DFP

Algorithme DFP • Direction de descente à l’itération k : u k 1 •

Minimisation dans la direction uk-1 :

•

Mise à jour de l’inverse du hessien

H

-1 k

H

-1 k -1

xk

d k 1d Tk -1 H -1k -1 y k 1 y Tk 1H -1k -1  T  d k -1 y k 1 y Tk 1H -k1-1 y k 1

H -1k -1g ( x k 1 ) ­u k 1  H -1k -1g ( x k 1 ) avec ®s o min f x  su k 1 k 1 s ¯

x k 1  su k 1

d avec ­® k -1 ¯ y k -1

x k  x k -1 g(x k )  g(x k -1 )

Propriété 1 T La mise à jour DFP donne une matrice définie positive si d k -1 y k 1 ! 0 Cette condition est réalisée si xk est obtenu par minimisation exacte dans la direction  H -1k -1g ( x k 1 ) Propriété 2 Pour une fonction f quadratique : f ( x )

1 T x Qx  c T x 2

l’algorithme DFP donne des directions successives vérifiant : o directions conjuguées par rapport à Q o convergence en n itérations avec à l’itération n : H n

­u i Qu j 0 , 0 d i z j d k ® 1 ¯H k Qu i u i , 0 d i d k

Q

251

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode SR1

Equation sécante La méthode SR1 construit une solution Hk de l’équation sécante H k d k 1 • Symétrique, de rang 1 (i.e. dépendante d’un seul vecteur u de Rn) • Non nécessairement définie positive.

y k 1

Méthode de résolution • On cherche la matrice Hk à partir de Hk-1 sous la forme Hk

H k -1  uu T

o addition d’une matrice symétrique de rang 1 y k 1

H k -1d k 1  uu T d k 1 Ÿ y k 1  H k -1d k 1

H k d k 1

•

Equation sécante :

•

On pose :

•

On reporte u pour obtenir J :

•

On exprime uuT en fonction de dk-1, yk-1, Hk-1

1 J

u T d k 1

Ÿ y k 1  H k -1d k 1

­u J y k 1  H k -1d k 1 °1 ® d Tk -1 ( y k 1  H k -1d k 1 ) 2 °¯ J

1 J

1 u Ÿ u J

J y k 1  H k -1d k 1

J ( y k 1  H k -1d k 1 ) T d k 1 Ÿ d Tk -1 ( y k 1  H k -1d k 1 )

Ÿ uu T Ÿ uu T

u T d k 1u

J 2 ( y k 1  H k -1d k 1 )( y k 1  H k -1d k 1 ) T ( y k 1  H k -1d k 1 )( y k 1  H k -1d k 1 ) T d Tk -1 ( y k 1  H k -1d k 1 )

1 J2

252

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Méthode SR1

Formule SR1 ( y k 1  H k -1d k 1 )( y k 1  H k -1d k 1 ) T H k -1  d Tk -1 ( y k 1  H k -1d k 1 )

d avec ­® k -1 ¯ y k -1

•

Mise à jour de Hk : H k

• •

Mise à jour symétrique, de rang 1 Mise à jour non nécessairement définie positive o Méthode alternative à la méthode BFGS (cas d’un hessien indéfini)

x k  x k -1 g(x k )  g(x k -1 )

Limitations • La formule SR1 peut donner des matrices Hk non définies positives, même si le hessien de la fonction est défini positif. • Le dénominateur peut devenir petit o empêche la mise à jour et la convergence Propriété Pour une fonction f quadratique : f ( x )

1 T x Qx  c T x 2

la formule SR1 donne après n déplacements suivant des directions indépendantes dk : H n o ne nécessite pas de minimisation suivant dk

Q

253

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Comparaison

Méthodes de quasi-Newton BFGS  DFP  SR1 BFGS

DFP

SR1

Matrice mise à jour

Hessien Hk

Inverse hessien Hk-1

Hessien Hk

Equation résolue

Sécante

Inverse sécante

Sécante

Méthode

Broyden

Broyden

Résolution directe

Forme solution

Symétrique AAT Rang 2 Définie positive

Symétrique AAT Rang 2 Définie positive

Symétrique uuT Rang 1 Indéfinie

Minimisation dk

Précision moyenne

Précision forte

Précision faible

Fonction quadratique

Hessien exact : Hn=Q Directions conjuguées Q-1

Hessien exact : Hn=Q Directions conjuguées Q

Hessien exact : Hn=Q

Limitations

Hessien de f indéfini

Hessien de f indéfini Précision minimisation

Matrices Hk non définies positives

Méthode BFGS réputée la plus efficace

254

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode de quasi-Newton à une variable Les formules BFGS et SR1 se simplifient pour une fonction à une variable. • Fonction f(x) , xR •

Mise à jour BFGS : H k

Ÿ Hk

•

Mise à jour SR1 :

Hk

Ÿ Hk

y k 1 y Tk -1 H k -1d k 1d Tk 1H k -1 H k -1  T  y k -1d k 1 d Tk 1H k -1d k 1 y H k -1  k 1  H k -1 d k 1 y k 1 g(x k )  g(x k -1 ) d k 1 x k  x k -1 ( y k 1  H k -1d k 1 )( y k 1  H k -1d k 1 ) T H k -1  d Tk -1 ( y k 1  H k -1d k 1 ) y  H k -1d k 1 H k -1  k 1 d k 1 y k 1 g(x k )  g(x k -1 ) d k 1 x k  x k -1

o On retrouve la formule de la sécante appliquée au gradient de f.

255

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Comparaison Newton  Quasi-Newton 4 3 2 • Fonction : f ( x )  x  12 x  47 x  60 x

0,25 0,00

•

Dérivée : f ' ( x )

4 x 3  36 x 2  94 x  60

-0,25 -0,50

•

Quasi-Newton : h k

f ' ( x k )  f ' ( x k -1 ) x k  x k -1

•

Point initial : x0 = 3 o convergence Autres points o divergence ou maximum de f

-1,00

2,75

3,00

x(k) 3,00000000 2,99900000 3,42857155 3,45230465 3,45554876 3,45558934 3,45558940 3,45558940

f(x) 0,00000000 0,00600700 -1,31945027 -1,32362420 -1,32368634 -1,32368635 -1,32368635 -1,32368635

f'(x) -6,00E+00 -6,01E+00 -3,15E-01 -3,79E-02 -4,68E-04 -7,27E-07 -1,40E-11 -5,68E-14

3,50

3,75

4,00

4,25

-0,75

-1,25 -1,50

Quasi - Newton Itération 0 1 2 3 4 5 6 7

3,25

Newton h(k) Erreur 1,000 -4,56E-01 14,000 -4,57E-01 13,267 -2,70E-02 11,672 -3,28E-03 11,527 -4,06E-05 11,509 -6,32E-08 11,509 -1,22E-12 11,462 -4,44E-15

Itération 0 1 2 3 4

x 3,00000000 3,42857143 3,45526446 3,45558935 3,45558940

f(x) 0,00000000 -1,31945023 -1,32368574 -1,32368635 -1,32368635

f'(x) -6,00E+00 -3,15E-01 -3,74E-03 -5,77E-07 -5,68E-14

f''(x) Erreur 14,000 -4,56E-01 11,796 -2,70E-02 11,513 -3,25E-04 11,509 -5,01E-08 11,509 -4,88E-15

256

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode DFP à 2 variables • Minimisation de f ( x ) x 1  x 2  2 x 12  2 x 1 x 2  x 22 •

Point initial : x0 = (0 0)

•

Itération 1 : x 0 x1

•

§1 0· ¸¸ H 01 ¨¨ 0 1 © ¹

§ s· x 0  su 1 ¨¨ ¸¸ o min F(s) s © s¹

g0

§ 1· ¨¨ ¸¸ ©  1¹

o u1

s 2  2s o s 1 o x 1

H 01g 0

§  1· ¨¨ ¸¸ © 1¹

§  1· ¨¨ ¸¸ o g1 © 1¹

§  1· ¨¨ ¸¸ ©  1¹

Mise à jour DFP de H-1

­d 0 ®y ¯ 0 H •

§0· ¨¨ ¸¸ ©0¹

§ 1  4x1  2x 2 · ¸¸ Ÿ g ( x ) ¨¨ ©  1  2x1  2x 2 ¹

-1 1

x1  x 0 o d0 g(x 1 )  g(x 0 )

§  1· ¨¨ ¸¸ , y 0 © 1¹

d 0 d T0 H -10 y 0 y T0 H -10 H  T  d0 y0 y T0 H -01 y 0 -1 0

Comparaison au vrai hessien :

§  2· ¨¨ ¸¸ © 0¹

§ 1 0 · 1 § 1  1· 1 § 4 0 · ¨¨ ¸¸  ¨¨ ¸¸  ¨¨ ¸¸ 0 1 1 1 0 0  2 4 © ¹ © ¹ © ¹

1 § 1  1· ¨ ¸ 2 ¨©  1 3 ¸¹

§ 4 2· ¸¸ Ÿ H 1 H( x ) ¨¨ © 2 2¹

1 § 1  1· ¨ ¸ 2 ¨©  1 2 ¸¹

257

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode DFP à 2 variables •

§  1· Itération 2 : x 1 ¨¨ ¸¸ © 1¹ x2

• •

§  1· g1 ¨¨ ¸¸ o u 2 ©  1¹

§ 1 · ¨¨ ¸¸ o min F(s) 1  3(1  s)  (1  s) 2 o s s ©1  s ¹

§0· H11g1 ¨¨ ¸¸ ©1¹ 1 o x2 2

§  1· ¨¨ ¸¸ o g 2 ©1.5 ¹

§  1· On obtient le minimum en 2 itérations (fonction quadratique) : x* ¨¨ ¸¸ ©1.5 ¹ Mise à jour DFP de H-1

­d1 ®y ¯ 1 H •

x 1  su 2

1 § 1  1· ¨¨ ¸¸ 2 © 1 3 ¹

H1-1

-1 2

x 2  x1 o d1 g(x 2 )  g(x 1 )

§ 0 · ¨¨ ¸¸ , y1 © 0.5 ¹

d1d1T H1-1 y1 y1T H1-1 H  T  d 1 y1 y1T H1-1 y1 -1 1

Comparaison au vrai hessien :

§ 1· ¨¨ ¸¸ © 1¹

1 § 1  1· 1 § 0 0 · § 0 0 · ¨¨ ¸¸  ¨¨ ¸¸  ¨¨ ¸¸  1 3 0 1 0 1 2© ¹ 2© ¹ © ¹

1 § 1  1· ¨¨ ¸¸ 1 2 2 © ¹

§ 4 2· ¸¸ Ÿ H 1 H( x ) ¨¨ © 2 2¹

1 § 1  1· ¨ ¸ 2 ¨©  1 2 ¸¹

258

§0· ¨¨ ¸¸ ©0¹

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.2 Minimisation

Techniques d’optimisation 2.2.2 Exemple

Méthode DFP à 2 variables On vérifie les propriétés de la méthode DFP appliquée à une fonction quadratique. f ( x ) x1  x 2  2x  2x1x 2  x 2 1

1 § x1 · ¨¨ ¸¸ 2 ©x2 ¹

2 2

T

§ 4 2 · § x1 · § 1 · ¨¨ ¸¸ ¨¨ ¸¸  ¨¨ ¸¸ © 2 2 ¹ © x 2 ¹ ©  1¹

T

§ x1 · § 4 2· ¨¨ ¸¸ o Q ¨¨ ¸¸ x 2 2 © 2¹ © ¹

•

Le minimum est obtenu en 2 itérations.

•

Les directions successives u1 et u2 sont conjuguées par rapport à Q

•

§ 0 · § 4 2 ·§  1· ¸¸¨¨ ¸¸ u T2 Qu 1 ¨¨ ¸¸ ¨¨ 1 2 2 © ¹ © ¹© 1¹ On vérifie également :

T

H11Qu 1 H 21Qu 2

1 § 1  1·§ 4 ¨ ¸¨ 2 ¨©  1 3 ¸¹¨© 2 1 § 1  1·§ 4 ¨ ¸¨ 2 ¨©  1 2 ¸¹¨© 2

§ 0· ¨¨ ¸¸ ©1¹

T

§  2· ¨¨ ¸¸ © 0¹

2 ·§  1· ¸¨ ¸ 2 ¸¹¨© 1¸¹ 2 ·§ 0 · ¸¨ ¸ 2 ¸¹¨© 1 ¸¹

0

1 § 2 0 ·§  1· ¨ ¸¨ ¸ 2 ¨© 2 4 ¸¹¨© 1¸¹ § 1 0 ·§ 0 · § 0 · ¨¨ ¸¸¨¨ ¸¸ ¨¨ ¸¸ 0 1 © ¹© 1 ¹ © 1 ¹

§  1· ¨¨ ¸¸ © 1¹ u2

u1 avec H 21

Q 1

259

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.3 Globalisation

Techniques d’optimisation 2.2.3 Globalisation

‰ Difficultés de la méthode de Newton ‰ Méthodes de globalisation ‰ Point de Newton et de Cauchy

260

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.3 Globalisation

Techniques d’optimisation 2.2.3 Globalisation

Difficultés de la méthode de Newton La convergence n’est pas garantie même près de la solution. On ne peut appliquer directement l’itération de Newton. o techniques de globalisation pour vérifier et améliorer le point de Newton Vérification du point de Newton Le point xk+1 doit être meilleur que xk pour être accepté. •

Pour une résolution d’équation :

g( x )

•

Pour une minimisation :

min f ( x ) x

0

Ÿ g(x k 1 )  g(x k )

0 Ÿ f(x k 1 )  f(x k )

Techniques de globalisation Si le point xN obtenu par l’itération de Newton ne vérifie pas les conditions d’amélioration, on procède à une recherche locale au voisinage de xk. •

Méthode de recherche linéaire :

•

Méthode de région de confiance : à l’intérieur d’une sphère de centre xk

suivant la direction du point de Newton xN

261

2 Optimisation sans contraintes 2.2 Méthode de Newton 2.2.3 Globalisation

Techniques d’optimisation 2.2.3 Point de Newton et de Cauchy

Points particuliers Deux points particuliers sont définis à partir du modèle quadratique de f en xk : 1 ’ f k (x k ) ­g fˆk (x) f k (x k )  g Tk (x  x k )  (x  x k ) T H k (x  x k ) avec ® k 2 2 ¯H k ’ f k (x k ) • Point de Newton o points utiles dans les algorithmes de globalisation • Point de Cauchy Point de Newton Le point de Newton xN de f en xk minimise le modèle quadratique en xk. xN n’existe que si ’2f(xk) est définie positive.

xN

x k  d N avec ’ 2 f(x k )d N

’f(x k )

o dN solution des équations de Newton

Point de Cauchy Le point de Cauchy xC de f en xk minimise le modèle quadratique en xk dans la direction gk.

xC

x k  Į C g k solution de min f(x k  ĮJ k ) Įt0

Si f est convexe suivant –gk : Į C

o minimum suivant la plus forte descente

g Tk g k g Tk H k g k

262

2 Optimisation sans contraintes 2.3 Recherche linéaire

Techniques d’optimisation Sommaire

1.

Bases théoriques

2.

Optimisation sans contraintes 2.1 Méthodes de descente 2.2 Méthode de Newton 2.3 Recherche linéaire 2.3.1 Principes 2.3.2 Direction de descente 2.3.3 Pas de déplacement 2.3.4 Algorithme 2.4 Région de confiance 2.5 Moindres carrés 2.6 Méthode de Nelder-Mead

3.

Optimisation avec contraintes 263

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.1 Principes

Techniques d’optimisation 2.3.1 Recherche linéaire

Problème sans contrainte minn f(x) xR

Etapes principales A chaque itération • Construction d’une direction de descente dk à partir du point xk • Réglage du pas de déplacement sk suivant dk

Initialisation x0

Point initial xk

Direction de descente dk

Solution x*

Nouveau point

Pas de déplacement sk

xk+1=xk+skdk

264

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.1 Principes

Techniques d’optimisation 2.3.1 Recherche linéaire

Etapes principales A chaque itération • Construction d’une direction de descente dk à partir du point xk • Réglage du pas de déplacement sk suivant dk Direction de descente dk est une direction de descente en xk si • •

’f(xk)Tdk < 0

La direction de descente est construite à partir du gradient et du hessien. Plus forte pente o gradient (méthode d’ordre 1) Préconditionnement o hessien (méthode d’ordre 2)

Pas de déplacement Le pas de déplacement sk suivant dk doit vérifier • •

f(xk+skdk) < f(xk)

L’algorithme de recherche linéaire résout un problème de minimisation à une variable s Minimisation exacte o dichotomie (Fibonacci, nombre d’or, interpolation) Minimisation approchée o règles de pas acceptable (Armijo, Goldstein, Wolfe)

265

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.2 Direction de descente

Techniques d’optimisation 2.3.2 Direction de descente

‰ Plus forte pente ‰ Préconditionnement

266

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.2 Direction de descente

Techniques d’optimisation 2.3.2 Direction de descente

Plus forte pente La direction de descente « naturelle » est celle du gradient = plus forte dérivée directionnelle dk

• •

’f(x k )

Comportement caractéristique en zigzag Convergence très lente o méthode inefficace en général

Illustration lignes de niveau de f

x*

267

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.2 Direction de descente

Techniques d’optimisation 2.3.2 Direction de descente

Plus forte pente Les directions successives de plus forte pente avec pas optimal sont orthogonales. •

Itération k On cherche le minimum de f à partir de xk suivant la direction dk = ’f(xk) Le nouveau point est xk+1 = xk + sdk avec le pas s>0 solution de : d min f x k  sd k Ÿ f x k  sd k 0 Ÿ d Tk ’f x k  sd k 0 Ÿ d Tk ’f x k 1 0 sR ds

•

Itération k+1 La direction de plus forte pente en xk+1 est dk+1 = ’f(xk+1) Ÿ d Tk d k 1

0

Illustration xk+1 dk=’f(xk)

lignes de niveau de f dk+1=’f(xk+1)

xk

268

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.2 Direction de descente

Techniques d’optimisation 2.3.2 Exemple

Plus forte pente •

Fonction 1 2 9 2 f (x) x1  x 2 2 2

•

Direction §  x1 · ¸¸ ’f ( x ) ¨¨ ©  9x 2 ¹

d

•

Iteration x1 9,000 0 1 7,200 2 5,760 3 4,608 4 3,686 5 2,949 10 0,966 20 0,104 30 1,11E-02 40 1,20E-03 50 1,28E-04

d2 -9,000 7,200 -5,760 4,608 -3,686 2,949 -0,966 -0,104 -1,11E-02 -1,20E-03 -1,28E-04

s 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2

Erreur 9,055 7,244 5,795 4,636 3,709 2,967 0,972 0,104 1,12E-02 1,20E-03 1,29E-04

0,75

min f ( x  sd )

0,50

s

x 12  81x 22 x 12  729 x 22

0,25 0,00 -1

•

d1 -9,000 -7,200 -5,760 -4,608 -3,686 -2,949 -0,966 -0,104 -1,11E-02 -1,20E-03 -1,28E-04

1,00

Pas

os

x2 f(x) 1,000 45,000 -0,800 28,800 0,640 18,432 -0,512 11,796 0,410 7,550 -0,328 4,832 0,107 0,519 0,012 0,006 1,24E-03 6,90E-05 1,33E-04 7,95E-07 1,43E-05 9,17E-09

Itération

x k 1

x k  skdk

0

1

2

3

4

5

6

7

8

9

10

-0,25 -0,50 -0,75 -1,00

269

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.2 Direction de descente

Techniques d’optimisation 2.3.2 Direction de descente

Préconditionnement • On se donne une matrice Hk matrice symétrique définie positive. o factorisation de Cholesky de Hk : Hk = LkLkT • • • • •

LTk x k

~ Direction de plus forte pente pour : f (~ x k ) f(x k ) f(LkT ~ xk ) ~ ~ d k ’ f (~ x k ) ’f(LkT ~ x k ) Lk1’f(LkT ~ x k ) Lk1’f(x k ) Lk1d k ~ ~ x x  s ’ f (~ x ) Itération en ~ x : ~ k

k 1

Itération en xk : x k 1 Ÿ x k 1

k

k

LkT ~ x k 1

k



~ LkT ~ x k  s k ’ f (~ xk )

x k  s k LkT Lk1d k





LkT LTk x k  s k Lk1d k



x k  s k H k1d k

Le préconditionnement par la matrice Hk consiste à prendre comme direction de descente dk

•

~ xk

Changement de variable :

H k1’f(x k )

On vérifie que dk est une direction de descente d Tk ’f(x k ) ’f(x k ) T H k1’f(x k )  0 car Hk est définie positive

270

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.2 Direction de descente

Techniques d’optimisation 2.3.2 Direction de descente

Choix du préconditionnement Toute matrice Hk symétrique définie positive convient. Cas d’un hessien défini positif • Si le hessien ’2f(xk) est défini positif, on peut prendre dk

H k1’f(x k )

’ 2 f(x k ) 1 ’f(x k )

Ÿ x k 1

’ 2 f(x k ) 1.

Hk

x k  s k ’ 2 f(x k ) 1 ’f(x k )

On obtient l’itération de Newton si le pas sk vaut 1. •

On peut prendre pour Hk l’approximation du hessien donné par une méthode quasi-Newton.

Cas d’un hessien non défini positif • On peut effectuer la factorisation de Cholesky modifiée du hessien ’2f(xk) (ou son approximation quasi Newton) pour obtenir une matrice définie positive. • •

On peut ajouter un multiple de l’identité : H k On peut également prendre Hk diagonale : H k i à partir des dérivées secondes de f

’ f(x 2

k )  WI



1

avec W > 0 assez grand

1 § § w 2f · · ¨ max H, ¨¨ 2 (x k ) ¸¸ ¸ , H ! 0 ¨ wx ¸ i © ¹ © ¹

271

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.2 Direction de descente

Techniques d’optimisation 2.3.2 Exemple

Préconditionnement • • •

Fonction :

1 2 9 2 f (x) x1  x 2 2 2

§1 0· ¸¸ Préconditionnement : L ¨¨ 0 3 © ¹ x · ~ ~ ~ §~ Direction : d ’ f ( x ) ¨¨ ~ 1 ¸¸ © x2 ¹

§ x · §1 0· §1 0·§1 0· Ÿ ’f ( x ) ¨¨ 1 ¸¸ Ÿ ’ 2 f ( x ) ¨¨ ¸¸ ¨¨ ¸¸ ¨¨ ¸¸ 9 x © 2¹ © 0 9¹ © 0 3¹ © 0 3¹ 2 ~ ~ ~ 1 ~2 9 § 1 · 1 ~2 1 ~2 x1 x1 ­ Ÿ ®~ Ÿ f (x) x1  ¨ x 2 ¸ x1  x 2 x 3 x 2 2 3 2 2 2 ¯ 2 ¹ © 2,00

1,50

~ ~ min f (~ x  sd ) o s 1

•

Pas :

•

Itération : ~ x k 1

1,00

s

~ ~ x k  s k dk

0,50

0

o convergence en 1 itération

T

0,00 -1

0

1

2

3

4

-0,50

-1,00

272

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Pas de déplacement

‰ Minimisation unidimensionnelle ‰ Minimisation exacte - Méthode de dichotomie - Méthode de Fibonacci - Méthode du nombre d’or - Interpolation quadratique ‰ Minimisation approchée - Règle d’Armijo - Règle de Goldstein - Règle de Wolfe

273

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation

2.3.3 Minimisation unidimensionnelle Problème à une variable

min f(x)

f(x)

xR

minimum local

minimum global

x

Méthodes • Minimisation exacte On cherche à trouver un minimum local x* avec une précision donnée o réduction itérative de l’intervalle de recherche : dichotomie o réduction optimale : Fibonacci, nombre d’or •

Minimisation approchée On cherche une réduction suffisante de la fonction sans déterminer précisément le minimum x* o règles d’acceptation (Armijo, Goldstein, Wolfe) o limitation du nombre d’évaluations de la fonction

274

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Recherche par dichotomie L’allure de la fonction f n’est pas connue. On suppose qu’il existe un minimum unique dans l’intervalle de recherche [a,d] • On évalue la fonction aux extrémités a et d : o f(a) , f(d) • On évalue la fonction en 2 points b et c : a < b < c < d o f(b) , f(c) • On conserve soit l’intervalle [a,c], soit l’intervalle [b,d]

f(x)

f(x)

a

b

c

On conserve [a,c]

d

x

a

b

c

d

x

On conserve [b,d]

275

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Réduction optimale de l’intervalle • On cherche b et c pour que l’intervalle restant soit le plus petit possible. La taille de l’intervalle restant ne doit pas dépendre du choix de [a,c] ou [b,d]. • On note : '1 la longueur de l’intervalle initial o '1 = d  a '2 la longueur de l’intervalle restant o '2 = c  a si on garde [a,c] ou '2 = d  b si on garde [b,d] '2

f(x)

db ca

Ÿ ad bc Ÿ

'1

ad 2

bc 2

'2 '2

a

b

Les points b et c doivent être symétriques par rapport au milieu de l’intervalle [a,d]. c

d

x

276

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Réduction optimale de l’intervalle • On suppose que l’intervalle restant est [a,c]. • Pour réutiliser le point b à l’itération suivante, on choisit le nouveau point e symétrique de b par rapport au milieu de l’intervalle [a,c]. o '1 = d  a o '2 = c  a = d  b o '3 = b  a = c  e d  a d  b  b  a Ÿ '1 ' 2  ' 3

f(x) '1 '2

Les longueurs 'k des intervalles successifs vérifient :

'2

'3

' k ' k 1  ' k  2

'3 a

e

b

c

d

x

277

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Réduction optimale de l’intervalle • Les intervalles successifs sont de longueur 'k vérifiant : 'k = 'k+1 + 'k+2 •

Après un nombre N d’itérations, on obtient un intervalle de longueur 'N1 .

•

On définit la suite de nombres Fk par :

•

La suite (Fn)n=1,…,N1 vérifie ǻ k ǻ k 1  ǻ k  2 Ÿ

ǻk ǻ N 1

ǻ N 1 F1ǻ N 1 pour k

•

'k = FNk 'N1 pour k = 1,…,N1

ǻ k 1 ǻ k  2  Ÿ FN  k FN  k 1  FN  k  2 ǻ N 1 ǻ N 1 Ÿ Fn Fn 1  Fn  2 pour n

N 1

Ÿ F1

N  k, n

3,4,..., N  1

1

La suite est complètement déterminée par la valeur de F2 ­°F1 1 ®F2 à choisir °¯Fn Fn -1  Fn - 2 pour n

3,4,..., N  1

278

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Méthode de Fibonacci • Pour un nombre N d’itérations fixé, on choisit F2 pour que 'N-1 soit minimal. ǻ1 ǻ N -1 minimal Ÿ FN -1 maximal Ÿ F2 maximal FN -1 1 1 1 · § • Valeur maximale de F2 : ǻ N -1 t ǻ N -2 ¨ car ǻ k t ǻ k -1 ¸ Ÿ F1 t F2 Ÿ F2 max 2 2 2 ¹ © •

2

On obtient la suite de Fibonacci : 1, 2, 3, 5, 8, 13, 21, …

Nombre d’itérations La méthode de Fibonacci est optimale si l’on fixe à l’avance la précision requise sur la solution. • Précision requise : 'N-1 = p ǻ1 b-a Ÿ ǻ N -1 Ÿ FN -1 o valeur de N • Intervalle initial [a,b] : ' 1 = b-a FN -1 p La méthode de Fibonacci donne le nombre minimal d’itérations N pour obtenir la solution avec une précision donnée. •

La disposition des premiers points b et c dépend de N :

ǻ1 ǻ2

FN -1 FN - 2

o '2

279

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Méthode du nombre d’or La méthode de Fibonacci nécessite de changer la disposition des points à chaque itération. La disposition des points n’est optimale que pour une précision donnée. La méthode du nombre d’or est plus générale et plus simple à mettre en oeuvre. •

On impose un rapport de réduction fixe de l’intervalle à chaque itération. ǻ1 ǻ 2 ǻ ǻ k 1 ... k ... Ȗ avec ǻ k ǻ k 1  ǻ k  2 ǻ2 ǻ3 ǻ k 1 ǻ k  2 ǻk ǻ 1 1  k2 Ÿ Ȗ 1  Ÿ Ȗ 2  Ȗ 1 0 Ÿ ǻ k 1 ǻ k 1 Ȗ

•

Ȗ On obtient pour le rapport J le nombre d’or : o Méthode du nombre d’or (ou de la section dorée)

1 5 | 1.618034 2

Optimalité • La méthode du nombre d’or n’est pas optimale pour un nombre d’itérations donné N. •

Pour un nombre d’itérations grand : Nlim of

FN FN -1

Ȗ

o La disposition des points de Fibonacci tend vers celle du nombre d’or.

280

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Comparaison Fibonacci - Nombre d’or Le rapport de réduction de l’intervalle après n itérations vaut : • •

ǻ1 ǻn ǻ1 Pour la méthode du nombre d’or : ǻn

Pour la méthode de Fibonacci :

Fn Ȗ n 1

Nombre d’itérations Une itération de la méthode de Fibonacci ou du nombre d’or correspond à une évaluation de f. Nombre d’évaluations Rapport de réduction

Fibonacci

Nombre d’or

10-2

11

13

10-3

15

18

10-4

20

22

10-5

25

27

10-6

30

31

281

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Méthode du nombre d’or • Positionnement des points ǻ1 ǻ2

­ °°ǻ 2 Ÿ ® °ǻ 3 °¯

ǻ2 ǻ3

Ȗ

1 ǻ1 Ȗ 1 ǻ1 Ȗ2

1 5 | 1.618034 2

rǻ1 r 2 ǻ1

avec r

1 Ȗ

f(x) '1 5 1 | 0.618034 2

'2

•

a Itération ­d °c Si f (b)  f (c) o ®ǻ ° 1 ¯b

'2

'3

­b a  r 2 ǻ 1 ° Ÿ ®c a  rǻ1 °¯d a  ǻ1

mc mb m ǻ2 a  r 2 ǻ1

b

c

d

­a m b °b m c Si f (b) ! f (c) o ® ǻ m ǻ2 ° 1 ¯c a  rǻ1

282

x

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Exemple

Méthode du nombre d’or S • Minimisation de f ( x )  x cos( x ) , 0 d x d 2 • • • •

Itération 1

Itération 2

Itération 3

Itération 4

f

0

-0.4952

-0.5482

0

x

0

0.6000

0.9708

1.5708

-0.5482

-0.4350

0

0.6000

0.9708

1.2000

1.5708

f -0.4952

-0.5601

-0.5482

-0.4350

0.6000

0.8292

0.9708

1.2000

f -0.4952

-0.5468

-0.5601

-0.5482

0.6000

0.7416

0.8292

0.9708

f

-0.5468

-0.5601

-0.5606

-0.5482

x

0.7416

0.8292

0.8832

0.9708

f -0.4952 x

x

x

• •

Itération 5

Solution : x* | 0.8832 o f(x*) | 0.5606 au lieu de x* | 0.8603 o f(x*) | 0.5611

283

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Interpolation quadratique •

On connaît la valeur de la fonction f en 3 points x1, x2, x3. ­° y1 ®y 2 °¯ y 3

•

y3 y2

On construit le polynome q de degré 2 passant par les 3 points. q( x )

•

f (x1 ) f (x 2 ) f (x 3 )

y1

x1

x2

x3

­°q ( x 1 ) y1 y1  y2  y3 o ®q ( x 2 ) y 2 ( x 1  x 2 )( x 1  x 3 ) ( x 2  x 3 )( x 2  x 1 ) ( x 3  x 1 )( x 3  x 2 ) °¯q ( x 3 ) y 3 ( x  x 2 )( x  x 3 )

( x  x 3 )( x  x 1 )

( x  x 1 )( x  x 2 )

Dérivée du polynome q q' ( x )

y1

(2x  x 2  x 3 ) (2x  x 3  x 1 ) (2x  x 1  x 2 )  y2  y3 ( x 1  x 2 )( x 1  x 3 ) ( x 2  x 3 )( x 2  x 1 ) ( x 3  x 1 )( x 3  x 2 )

On obtient une approximation du minimum de f en minimisant q.

284

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Interpolation quadratique •

La dérivée du polynome q s’écrit : q' ( x )

y1

(2x  x 2  x 3 ) (2x  x 3  x 1 ) (2x  x 1  x 2 )  y2  y3 ( x 1  x 2 )( x 1  x 3 ) ( x 2  x 3 )( x 2  x 1 ) ( x 3  x 1 )( x 3  x 2 )

>

Ÿ q' ( x )

 2 x>y1 ( x 2  x 3 )  y 2 ( x 3  x 1 )  y 3 ( x 1  x 2 )@  y1 ( x 22  x 32 )  y 2 ( x 32  x 12 )  y 3 ( x 12  x 22 ) ( x 1  x 2 )( x 2  x 3 )( x 3  x 1 )

Ÿ q' ( x )

­s ij  2 x y1s 23  y 2 s 31  y 3s12  y1r23  y 2 r31  y 3 r12 avec ® ( x 1  x 2 )( x 2  x 3 )( x 3  x 1 ) ¯rij

•

@

xi  x j x i2  x 2j

On cherche la valeur xm qui annule la dérivée du polynome q. q' ( x m )

0 Ÿ 2 x m >y1s 23  y 2 s 31  y 3s12 @  >y1r23  y 2 r31  y 3 r12 @ 0 Ÿ xm

1 y1r23  y 2 r31  y 3 r12 2 y1s 23  y 2 s 31  y 3s12

­s ij avec ® ¯rij

xi  x j x i2  x 2j

285

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation exacte

Interpolation quadratique • On évalue la valeur de la fonction en xm o ym = f(xm) o On dispose de 4 points x1, x2, x3, xm avec les valeurs respectives de f : y1, y2, y3, ym o On conserve 3 points choisis parmi x1, x2, x3, xm selon : - la position de xm par rapport à x1, x2, x3 - le minimum parmi ym, y1, y2, y3 Points retenus

xm < x1

x1 < xm < x2

x2 < xm < x3

x3 < xm

Minimum = ym

(xm,x1,x2)

(x1,xm,x2)

(x2,xm,x3)

(x2,x3,xm)

Minimum = y1

(xm,x1,x2)

(x1,xm,x2)

(x1,x2,xm)

divergence

Minimum = y2

divergence

(xm,x2,x3)

(x1,x2,xm)

divergence

Minimum = y3

divergence

(xm,x2,x3)

(x2,xm,x3)

(x2,x3,xm)

Cas de divergence : Le polynome est trop éloigné de la fonction Il faut un balayage plus fin avant l’interpolation quadratique. •

On réitère l’interpolation quadratique avec les 3 nouveaux points jusqu’à réduire la taille de l’intervalle à la précision souhaitée.

286

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Exemple

Interpolation quadratique • Minimisation de f ( x ) ( x  1)( x  1) 2 , 0 d x d 2 • • • •

Itération 1

f -1.0000

-1.1816

0.0000

9.0000

x

0.3750

1.0000

2.0000

-1.1814

-1.1816

0.0000

0.2895

0.3750

1.0000

-1.1852

-1.1816

0.0000

0.2895

0.3327

0.3750

1.0000

f -1.1814

-1.1852

-1.1852

-1.1816

0.2895

0.3327

0.3329

0.3750

f

-1.1852

-1.1852

-1.1852

-1.1816

x

0.3327

0.3329

0.3333

0.3750

f -1.0000

Itération 2

x

•

Itération 3

x

Itération 4

Itération 5

Solution :

0

f -1.1814

x

•

0

x* | 0.3333 o

f(x*) | 1.1852

287

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation approchée

Principes • Il n’est pas utile de réaliser une minimisation exacte suivant la direction de descente : o nécessite un grand nombre d’évaluations de la fonction o n’apporte pas une amélioration significative loin de la solution • On peut se contenter d’une minimisation approchée o 2 règles d’acceptation d’un pas de déplacement Notations • xk = point courant o f(xk) • dk = direction de descente o ’f(xk)Tdk < 0 •

Variation de la fonction f dans la direction dk :

M(s)

Règles d’acceptation du pas • Diminution suffisante de la valeur de la fonction •

Déplacement suffisant par rapport au point initial

f ( x k  sd k ), s t 0

o condition d’Armijo 1ère condition de Wolfe o condition de Goldstein 2ème condition de Wolfe

288

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation approchée

Diminution suffisante La fonction f doit décroître suffisamment pour accepter le pas. • Dérivée directionnelle de f suivant la direction dk M(s)

•

f ( x k  sd k ), s t 0 Ÿ

M' (0)

’f ( x k ) T d k  0

On impose une diminution proportionnelle à la dérivée directionnelle, avec 0 < H < c1 < 0.5 M(s)  M(0)  c1sM' (0)

œ

f ( x k  sd k )  f ( x k )  c1s’f ( x k ) T d k

o valeur typique c1=0.1

o Condition d’Armijo ou 1ère condition de Wolfe ou 1ère condition de Goldstein f(x)=M(s)

pas acceptables

s o x = xk+sdk

c1M’(0) M’(0)

289

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation approchée

Déplacement suffisant Le déplacement à partir du point initial doit être suffisant pour accepter le pas. • Condition de Goldstein M(s) ! M(0)  c 2 sM' (0)

•

œ f ( x k  sd k ) ! f ( x k )  c 2 s’f ( x k ) T d k

o valeur typique c2=0.9

Condition de Wolfe : réduction de la dérivée M' (s) ! c 2 M' (0)

f(x)=M(s)

œ ’f ( x k  sd k ) T d k ! c 2 ’f ( x k ) T d k

f(x)=M(s)

pas acceptables (Goldstein)

o valeur typique c2=0.9

pas acceptables (Wolfe)

s

M’(0)

c2M’(0)

s

M’(0)

c2M’(0)

290

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Minimisation approchée

Récapitulatif • Conditions de Goldstein (si la dérivée de f est coûteuse) •

Conditions de Wolfe (si la dérivée de f est disponible) ou

­M(s)  M(0)  c1sM' (0) o c1 | 0.1 ®M(s) ! M(0)  c sM' (0) o c | 0.9 2 2 ¯ ­M(s)  M(0)  c1sM' (0) o c1 | 0.1 ®M' (s) ! c M' (0) o c 2 | 0.9 2 ¯ M' (s)  c 2 M' (0) o assure théoriquement la convergence pas acceptables (Goldstein)

f(x)=M(s)

s o x = xk+sdk

c1M’(0) M’(0)

c2M’(0)

291

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Réglage du pas

Méthode de dichotomie

­M(s)  M(0)  c sM' (0) On cherche un pas s vérifiant les conditions de Goldstein : ®M(s) ! M(0)  c1 sM' (0) 2 ¯ Initialisation • Intervalle initial : •

Valeur initiale :

[smin , smax] avec smin = 0 smax assez grand s=1 (pas de Newton)

Itérations Evaluation de M(s) et comparaison aux droites de Goldstein • Si s ne respecte pas la condition 1 o amélioration insuffisante, pas trop grand : • Si s ne respecte pas la condition 2 o déplacement insuffisant, pas trop petit: o Réduction de l’intervalle [smin , smax] o Essai suivant : s

smax=s smin=s

1 ( s min  s max ) 2

Arrêt • Si s respecte les 2 conditions o pas acceptable • Si l’intervalle [smin , smax] devient inférieur à un seuil donné

292

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.3 Pas de déplacement

Techniques d’optimisation 2.3.3 Réglage du pas

Illustration M(s) smin

s2

s3

s1

smax

s

c1M’(0) c2M’(0)

293

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.4 Algorithme

Techniques d’optimisation 2.3.4 Algorithme

‰ Algorithme de recherche linéaire ‰ Convergence ‰ Exemple

294

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.4 Algorithme

Techniques d’optimisation 2.3.4 Algorithme

Algorithme de recherche linéaire Initialisation : x0 Gradient : ’f(x0) Approximation du hessien : H0

Itération k : xk Gradient : ’f(xk) Approximation du hessien : Hk>0

o H0 =I par défaut

Direction de descente : d k

H k1’f(x k )

Recherche linéaire suivant dk o pas sk Règle de Goldstein ou Wolfe Arrêt si : ’f(x k 1 )  İ

Itération k+1 : xk+1 Gradient : ’f(xk+1) Approximation du hessien : Hk+1>0

Nouveau point : xk+1 = xk + sk dk Gradient : ’f(xk+1) Mise à jour du hessien par BFGS ou SR1 Modification du hessien : Hk+1>0 Factorisation de Cholesky modifiée

295

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.4 Algorithme

Techniques d’optimisation 2.3.4 Algorithme

Principaux résultats de convergence • Si d est une direction de descente, et f est bornée inférieurement suivant d, alors il existe un pas s suivant d vérifiant les conditions de Wolfe •

Si les directions de descente ne deviennent pas « trop » orthogonales au gradient, l’algorithme de recherche linéaire avec les conditions de Wolfe est globalement convergent. lim ’f ( x k ) 0 o convergence vers un point stationnaire

k of

En pratique • Les directions de descente peuvent être construites avec BFGS ou SR1 (si matrices Hk > 0) •

La valeur des coefficients de Goldstein ou Wolfe c1 et c2 n’est pas critique pour la convergence.

•

Le pas de Newton (s=1) est systématiquement testé, car il donne la solution si la fonction est proche de son modèle quadratique.

•

La méthode de plus forte pente a la propriété de convergence globale, mais peut être très lente. On peut assurer la convergence globale d’un algorithme de recherche linéaire utilisant d’autres directions en effectuant périodiquement une itération de plus forte pente.

296

2 Optimisation sans contraintes 2.3 Recherche linéaire 2.3.4 Algorithme

Techniques d’optimisation 2.3.4 Exemple

Fonction de Rosenbrock



5



f ( x1 , x 2 ) 100 x 2  x12  1  x1 • •

2

2

f

4 3

 1.2 · Point initial : §¨ ¨ 1 ¸¸ © ¹

BFGS SR1

2

Recherche linéaire avec BFGS ou SR1

1 Itération 0 0

1,25

10

20

-1

BFGS

SR1

1

1

0,75

0,75

0,5

0,5

0,25

0,25

-0,5

0 0

-0,25

40

1,25

0 -1,5

30

0,5

1

1,5

-1,5

-1

-0,5

0 -0,25

0,5

1

1,5

297

2 Optimisation sans contraintes 2.4 Région de confiance

Techniques d’optimisation Sommaire

1.

Bases théoriques

2.

Optimisation sans contraintes 2.1 Méthodes de descente 2.2 Méthode de Newton 2.3 Recherche linéaire 2.4 Région de confiance 2.4.1 Principes 2.4.2 Modèle quadratique 2.4.3 Rayon de confiance 2.4.4 Algorithme 2.5 Moindres carrés 2.6 Méthode de Nelder-Mead

3.

Optimisation avec contraintes 298

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.1 Principes

Techniques d’optimisation 2.4.1 Région de confiance

Problème sans contrainte minn f(x) xR

Etapes principales A chaque itération • Résolution d’un modèle quadratique dans un rayon rk autour du point xk o déplacement dk • Réglage du rayon de confiance rk pour obtenir une amélioration de f

Initialisation x0

Point initial xk

Modèle quadratique dk

Solution x*

Nouveau point

Rayon de confiance rk

xk+1=xk+dk

299

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.1 Principes

Techniques d’optimisation 2.4.1 Région de confiance

Illustration x0

modèle quadratique en x0

x1

modèle quadratique en x1

modèle quadratique en x2 x2 x*

300

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Modèle quadratique

‰ Problème de région de confiance ‰ Conditions d’optimalité ‰ Résolution approchée ‰ Méthode dogleg

301

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation

2.4.2 Problème de région de confiance Modèle quadratique • Au point courant xk on approxime la fonction par son modèle quadratique. dRn = déplacement à partir du point xk 1 fˆk ( x k  d ) f ( x k )  d T ’f ( x k )  d T ’ 2 f ( x k )d 2 • Le modèle quadratique représente correctement la fonction au voisinage de xk dans un rayon rk La région de confiance est le voisinage dans lequel l’approximation est « bonne » (à définir). Région de confiance de rayon rk : rk = rayon de confiance en xk

d d rk

Problème de région de confiance • On cherche le minimum du modèle quadratique à l’intérieur de la région de confiance

min fˆk ( x k  d ) sous d d rk dR n

•

o Problème de région de confiance

On peut choisir différentes normes pour définir la région de confiance - Norme 2 : région de confiance circulaire - Norme f : région de confiance rectangulaire

302

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation

2.4.2 Problème de région de confiance Notations • Point courant : xk noté x0 • Fonction : f(xk) noté f0 • Gradient : ’f(xk) noté g0 • Hessien : ’2f(xk) noté H0 • Déplacement à partir de x0 :dRn • • •

1 fˆ (d ) f 0  d T g 0  d T H 0 d Fonction modèle : 2 Région de confiance : d d r 1 Problème de région de confiance : minn fˆ (d ) f 0  d T g 0  d T H 0 d sous d d r dR 2 x0 -g0

dN xN

lignes de niveau du modèle quadratique

303

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Conditions d’optimalité

Région de confiance en norme 2 Le problème de région de confiance s’écrit avec la norme 2



• •



1 1 2 f 0  d T g 0  d T H 0 d sous d  r2 d 0 dR 2 2 1 1 2 L(d , P ) f 0  d T g 0  d T H 0 d  P d  r 2 Lagrangien : 2 2 minn fˆ (d )





­’ L(d*, ȝ g  H d * ȝ * d* 0 0 0 °° d Conditions d’ordre 1 : ® d * d r , ȝ t 0 ° 2 2 0 œ ȝ * d *  r 0 °¯ȝ * d *  r





Contrainte de région de confiance • Si la contrainte de région de confiance est inactive, la contrainte peut être ignorée. La solution du problème quadratique sans contrainte est le point de Newton. •

Si la contrainte de région de confiance est active, la solution est au bord de la région de confiance : d * r Ÿ H 0  P * I d* g 0 On peut alors montrer que H 0  P * I est semi-définie positive. Le problème quadratique est résolu avec la méthode de Newton et la matrice H 0  P * I t 0

304

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Résolution approchée

Résolution du problème quadratique

1 f 0  d T g 0  d T H 0 d sous d d r 2

•

On doit résoudre à chaque itération le problème : minn fˆ (d )

•

Le problème doit éventuellement être résolu pour plusieurs valeurs du rayon. o résolution coûteuse si la contrainte est active o solution approximative par une méthode simplifiée (méthode dogleg)

dR

Point de Newton Le point de Newton xN est la solution du problème quadratique sans contrainte.

minn fˆ (d ) dR

1 f 0  d T g 0  d T H 0d 2

Ÿ dN

H 01g 0 Ÿ x N

x0  dN

Point de Cauchy Le point de Cauchy xC minimise le critère quadratique suivant le gradient : d C

min fˆ (sg 0 ) sR

1 f 0  sg g 0  s 2 g T0 H 0 g 0 2 T 0

Ÿ sC

g T0 g 0 g T0 H 0 g 0

Ÿ dC

s C g 0 Ÿ x C

sg 0 , s t 0

x0  dC

305

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Résolution approchée

Résolution du problème quadratique

minn fˆ (d ) dR

1 f 0  d T g 0  d T H 0 d sous d d r 2

o solution d(r)Rn, x(r) = x0 + d(r)

Lorsque le rayon de confiance r varie, la solution suit une courbe x(r) allant de x0 à xN. • r=0 o x(0) = x0 (tangente = g0) • r > _dN_ o x(r) = xN r x0 x(r)

g0

xN

lignes de niveau du modèle quadratique

306

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Méthode dogleg

Chemin dogleg Le chemin dogleg est composé de 2 segments : • Le segment 1 joignant le point initial x0 au point de Cauchy xC = x0 + dC • Le segment 2 joignant le point de Cauchy x0 au point de Newton xN = x0 + dN On restreint la recherche de la solution au chemin dogleg. Paramétrage du chemin dogleg Le chemin dogleg est paramétré par s : x(s) = x0 + d(s) , pour s[0,2] • Segment 1 o d(s) = sdC pour s[0,1[ • Segment 2 o d(s) = dC + (s1)(dN  dC) pour s[1,2] x0 dN

dC xC

xN

lignes de niveau du modèle quadratique

307

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Méthode dogleg

Résolution du problème quadratique On cherche la solution du problème quadratique sous contrainte de région de confiance 1 minn fˆ (d ) f 0  d T g 0  d T H 0 d sous d d r dR 2 Le point de Newton est la solution du problème quadratique sans contrainte o 2 cas possibles •

Si le point de Newton est à l’intérieur de la région de confiance, la contrainte est inactive. o La solution est dN.

•

Sinon, la contrainte est active et peut être formulée comme une contrainte égalité. 1 minn fˆ (d ) f 0  d T g 0  d T H 0 d sous d r dR 2 On restreint la recherche de la solution au chemin dogleg paramétré par s[0,2]. Segment 1 o d(s) = sdC pour s[0,1[ Segment 2 o d(s) = dC + (s1)(dN  dC) pour s[1,2] o Il suffit de trouver l’intersection du chemin dogleg avec la région de confiance en résolvant _d(s)_ = r.

308

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Méthode dogleg

Position des points dogleg Trois situations sont possibles par rapport au rayon de confiance. • _dC_ t r o le point de Cauchy est à l’extérieur de la région de confiance •

_dC_ < r < _dN_

o le point de Cauchy est à l’intérieur de la région de confiance le point de Newton est à l’extérieur de la région de confiance

•

_dN_ d r

o le point de Newton est à l’intérieur de la région de confiance r r

r

x0

x0 dN

dC xC

x0 dN

dC xN

xC

dN

dC xN

xC

xN

309

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Méthode dogleg

Solution du problème dogleg La fonction _d(s)_ est croissante. La solution s* de _d(s)_ = r est : • Sur le segment 1 si _dC_ t r • Sur le segment 2 si _dC_ < r Solution sur le segment 1 d(s) = sdC avec s[0,1[

s *dC

r Ÿ s*

r dC

Ÿ d* r

dC dC

r

g0 g0

car dC // g0

Solution sur le segment 2 d(s) = dC + (s1)(dN  dC) avec s[1,2]

d C  (s * 1)(d N  d C )

r Ÿ d C  (s * 1)(d N  d C ) d C  (s * 1)(d N  d C ) r 2 T

L’équation du second degré en s* admet une racine positive.

­a °°  b  b 2  4ac Ÿ s* 1  avec ®b 2a ° °¯c

d N  dC

2

2d TC d N  d C 2

dC  r 2

310

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Exemple

Méthode dogleg f (x1 , x 2 ) • Fonction

1 2 9 2 x1  x 2 2 2 §9· ’f ( x 0 ) ¨¨ ¸¸ ©9¹

§1 0· ¨¨ ¸¸ ©0 9¹ 1 f ( x 0 )  ’f ( x 0 ) T p  p T ’ 2 f ( x 0 ) p 2

•

§9· ¨¨ ¸¸ ©1¹ Modèle quadratique : fˆ ( x 0  p)

•

fˆ x 0  s’f ( x 0 ) o min 45  18(9s)  5(9s) 2 o s Point de Cauchy : min s s

•

Point de Newton : x N

•

Région de confiance de rayon r :

•

Chemin dogleg :

•

Point initial : x 0



’ 2f (x 0 )



1

x 0  ’ 2 f ( x 0 ) ’f ( x 0 ) xr

45  9p1  9p 2 

1 5

§ 9 · § 1 0 ·§ 9 · ¨¨ ¸¸  ¨¨ ¸¸¨¨ ¸¸ © 1 ¹ © 0 1 / 9 ¹© 9 ¹

§ cos T · ¸¸ x 0  r¨¨ © sin T ¹

§ 9  r cos T · ¨¨ ¸¸ © 1  r sin T ¹

Ÿ xC Ÿ xN

1 2 9 2 p1  p 2 2 2 § 7.2 · ¨¨ ¸¸ ©  0.8 ¹ §0· ¨¨ ¸¸ ©0¹

o paramétrée par T

segment 1 o

x d1 (s)

x 0  s( x C  x 0 )

§ 9  1.8s · ¨¨ ¸¸ 1  1 . 8 s © ¹

segment 2 o

x d 2 (s)

x C  s( x N  x C )

§ 7.2  7.2s · ¨¨ ¸¸ , 0 d s d 1 ©  0,8  0.8s ¹ 311

, 0dsd1

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.2 Modèle quadratique

Techniques d’optimisation 2.4.2 Exemple

Méthode dogleg 1 2 9 2 f (x1 , x 2 ) x1  x 2 2 2

x0

§ 7.2 · §0· ¨¨ ¸¸ , x N ¨¨ ¸¸ ©  0.8 ¹ ©0¹ § 8,293 · ¸¸ sur le segment 1 Ÿ x d | ¨¨ 0 . 293 © ¹

§9· ¨¨ ¸¸ Ÿ x C ©1¹

•

Région de confiance de rayon r=1 :

•

Région de confiance de rayon r=4 :

§ 5,331 · ¸¸ sur le segment 2 Ÿ x d | ¨¨ ©  0.592 ¹

4,00

r=4

3,50 3,00 2,50

r=1

2,00 1,50

x0

1,00 0,50

xN

0,00 -1

-0,50 -1,00 -1,50

0

1

2

3

4

5

6

7

8

xC

9

10

11

  chemin dogleg

312

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.3 Rayon de confiance

Techniques d’optimisation 2.4.3 Rayon de confiance

‰ Rapport de réduction ‰ Réglage du rayon

313

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.3 Rayon de confiance

Techniques d’optimisation 2.4.3 Rapport de réduction

Validité du modèle quadratique Le modèle quadratique est une approximation de la fonction valide dans un voisinage de x0. o Si le rayon de confiance est trop grand, le modèle quadratique n’est plus représentatif. o Il faut vérifier que la solution d* du modèle quadratique donne l’amélioration attendue. Rapport de réduction • On définit le rapport de réduction U entre la variation prévue : fˆ ( x 0 )  fˆ ( x 0  d*) et la variation réalisée : f ( x 0 )  f ( x 0  d*) Rapport de réduction :

U

f ( x 0 )  f ( x 0  d*) fˆ ( x )  fˆ ( x  d*) 0

0

•

La valeur de U permet de vérifier si le modèle quadratique représente correctement la fonction, et d’adapter le rayon de confiance.

• •

U | 1 ou > 1 : amélioration réelle > amélioration prévue U | 0 ou < 0 : amélioration réelle < amélioration prévue

o modèle bon o modèle mauvais

Le rayon est réglé de façon itérative en fonction de la valeur de U.

314

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.3 Rayon de confiance

Techniques d’optimisation 2.4.3 Réglage du rayon

Réglage du rayon On modifie le rayon de confiance en fonction du rapport de réduction U

f ( x 0 )  f ( x 0  d*) fˆ ( x )  fˆ ( x  d*) 0

•

U > U2 avec U2 = 0.9 La fonction f décroît au moins comme prévu : le modèle est bon. o On accepte le nouveau point. o On passe à l’itération suivante en multipliant par 2 le rayon de confiance.

•

U < U1 avec U1 = 0.01 La fonction f augmente au lieu de diminuer comme prévu : le modèle est mauvais. o On rejette le nouveau point. o On reprend l’itération en divisant par 2 le rayon de confiance.

•

U1 < U < U2 La fonction décroît, mais moins que prévu : le modèle est correct. o On accepte le nouveau point. o On passe à l’itération suivante sans changer le rayon de confiance.

0

315

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.4 Algorithme

Techniques d’optimisation 2.4.4 Algorithme

‰ Algorithme de région de confiance ‰ Convergence ‰ Exemple - Région de confiance norme 2 - Région de confiance norme f

316

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.4 Algorithme

Techniques d’optimisation 2.4.4 Algorithme

Algorithme de région de confiance Initialisation : x0  Rayon r0 Gradient : ’f(x0) Approximation du hessien : H0

Itération k : xk  Rayon rk Gradient : ’f(xk) Approximation du hessien : Hk>0

o H0 =I par défaut

Résolution problème quadratique o pas dk Méthode dogleg Rapport de réduction o U Réglage du rayon o rk+1

Arrêt si : ’f(x k 1 )  İ

Itération k+1 : xk+1  Rayon rk+1 Gradient : ’f(xk+1) Approximation du hessien : Hk+1>0

Nouveau point : xk+1 = xk + dk Gradient : ’f(xk+1) Mise à jour du hessien par BFGS ou SR1 Modification du hessien : Hk+1>0 Factorisation de Cholesky modifiée

317

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.4 Algorithme

Techniques d’optimisation 2.4.4 Algorithme

Principaux résultats de convergence • Lorsque le rayon de confiance est petit, la solution dogleg est suivant le gradient. L’itération est équivalente à la méthode de plus forte pente o convergence lente •

Lorsque le rayon de confiance est grand, la solution dogleg est le point de Newton. L’itération est équivalente à la méthode de Newton o convergence rapide

En pratique • On peut combiner l’algorithme de région de confiance avec BFGS ou SR1. Il n’est pas nécessaire que le hessien soit défini positif. Si le hessien n’est pas défini positif, la méthode SR1 est plus efficace. •

La valeur des seuils de réduction U1 et U2 pour régler le rayon n’est pas critique pour la convergence.

•

Le point de Newton xN est systématiquement testé, car il donne la solution s’il est à l’intérieur de la région de confiance. Sinon, on cherche une solution approchée sur le chemin dogleg.

•

D’autres méthodes de résolution approchée du problème quadratique existent.

318

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.4 Algorithme

Techniques d’optimisation 2.4.4 Exemple

Fonction de Rosenbrock



f ( x1 , x 2 ) 100 x 2  x • • •

5

f

 1  x

2 2 1

2

4

1

3

 1.2 · Point initial : §¨ ¨ 1 ¸¸ © ¹

2

Région de confiance avec BFGS ou SR1 Norme 2 : région de confiance circulaire 1,25

BFGS SR1

1

Itération

0 0

10

20

-1

BFGS

SR1

1

1

0,75

0,75

0,5

0,5

0,25

0,25

-0,5

0 0

-0,25

40

1,25

0 -1,5

30

0,5

1

1,5

-1,5

-1

-0,5

0 -0,25

0,5

1

1,5

319

2 Optimisation sans contraintes 2.4 Région de confiance 2.4.4 Algorithme

Techniques d’optimisation 2.4.4 Exemple

Fonction de Rosenbrock



5



f ( x1 , x 2 ) 100 x 2  x12  1  x1 • • •

2

2

f

4 3

 1.2 · Point initial : §¨ ¨ 1 ¸¸ © ¹

BFGS SR1

2 1

Région de confiance avec BFGS ou SR1 Norme f : région de confiance rectangulaire 0 1,25

Itération

0

10

20

-1

BFGS

SR1

1

1

0,75

0,75

0,5

0,5

0,25

0,25

-0,5

0 0

-0,25

40

1,25

0 -1,5

30

0,5

1

1,5

-1,5

-1

-0,5

0 -0,25

0,5

1

1,5

320

2 Optimisation sans contraintes 2.5 Moindres carrés

Techniques d’optimisation Sommaire

1.

Bases théoriques

2.

Optimisation sans contraintes 2.1 Méthodes de descente 2.2 Méthode de Newton 2.3 Recherche linéaire 2.4 Région de confiance 2.5 Moindres carrés 2.5.1 Formulation 2.5.2 Méthode de Gauss-Newton 2.5.3 Moindres carrés linéaires 2.5.4 Filtre de Kalman 2.5.5 Méthode du gradient conjugué 2.6 Méthode de Nelder-Mead

3.

Optimisation avec contraintes 321

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.1 Formulation

Techniques d’optimisation 2.5.1 Formulation

Problème de moindres carrés

minn xR

1 r(x) 2

2

o problème (MC)

• •

Variables xRn : n paramètres d’ajustement d’un modèle Résidus r(x)Rm : m écarts entre modèle et mesures

•

1 r(x) 2

Critère f(x)R :

f (x)

1 r(x) T r(x) 2

2

1 m ri ( x ) 2 ¦ 2i1

o minimisation d’écart quadratique • •

Gradient :

’f ( x )

Hessien :

’ f (x) 2

’r ( x ) r ( x )

m

’ri ( x )ri ( x ) ¦ i 1

¦ ’r (x )’r (x ) m

i

T

i

i 1

­’r ( x )  R num avec ® n u1 ’  r ( x ) R ¯ i

 ’ 2 ri ( x )ri ( x )



m

’r ( x )’r ( x )  ¦ ’ 2 ri ( x )ri ( x ) T

i 1

•

Résolution : en appliquant la méthode de Newton

322

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.2 Méthode de Gauss-Newton

Techniques d’optimisation 2.5.2 Méthode de Gauss-Newton

Méthode de Newton L’itération de Newton au point xk est : ’ 2 f ( x k )d k Avec

’f ( x k )

o déplacement dk

m ­ °°’ f ( x ) ’r ( x )r ( x ) ¦ ’ri ( x )ri ( x ) i 1 ® m 2 T °’ f ( x ) ’r ( x )’r ( x )  ¦ ’ 2 ri ( x )ri ( x ) °¯ i 1

Méthode de Gauss-Newton • L’évaluation du hessien nécessite les dérivées secondes des fonctions ri(x) o calcul très coûteux si m est grand •

2 T Pour accélérer les calculs, on ignore le second terme : ’ f ( x ) | ’r ( x )’r ( x ) Cette approximation du hessien n’utilise que les dérivées premières. La matrice obtenue est de plus toujours semi-définie positive o nécessaire pour la convergence de la méthode de Newton

•

L’itération de Gauss-Newton au point xk est : ’r ( x k )’r ( x k ) T d k

’r ( x k )r ( x k )

323

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.2 Méthode de Gauss-Newton

Techniques d’optimisation 2.5.2 Méthode de Gauss-Newton

Méthode de Gauss-Newton La méthode de Gauss-Newton équivaut à considérer un modèle linéaire des fonctions ri(x) en xk

rˆi ( x )

ri ( x k )  ’ri ( x k ) T ( x  x k ) , i 1,  , m

Le problème devient : minn xR

•

Critère :

fˆ ( x )

Ÿ fˆ ( x )

1 rˆ ( x ) 2

œ rˆ ( x )

r ( x k )  ’r ( x k ) T ( x  x k )

2

2 1 1 rˆ ( x ) rˆ ( x ) T rˆ ( x ) 2 2 T 1 r ( x k )  ’r ( x k ) T ( x  x k ) r ( x k )  ’r ( x k ) T ( x  x k ) 2 1 1 r ( x k ) T r ( x k )  ( x  x k ) T ’r ( x k )r ( x k )  ( x  x k ) T ’r ( x k )’r ( x k ) T ( x  x k ) 2 2 ’fˆ ( x ) ’r ( x )’r ( x ) T ( x  x )  ’r ( x )r ( x )



•

Gradient :

•

Condition d’ordre 1 : ’fˆ ( x )



k

k



k

0 Ÿ ’r ( x k )’r ( x k ) T ( x  x k )

o On retrouve l’itération de Gauss-Newton obtenue en ignorant les dérivées secondes dans le hessien

k

k

’r ( x k )r ( x k )

324

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.3 Moindres carrés linéaires

Techniques d’optimisation 2.5.3 Moindres carrés linéaires

Cas linéaire

minn xR

1 r(x) 2

2

avec r ( x )

Ax  b, A  R mun , b  R m

•

Critère :

•

Gradient :

1 1 2 Ax  b T Ax  b r(x) 2 2 ’f ( x ) ’r ( x )r ( x ) A T Ax  b

•

Hessien :

’ 2f (x)

f (x)

o problème (MC)

1 T T 1 x A Ax  b T Ax  b T b 2 2

ATA

Dans le cas linéaire, la méthode de Gauss-Newton est identique à la méthode de Newton. o La convergence est obtenue en une itération. Equations normales • La solution x* du problème (MC) vérifie

’f ( x*)

0 Ÿ A T Ax  b 0 Ÿ A T Ax

ATb

o système d’équations normales du problème (MC) : minn xR

•

1 Ax  b 2

Si A est de rang plein, x* est l’unique solution du problème (MC).

2

325

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.3 Moindres carrés linéaires

Techniques d’optimisation 2.5.3 Exemple

Moindres carrés linéaires On cherche à estimer l’accélération de la gravité à partir de mesures de hauteur en chute libre. Temps (s) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Hauteur (m) 0,90 5,40 20,81 45,73 78,56 124,10 175,75 241,41 315,08 397,36 488,25 595,35 707,26 829,98 961,20 1103,14 1252,89 1415,55 1586,62 1770,20 1964,29

g

o h

1 2 gt 2

h Hauteur h (m) 2000

1500

1000

500

0 0

5

10

Temps t (s)

15

20

326

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.3 Moindres carrés linéaires

Techniques d’optimisation 2.5.3 Exemple

Moindres carrés linéaires On résout le problème de moindres carrés linéaires : min f (g ) gR

Temps (s) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

H mesure (m) 0,90 5,40 20,81 45,73 78,56 124,10 175,75 241,41 315,08 397,36 488,25 595,35 707,26 829,98 961,20 1103,14 1252,89 1415,55 1586,62 1770,20 1964,29

H modèle Résidu (m) (m) 0,00 0,90 4,90 0,49 19,61 1,19 44,13 1,60 78,46 0,10 122,59 1,51 176,53 -0,78 240,27 1,13 313,82 1,25 397,18 0,17 490,35 -2,10 593,32 2,02 706,10 1,15 828,69 1,28 961,09 0,12 1103,29 -0,14 1255,30 -2,40 1417,11 -1,56 1588,73 -2,11 1770,16 0,04 1961,40 2,89

Modèle : Résidu :

t i2 h mod èle g 2 r h mesure  h mod èle

1 m § t i2 · ¨¨ h i  g ¸¸ ¦ 2 i 1© 2¹ o f (g )

1 m 2 r ( g ) ¦i 2i1

Solution moindres carrés : g* = 9,8070 m/s2 o f(g*) = 21,668 h (m) 2000

1500

1000

500

0 0

50

100

t2/2 (s2)

150

200 327

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.4 Filtre de Kalman

Techniques d’optimisation 2.5.4 Filtre de Kalman

Moindres carrés récursifs • On considère un problème de moindres carrés linéaires composé de 2 blocs 2

min A1 x  b1  A 2 x  b 2 xR n

•

­A 1  R m 1 u n , b 1  R m 1 avec ® m 2 un , b 2  R m2 ¯A 2  R

Les 2 blocs correspondent à 2 séries de mesures donnant chacune des résidus respectifs. ­r1 ( x ) A1x  b1 ® ¯r2 ( x ) A 2 x  b 2

•

2

o m1 mesures o m2 mesures

Les matrices A1 et A2 sont supposées de rang plein o A1T A1 et A2T A2 inversibles

Problème initial • On appelle problème initial le problème restreint au 1er bloc : minn A1 x  b1

2

xR

•

On note x1 la solution du problème initial. T La solution x1 vérifie les équations normales du problème initial : A1 A1 x 1

•

On cherche ensuite à exprimer la solution x2 du problème complet en fonction de x1.

A1T b1

328

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.4 Filtre de Kalman

Techniques d’optimisation 2.5.4 Filtre de Kalman

Problème complet • On réécrit le problème complet en regroupant les 2 blocs. 2 § A 1 · § b1 · 2 2 minn A1 x  b1  A 2 x  b 2 œ minn ¨¨ ¸¸ x  ¨¨ ¸¸ œ minn Ax  b xR xR xR © A2 ¹ © b2 ¹

avec A

§ A1 · ¨¨ ¸¸  R ( m1  m 2 )un , b © A2 ¹

2

§ b1 · ¨¨ ¸¸  R m1  m 2 © b2 ¹

•

La solution x2 vérifie les équations normales du problème complet.

•

§A · §b · A T2 ¨¨ 1 ¸¸ x 2 A1T A T2 ¨¨ 1 ¸¸ Ÿ A1T A1  A T2 A 2 x 2 © A2 ¹ © b2 ¹ La solution x1 vérifie les équations normales du problème initial : A1T A1 x 1

•

On exprime x2 en fonction de x1 et des données du 2ème bloc de mesures

A T Ax 2

A

T 1

Ÿ x2





A T b Ÿ A1T



A1  A T2 A 2 x 2











A1T b1  A T2 b 2 A1T b1

A1T b1  A T2 b 2 A1T A1 x 1  A T2 b 2 A1T A1 x 1  A T2 A 2 x 1  A T2 A 2 x 1  A T2 b 2 A1T A1  A T2 A 2 x 1  A T2 b 2  A 2 x 1



x 1  A1T A1  A T2 A 2



1



A T2 b 2  A 2 x 1

329

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.4 Filtre de Kalman

Techniques d’optimisation 2.5.4 Filtre de Kalman

Filtre de Kalman La solution des moindres carrés est mise à jour à chaque nouvelle mesure disponible. o traitement incrémental en temps réel •

Initialisation :

filtre H0 (=0 par défaut) solution x0 (=0 par défaut)

•

Itération :

filtre Hk solution xk

Hk xk

k

H k 1  A Tk A k œ minn ¦ A i x  b i x k 1  H k1A Tk b k  A k x k 1 xR i 1

2

Mise en œuvre • Les matrices AkTAk doivent être inversibles o en prenant un nombre suffisant de mesures •

•

On peut introduire une pondération U pour privilégier les mesures récentes. o U = 1 pour donner le même poids à toutes les mesures o U < 1 pour privilégier la dernière mesure Itération :

filtre Hk solution xk

Hk xk

UH k 1  A A k x k 1  H k1A Tk b k  A k x k 1 T k

k

œ min ¦ U k i A i x  b i xR n

i 1

330

2

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.4 Filtre de Kalman

Techniques d’optimisation 2.5.4 Filtre de Kalman

Exemple On applique la mise à jour de Kalman à chaque nouvelle mesure. Mesure : h mesure

o bk

hk t 2k t g o Ak , xk gk Modèle : h mod èle Ax 2 2 T Filtre : ­®H 0 0 o ­®H k H k 1  A1k ATk ¯x 0 0 ¯x k x k 1  H k A k b k  A k x k 1

•

b

2

Estimation g (m/s2) 11,00 10,75 10,50

g20 = 9.8070 m/s2

10,25 10,00 9,75 9,50 0

5

10

Temps t (s)

15

20

Temps Matrice H (s) 0 0,0 1 0,3 2 4,3 3 24,5 4 88,5 5 244,8 6 568,8 7 1169,0 8 2193,0 9 3833,3 10 6333,3 11 9993,5 12 15177,5 13 22317,8 14 31921,8 15 44578,0 16 60962,0 17 81842,3 18 108086,3 19 140666,5 20 180666,5

Estimation g (m/s2) 0,0000 10,7937 10,4263 10,2074 9,9269 9,9274 9,8341 9,8440 9,8450 9,8305 9,8046 9,8177 9,8195 9,8204 9,8167 9,8136 9,8068 9,8041 9,8016 9,8029 9,8070

331

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.4 Filtre de Kalman

Techniques d’optimisation 2.5.4 Filtre de Kalman

Comparaison moindres carrés  filtre de Kalman • Les moindres carrés sont adaptés à l’estimation de paramètres de modèle a posteriori (= lorsque toutes les mesures sont disponibles). •

Le filtre de Kalman est adapté à des applications en temps réel (= lorsque les mesures arrivent une à une)

•

Les moindres carrés et le filtre de Kalman sont équivalents pour l’estimation de paramètres d’un modèle linéaire. Le filtre de Kalman peut être appliqué à différents problèmes d’estimation.

Applications du filtre de Kalman • Estimation de l’état d’un système dynamique linéaire, discret ou continu. o état fonction du temps, mesures en temps réel •

Estimation de l’état d’un système dynamique non linéaire o par linéarisation autour d’une trajectoire de référence estimée au préalable

•

Méthode de filtrage largement utilisée dans les systèmes temps réels o nombreuses variantes

332

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.5 Gradient conjugué

Techniques d’optimisation 2.5.5 Gradient conjugué

Problème quadratique On considère un problème de moindres carrés linéaires. 1 2 minn r ( x ) avec r ( x ) Ax  b, A  R mun , b  R m xR 2 1 1 2 Ax  b T Ax  b 1 x T A T Ax  b T Ax  1 b T b r(x) Ÿ 2 2 2 2 Le problème de moindres carrés revient à minimiser une forme quadratique définie positive. f (x)

1 T x Qx  c T x 2

avec QRnun symétrique définie positive

Méthode de directions conjuguées • 2 directions di et dj sont conjuguées par rapport à Q si diTQdj = 0 •

On obtient le minimum de la forme quadratique définie positive en n itérations à pas optimal suivant des directions conjuguées (di)i=1,…,n.

•

La méthode du gradient conjugué consiste à construire une suite de directions conjuguées et à minimiser suivant ces directions successives pour obtenir le minimum de f. o extension à une fonction f quelconque (méthode de Fletcher-Reeves)

333

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.5 Gradient conjugué

Techniques d’optimisation 2.5.5 Gradient conjugué

Méthode du gradient conjugué • On part d’un point initial x0 quelconque. La direction initiale est le gradient : d1 = ’f(x0) • A chaque itération, le nouveau point xk est obtenu par minimisation suivant dk. min f ( x k 1  sd k ) o x k s

x k 1  s k d k

•

La nouvelle direction dk+1 est définie à partir de la précédente dk et du gradient en xk. d k 1 ’f ( x k )  E k d k o plusieurs méthodes possibles

•

La méthode converge en n itérations pour une fonction quadratique définie positive. Pour une fonction f quelconque, la convergence est généralement rapide car f est proche d’une fonction quadratique définie positive au voisinage de l’optimum.

Initialisation x0

Point courant xk-1

Direction conjuguée dk

Solution x*=xn

Nouveau point xk

Minimisation suivant dk

334

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.5 Gradient conjugué

Techniques d’optimisation 2.5.5 Gradient conjugué

Méthode du gradient conjugué • La direction de descente à l’itération k est cherchée sous la forme d k 1 ’f ( x k )  E k d k avec xk obtenu par minimisation suivant dk : min f ( x k 1  sd k ) o x k x k 1  s k d k s

•

La nouvelle direction dk+1 doit être conjuguée à toutes les directions précédentes d1,…, dk.

d Tk 1Qd i

0 , i 1,  , k

Il existe plusieurs méthodes de construction des directions conjuguées successives (di)i=1,…,n. •

Directions de Fletcher-Reeves d k 1

•

’f ( x k )  E k d k avec E k

2

’f ( x k ) ’f ( x k 1 )

2

Directions de Polak-Ribière d k 1

’f ( x k )  E k d k avec E k

’f ( x k )  ’f ( x k 1 ) T ’f ( x k ) ’f ( x k 1 )

2

o formules équivalentes dans le cas d’une fonction f quadratique

335

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.5 Gradient conjugué

Techniques d’optimisation 2.5.5 Gradient conjugué

Directions de Fletcher-Reeves d k 1

’f ( x k )  E k d k avec E k

’f ( x k ) ’f ( x k 1 )

2 2

Preuve : On note gk = ’f(xk) = Qxk + c •

o directions conjuguées pour 1 T f (x) x Qx  c T x 2

Propriété préliminaire T Si les n directions d1,…,dn sont conjuguées, alors d i g k et g iT g k

0 , i 1, , k pour k=1 à n. 0 , i 1, , k  1

A l’itération i, xi est obtenu par minimisation suivant di d min f ( xi 1  sd i ) Ÿ f ( xi 1  sd i ) d iT ’f ( xi 1  sd i ) 0 Ÿ d iT g i 0 , i 1, , n s ds k k k · § xk xi  ¦ s j d j Ÿ g k Qxk  c Q¨¨ xi  ¦ s j d j ¸¸  c ’f ( xi )  ¦ s j Qd j j i 1 j i 1 j i 1 ¹ © T k ­d g 0 T T Ÿ d i g k d i g i  ¦ s j d iT Qd j 0 car ® iT i j i 1 ¯d i Qd j 0 si i z j Ÿ g iT g k

g iT g k  E i d iT g k car d iT g k d iT1 g k 0 car i  k

0 ,i

1, , k

336

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.5 Gradient conjugué

Techniques d’optimisation 2.5.5 Gradient conjugué

Directions de Fletcher-Reeves Preuve : on montre par récurrenceque dk+1 est conjuguée à d1,…,dk. • Pour d1 et d2 : ­°d 1  g 0 x1  x0 T T d 2 Qd 1 g 1  E 1 g 0 Q car ®d 2 g 1  E 1 d 1 s1 °¯ x1 x0  s1 d 1 T g  g0 Ÿ d 2T Qd 1 g 1  E 1 g 0 1 car g Qx  c s1 Ÿ d 2T Qd 1 Ÿ d 2T Qd 1

•



 g1

2

 E1 g0

0 car E 1

car g T

’f ( x1 )

2

’f ( x0 )

2

T 1

g 1T d 1

g0 g1 g0

0

(propriété préliminaire)

2

(par définition de E)

2

On suppose d1,…,dk conjuguées : d iT Qd j 0 , i z j , i , j d k Il faut montrer que d iT Qd k 1 0 , i 1, , k d iT Qd k 1

 d iT Qg k  E k d k  d iT Qg k car d iT Qd k

0

(par hypothèse de récurrence)

T

Ÿ d iT Qd k 1 Ÿ d iT Qd k 1

§ xi  xi  1 · ¸ g k car xi Qd i g k ¨¨ Q ¸ si T © ¹ § g i  g i 1 · ¨ ¸ g k car g Qx  c ¨ ¸ si © ¹ T

xi  1  s i d i

337

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.5 Gradient conjugué

Techniques d’optimisation 2.5.5 Gradient conjugué

Directions de Fletcher-Reeves Preuve • •





1 T g i g k  g iT1 g k 0 pour i 1, , k  1 si car g iT g k 0 , i 1, , k  1 T Il faut encore montrer pour i=k : d k Qd k 1 0

On obtient : d iT Qd k 1

T k

d Qd k 1

0 Ÿ d Q g k  E k d k 0 Ÿ E k T k

T

d kT Qg k

d kT Qd k Ÿ d kT Qd k

(propriété préliminaire)

d kT Qg k d kT Qd k

§ xk  x k 1 · 1 1 2 T ¨Q ¸ gk   g g g g k k 1 k  k ¨ ¸ sk sk sk © ¹ § x  x k 1 · 1 T 1 T T ¸  d kT ¨¨ Q k d g g   d g car d g k 0 (propriété préliminaire) k k k  1 k k  1 k ¸ s s s k k k © ¹ 1 1 1 2 T  d kT g k 1   g k 1  E k 1 d k 1 g k 1 g k 1 car d kT1 g k 1 sk sk sk

On obtient bien : E k

gk g k 1

2 2

o valeur de Ek telle que d kT Qd k 1

0

338

2 Optimisation sans contraintes 2.5 Moindres carrés 2.5.5 Gradient conjugué

Techniques d’optimisation 2.5.5 Exemple

Gradient conjugué • Fonction quadratique f ( x 1 , x 2 ) x0

•

Point initial

•

1 Itération 1 : d

min f ( x 0  sd1 ) s

•

Itération 2 : d 2 d2 min f ( x1  sd 2 ) s

•

§ 10 · ¨¨ ¸¸ ©  5¹ ’f ( x 0 )

1 2 x 1  x 1 x 2  x 22 o ’f ( x 1 , x 2 ) 2

§  5· ¨¨ ¸¸ o x 1 © 0 ¹

25 2  s 2  252  s  25 Ÿ s1 2

’f ( x 1 )  E1d1 avec E1

§10  5s · ¨¨ ¸¸ © 5 ¹

x 0  sd1 1

’f ( x 1 )

2

’f ( x )

2

0

o x

25 25

1

§ x1  x 2 · ¨¨ ¸¸ © x1  2x 2 ¹ §2  s· ¸¸ 5¨¨ © 1 ¹ § 5 · ¨¨ ¸¸ , ’f ( x 1 ) ©  5¹

1

§  5· § 5  5s · §1· ¨¨ ¸¸ o x 2 x1  sd 2 ¨¨ ¸¸ 5(1  s)¨¨ ¸¸ © 5 ¹ ©  5  5s ¹ ©  1¹ 25 1  s 2  251  s 2  251  s 2 Ÿ s 2 1 o x 2 2

§0· Solution : x* ¨¨ ¸¸ , ’f ( x*) ©0¹

§ 0 · ¨¨ ¸¸ ©  5¹

§ 0· ¨¨ ¸¸ , ’f ( x 2 ) © 0¹

§0· ¨¨ ¸¸ ©0¹

§0· ¨¨ ¸¸ ©0¹

339

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead

Techniques d’optimisation Sommaire

1.

Bases théoriques

2.

Optimisation sans contraintes 2.1 Méthodes de descente 2.2 Méthode de Newton 2.3 Recherche linéaire 2.4 Région de confiance 2.5 Moindres carrés 2.6 Méthode de Nelder-Mead 2.6.1 Principes 2.6.2 Algorithme 2.6.3 Exemples

3.

Optimisation avec contraintes

340

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead 2.6.1 Principes

Techniques d’optimisation 2.6.1 Méthode de Nelder-Mead

Problème sans contrainte minn f(x) xR

Principes La méthode de Nelder-Mead est une méthode d’ordre 0 (sans dérivées) o n’utilise que des évaluations de la fonction (aucune évaluation du gradient)

^x1 , x 2 ,, x n , x n 1`

•

On définit un ensemble P de n+1 points de Rn : P P est un polytope ou « simplexe » de Rn.

•

Les points de P sont rangés du meilleur au plus mauvais : f ( x 1 ) d f ( x 2 ) d  d f ( x n ) d f ( x n 1 )

•

A chaque itération, on cherche à remplacer le plus mauvais point par un point meilleur. P ^x 1 , x 2 , , x n , x n 1 ` o P' ^x 1 , x 2 , , x n , x new ` o P' ^x 1 ' , x 2 ' , , x n ' , x n 1 '` après reclassement

•

On obtient une suite de polytopes (Pk)kN : P k

•

Si la méthode converge, les polytopes Pk sont de taille décroissante et les points du polytope convergent vers un minimum local de f.

^x

k 1

, x k2 ,  , x kn , x kn 1

` 341

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead 2.6.1 Principes

Techniques d’optimisation 2.6.1 Méthode de Nelder-Mead

Polytope P ^x 1 , x 2 ,  , x n , x n 1 `

x1

f ( x 1 ) d f ( x 2 ) d  d f ( x n ) d f ( x n 1 )

x3

x*

Nouveau point xc est le barycentre des n meilleurs points. 1 n xc ¦ xi ni1

x2

On cherche à ramener le plus mauvais point xn+1 vers le barycentre xc. On teste des points x sur la demi-droite [xn+1,xc) paramétrée par t > 0.

x(t)

x c  t ( x c  x n 1 ) x1

Points testés successivement : • Réflexion : x(t=+1) = xr • Expansion : x(t=+2) = xe • Contraction externe : x(t=+0.5) = xce • Contraction externe : x(t=0.5) = xci

x* xr xe x(t)

xc xce

x3 xci

x2

342

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead 2.6.1 Principes

Techniques d’optimisation 2.6.1 Méthode de Nelder-Mead

Nouveau point Le polytope initial est P

^x1 , x 2 ,, x n , x n 1`

avec

f ( x 1 ) d f ( x 2 ) d  d f ( x n ) d f ( x n 1 )

La demi-droite [xn+1,xc) est supposée être une direction de descente. On teste d’abord xr (symétrique de xn+1 / xc). •

• •

•

Résultat très bon : f ( x r )  f ( x 1 ) o on essaie xe on remplace xn+1 par xe ou xr.

x1 x*

f (x1 ) d f (x r )  f (x n ) Résultat bon : o on remplace xn+1 par xr. Résultat moyen : f ( x n ) d f ( x r )  f ( x n 1 ) o on essaie xce on remplace xn+1 par xce ou xr.

xr xe x(t)

Résultat mauvais : f ( x n 1 ) d f ( x r ) o on essaie xci on remplace xn+1 par xci , ou on contracte tout le polytope P vers x1

xc xce

x3 xci

x2

343

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead 2.6.2 Algorithme

Techniques d’optimisation 2.6.2 Algorithme

Itération k

Pk

^x

k 1

, x k2 ,  , x kn , x kn 1

`

avec f ( x 1k ) d f ( x k2 ) d  d f ( x kn ) d f ( x kn 1 ) 1 n k x i o d x c  x kn 1 ¦ ni1

1.

Barycentre :

2. 3.

o Réflexion : xr = x c + d Si f(xr) < f(x1) o Expansion : xe = xc + 2d o x’ = xe Si f(xe) < f(xr) Sinon o x’ = xr o x’ = xr Si f(x1) < f(xr) < f(xn) Si f(xn) < f(xr) < f(xn+1) Contraction externe : xce = xc + d/2 o o x’ = xce Si f(xce) < f(xr) Sinon o x’ = xr Si f(xn+1) < f(xr) Contraction interne : xci = xc  d/2 o o x’ = xci Si f(xci) < f(xn+1) Sinon réduction de P vers x1 o x ik 1

4. 5.

6.

7.

xc

Nouveau point x’

P k 1

^x

k 1 1

o polytope P

, x k2 1 ,  , x kn 1 , x kn 11

`

k 1

avec

f(xr)

d

f(xe) 2d

f(xce) d/2

f(xci)





d/2 1 k x1  x i 2 x 1k , x k2 , , x kn , x ' à reclasser

^

`

f ( x 1k 1 ) d f ( x k2 1 ) d  d f ( x kn 1 ) d f ( x kn 11 )

344

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead 2.6.2 Algorithme

Techniques d’optimisation 2.6.2 Algorithme

Initialisation 0 x 10 , x 02 , , x 0n , x 0n 1 avec Polytope initial P o points suffisamment distants, non alignés

^

Itération k

Pk

^x

k 1

, x k2 ,  , x kn , x kn 1

`

`

avec

f ( x 10 ) d f ( x 02 ) d  d f ( x 0n ) d f ( x 0n 1 )

f ( x 1k ) d f ( x k2 ) d  d f ( x kn ) d f ( x kn 1 )

•

Nouveau point x’ o reclassement des points x1, x2, … , xn, x’ par valeur de f croissante

•

Nouveau polytope :

P k 1

^x

k 1 1

, x k2 1 ,  , x kn 1 , x kn 11

`

avec

f ( x 1k 1 ) d f ( x k2 1 ) d  d f ( x kn 1 ) d f ( x kn 11 )

Arrêt • Taille du polytope • Valeur de la fonction (non décroissante, identique sur tout le polytope) • Dégénérescence du polytope (alignement des points).

345

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead 2.6.3 Exemples

Techniques d’optimisation 2.6.3 Exemples

Exemple 1 : fonction quadratique 1 2 9 2 f (x1 , x 2 ) x1  x 2 2 2 2,5

2,0

1,5

1,0

0,5

0,0 -0,5

0,0

-0,5

0,5

1,0

1,5

2,0

2,5

346

2 Optimisation sans contraintes 2.6 Méthode de Nelder-Mead 2.6.3 Exemples

Techniques d’optimisation 2.6.3 Exemples

Exemple 2 : fonction de Rosenbrock





f ( x1 , x 2 ) 100 x 2  x12  1  x1 2

2

1,25

1,00

0,75

0,50

0,25

0,00 -1,50

-1,00

-0,50

0,00

-0,25

0,50

1,00

1,50

347