Upload
others
View
10
Download
0
Embed Size (px)
Citation preview
Techniques d’optimisation
239
Max CERF2018
2.2.1 Résolution d’équations
� Principes
� Méthode de Newton
� Méthode de quasi-Newton
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
240
Max CERF2018
2.2.1 Résolution d’équationsSystème d’équations non linéaires
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 linéaire ĝ « proche » de g• Résoudre le système linéaire ĝ(x)=0 o nouveau point x1• Itérer jusqu’à vérifier g(x)=0 o solution x*
0 g(x)
Initialisation x0
Point initialxk
Nouveau pointxk+1
Fonction modèle(x)gk
Résolution0(x)gk
Solutionx*
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
241
Max CERF2018
2.2.1 Méthode de Newton
Fonction modèle• Développement de Taylor à l’ordre 1 de g en xk
• Modèle linéaire de g en xk :
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
• Système linéaire :
• Itération : si Gk inversible
• Condition d’arrêt :
)x(xG)g(x(x)g kkkk ��
0)x(xG)g(x0(x)g kkkk ���
ε)g(xk �
� �kkT
kk xxo)x(x)g(x)g(xg(x) �����
nnk RGavec u�
)g(xGxx k1
kk1k�
� �
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
242
Max CERF2018
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 )
• Intersection axe x :
• Nouveau point : x1, y1 = g(x1))(xg'
yxx0y
0
001 � �
x0x1x2
x*
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
243
Max CERF2018
2.2.1 Méthode de Newton
Modèle linéaire de g en xk
Erreur de linéarisationM = constante de Lipschitz sur le gradient | majorant de la courbure
o erreur quadratique
Vitesse de convergenceHypothèses sur la solution x* :
Suite (xk) :
• (xk) converge vers x* si x0 est « assez proche » de x* :
• La convergence est quadratique o
)xx(G)g(x(x)g kkkk �� Tkk )g(xGavec �
2kk xxM
21(x)gg(x) �d�
)g(xGxx k1
kk1k�
� �
η)g(x 1* d� �
*kk
*0 xxlimrxx/0r ���!�
fo
2*k
*1k xxMηxx �d��
inversible)g(x*�
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
244
Max CERF2018
2.2.1 Exemples
Exemple 1• Fonction :• Dérivée :• Solution : x = 1 o g’(1) = 2
1xg(x) 2 � Iteration x(k) g(x)=x**2-1 g'(x)=2x Erreur
0 4,00000000 1,5E+01 8,0000 3,0E+001 2,12500000 3,5E+00 4,2500 1,1E+002 1,29779412 6,8E-01 2,5956 3,0E-013 1,03416618 6,9E-02 2,0683 3,4E-024 1,00056438 1,1E-03 2,0011 5,6E-045 1,00000016 3,2E-07 2,0000 1,6E-076 1,00000000 2,5E-14 2,0000 1,3E-14
Convergence quadratiqueg’(x*) inversible
2x(x)g'
x
g(x)
1
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
245
Max CERF2018
2.2.1 Exemples
Exemple 2• Fonction :• Dérivée :• Solution : x = 1 o g’(1) = 0
2)1x(g(x) � Iteration x(k) g(x)=(x-1)**2 g'(x)=2(x-1) Erreur0 4,00000000 9,0E+00 6,0000 3,0E+001 2,50000000 2,3E+00 3,0000 1,5E+002 1,75000000 5,6E-01 1,5000 7,5E-013 1,37500000 1,4E-01 0,7500 3,8E-014 1,18750000 3,5E-02 0,3750 1,9E-015 1,09375000 8,8E-03 0,1875 9,4E-026 1,04687500 2,2E-03 0,0938 4,7E-027 1,02343750 5,5E-04 0,0469 2,3E-028 1,01171875 1,4E-04 0,0234 1,2E-029 1,00585938 3,4E-05 0,0117 5,9E-0310 1,00292969 8,6E-06 0,0059 2,9E-0315 1,00009155 8,4E-09 0,0002 9,2E-0520 1,00000286 8,2E-12 0,0000 2,9E-06
1)2(x(x)g' �
Convergence lenteg’(x*) non inversible
x1
g(x)
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
246
Max CERF2018
2.2.1 Exemples
Exemple 3• Fonction :
• Dérivée :
• Solution : x = 0 o g’’(1) = 0
)xtan(Arcg(x)
2x11(x)g'�
Iteration x(k) g(x)=Arctan(x) g'(x)=1/(1+x**2) Erreur0 1,500 0,983 0,308 1,5E+001 -1,694 -1,038 0,258 -1,7E+002 2,321 1,164 0,157 2,3E+003 -5,114 -1,378 0,037 -5,1E+004 32,296 1,540 0,001 3,2E+015 -1575,317 -1,570 0,000 -1,6E+036 3894976,008 1,571 0,000 3,9E+06
x0
g(x)
x0x1 x2
Iteration x(k) g(x)=Arctan(x) g'(x)=1/(1+x**2) Erreur0 1,300 0,915 0,372 1,3E+001 -1,162 -0,860 0,426 -1,2E+002 0,859 0,710 0,575 8,6E-013 -0,374 -0,358 0,877 -3,7E-014 0,034 0,034 0,999 3,4E-025 0,000 0,000 1,000 -2,6E-056 0,000 0,000 1,000 1,2E-14
Convergence
Divergence
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
247
Max CERF2018
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 o Gk = approximation du gradient �g(xk)
construite à partir des itérations précédentessans calcul explicite du gradient
• Techniques de globalisation o Contrôle du point xk+1 (meilleur que xk ?)
Si le point xk+1 n’est pas satisfaisant o Méthodes de recherche linéaireou région de confiance
pour minimiser
)g(x)g(x k1k ��
2g(x)
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
248
Max CERF2018
2.2.1 Méthode de quasi-Newton
Méthode de BroydenOn 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 :
• Modèle linéaire de g en xk:
• Différence entre les modèles en xk-1 et xk
)xx(G)g(x(x)g 1-k1-k1-k1-k ��
)xx(G)g(x(x)g kkkk ��
)xx)(GG((x)g)xx(G)xx(G(x)g)xx(G)g(x
)xx(G)xx(G)g(x)xx(G)g(x(x)g
1-k1-kk1-k
1-kk1-k1-k1-k
1-kk1-k
kk1-kkk1-k
kkkk
��� ���� �� ���� ��
k
1-kkk1-kkG de définitionpar
)x(xG)g(x)g(xcar ��
)x)(xG(G(x)g(x)g 1-k1-kk1-kk �� ��
1-k
1-k1-k1-k1-kg de définitionpar
)xx(G)g(x(x)gcar ��
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
249
Max CERF2018
1-kk1-k1-kkk1-kk dGy)xx(G)g(x)g(x �� �¯®
� �
)g(x)g(xyxxd
1-kk1-k
1-kk1-k
)xx(G)g(x(x)g kkkk �� Tkk )g(xGavec �|
2.2.1 Méthode de quasi-Newton
ObjectifConserver un modèle linéaire de g en xk
sans calculer explicitement Gk
Equation de la sécanteOn choisit une matrice Gk �Rnun vérifiant :
avec
o équation de la sécante entre xk-1 et xk
Choix de GIl 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 xko infinité d’ hyperplans possibles
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
250
Max CERF2018
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) o Sécante en x1 :
• Intersection axe x :
• Nouveau point : x2, y2 = g(x2)
001
0102 y
yyxx
xx0y��
� �
x0x1x2
x*
)xx(xxyy
yy 001
010 �
��
�
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
251
Max CERF2018
2.2.1 Méthode de quasi-Newton
Mise à jour de BroydenL’écart entre les modèles et est minimal en choisissant Gk solution de
avec
Formule de Broyden : o solution optimale
Convergence• La matrice G ne converge pas forcément vers �g 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éoriqueso Méthode efficace en pratique, comportement à vérifier et adapter au cas par cas
(x)gk(x)g 1-k
� �1k
T1k
T1k1k1-k1k
1-kk ddddGyGG
��
��� ��
¯®
� �
)g(x)g(xyxxd
1-kk1-k
1-kk1-k1k1k1-k
RGdGysousGGmin
nn ���
�u
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
252
Max CERF2018
Iteration x(k) g(x)=x**2-1 dg/dx Erreur5,00000000 2,4E+01 4,0E+00
0 4,00000000 1,5E+01 9,0000 3,0E+001 2,33333333 4,4E+00 6,3333 1,3E+002 1,63157895 1,7E+00 3,9649 6,3E-013 1,21238938 4,7E-01 2,8440 2,1E-014 1,04716672 9,7E-02 2,2596 4,7E-025 1,00443349 8,9E-03 2,0516 4,4E-036 1,00010193 2,0E-04 2,0045 1,0E-047 1,00000023 4,5E-07 2,0001 2,3E-078 1,00000000 2,3E-11 2,0000 1,1E-11
2.2.1 Exemple
Comparaison Newton � Quasi-Newton• Fonction :• Dérivée :• Solution : x = 1
1xg(x) 2 �
Iteration x(k) g(x)=x**2-1 g'(x)=2x Erreur0 4,00000000 1,5E+01 8,0000 3,0E+001 2,12500000 3,5E+00 4,2500 1,1E+002 1,29779412 6,8E-01 2,5956 3,0E-013 1,03416618 6,9E-02 2,0683 3,4E-024 1,00056438 1,1E-03 2,0011 5,6E-045 1,00000016 3,2E-07 2,0000 1,6E-076 1,00000000 2,5E-14 2,0000 1,3E-14
2x(x)g'
Quasi - Newton Newton
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.1 Résolution d’équations
Techniques d’optimisation
253
Max CERF2018
2.2.2 Minimisation
� Principes
� Méthode de Newton
� Méthode de quasi-Newton
� Méthode BFGS
� Méthode DFP
� Méthode SR1
� Comparaison
� Extensions BFGS
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
254
Max CERF2018
2.2.2 Problème de minimisation
Problème sans contrainteo gradient : g(x) = � f(x)
hessien : H(x) = �2f(x)
Condition nécessaire de minimum local
x* minimum local
Recherche des points stationnairesApplication 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 : G = H o calcul explicite du hessien à chaque itération• Méthode de quasi-Newton : G = approximation de H
construite à partir des itérations précédentessans calcul explicite du hessien
f(x)minnRx�
¯®
� � �
kk2T
kk
kk
H)f(x)g(xG)f(x)g(xavec)xx(G)g(x(x)g kkkk ��
¯®
t � 0H(x*)
0g(x*)(hessien semi-défini positif)
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
255
Max CERF2018
2.2.2 Méthode de Newton
Modèle linéaire de g=�f en xk
• Itération : o équations de Newton• Condition d’arrêt :
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*)=0o point stationnaire x* = minimum local, maximum local ou point selleo 2ème condition nécessaire de minimum à vérifier : �2f(x*)t0
Adaptations• Méthodes de quasi-Newton o Gk = approximation du hessien �2f(xk)• Techniques de globalisation o Contrôle de la décroissance de f
)xx(G)g(x(x)g kkkk ��
)f(x)f(xxx k1
k2
k1k ��� ��
ε)f(xk d�
¯®
� � �
kk2T
kk
kk
H)f(x)g(xG)f(x)g(xavec
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
256
Max CERF2018
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
• Modèle quadratique en xk
• Lien entre le modèle de f et le modèle de g =�f
Minimisation du modèle de f en xk
• Conditions suffisantes de minimum local :
• Si le hessien de f en xk est défini positif : �2f(xk) > 0Minimisation 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
� �2kkk
2Tkk
Tkk xxo)x)(xf(x)x(x
21)x(x)f(x)f(xf(x) ���������
)x(xH)x(x21)x(xg)(xf(x)f kk
Tkk
Tkkkk �����
(x)g)x(xHg(x)f kkkkk �� �
¯®
! � ��
� 0H(x*)f0(x*)g(x*)f(x)fmin
kk2
kkk
Rx n
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
257
Max CERF2018
2.2.2 Exemple
Méthode de Newton• Fonction :
• Dérivée : o 3 zéroso 1 minimum local, 2 maxima locaux
x60x47x12x)x(f 234 ����
-20,0
-15,0
-10,0
-5,0
0,0
5,0
10,0
15,0
20,0
0,0 1,0 2,0 3,0 4,0 5,0 6,0
60x94x36x4)x('f 23 ����
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
258
Max CERF2018
2.2.2 Exemple
Méthode de Newton• Modèle quadratique en x0 = 3 :
• Itération de Newton en x0 = 3 : o Meilleur que x0f(x1) = �1.32 < 0 = f(x0)
81x48x7)x(f 20 ��
)x(fmin 0x
-1,50
-1,25
-1,00
-0,75
-0,50
-0,25
0,00
0,25
0,50
0,75
1,00
1,25
1,50
2,50 2,75 3,00 3,25 3,50 3,75 4,00 4,25 4,50
x1x0
724x1 o
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
259
Max CERF2018
2.2.2 Exemple
Méthode de Newton• Modèle quadratique en x0 = 4 :
• Itération de Newton en x0 = 4 : o Moins bon que x0f(x1) = 12 > 0 = f(x0)
x4x)x(f 20 �
-5,00
-4,00
-3,00
-2,00
-1,00
0,00
1,00
2,00
3,00
4,00
5,00
1,00 1,50 2,00 2,50 3,00 3,50 4,00 4,50 5,00
x1 x0
2x1 o)x(fmin 0x
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
260
Max CERF2018
2.2.2 Exemple
Méthode de Newton• Modèle quadratique en x0 = 5 :
• Itération de Newton en x0 = 5 : o Moins bon que x0 (maximise f)f(x1) = 1.513 > 0 = f(x0)
-3,00
-2,50
-2,00
-1,50
-1,00
-0,50
0,00
0,50
1,00
1,50
2,00
4,00 4,25 4,50 4,75 5,00 5,25 5,50
x1 x0
1780x1 o)x(fmin 0x
375x160x17)x(f 20 ���
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
261
Max CERF2018
2.2.2 Méthode de quasi-Newton
ObjectifConserver un modèle quadratique de f en xk
sans calculer explicitement Hk
Mise à jour de BroydenOn peut appliquer la méthode de Broyden à la résolution de g(x)=�f(x)=0.
avec
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 o Formules BFGS, DFP ou SR1
¯®
� �
)g(x)g(xyxxd
1-kk1-k
1-kk1-k
)f(xHavec k2
k �|)x(xH)x(x21)x(xg)(xf(x)f kk
Tkk
Tkkkk �����
� �1k
T1k
T1k1k1-k1k
1-kk ddddHyHH
��
��� ��
)f(xH k2
k �|
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
262
Max CERF2018
2.2.2 Méthode BFGS
Equation sécantePour la résolution d’équations, on cherche la matrice Hk
• vérifiant l’équation sécante• 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• définie positive
Méthode de résolutionLa matrice Hk-1 issue de l’itération précédente est symétrique, définie positive.
• On part de la factorisation de Cholesky de Hk-1 :• On cherche la matrice Hk à partir de Hk-1 sous la forme :
Il faut exprimer la matrice Ak en fonction de Lk-1.o On décompose l’équation sécante en 2 équations.
1k1kk ydH �� o formule de Broyden
o formule BFGS
T1-k1-k1-k LLH
Tkkk AAH
¯®
� �
�
�����
1kk
1kTk
1k1kTkk1k1kk yxA
dAxydAAydH
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
263
Max CERF2018
2.2.2 Méthode BFGS
Méthode de résolution de l’équation sécante
1. Pour x donné, on cherche Ak la plus « proche » possible de Lk-1 vérifiant :2. On détermine ensuite x en reportant l’expression de Ak dans :3. On obtient que l’on exprime en fonction de Hk-1.
RésolutionNotations sans indices : L = Lk-1, A = Ak
y = yk-1 , d = dk-1
1. En appliquant la formule de Broyden à L on obtient Aen fonction de x :
2. En reportant :
Il faut résoudre pour trouver x.
¯®
� �
�
�����
1kk
1kTk
1k1kTkk1k1kk yxA
dAxydAAydH
1kk yxA �
1kTk dAx �
Tkkk AAH
xxx)Lxy(LA T
T��
xxx
dLx)y(dLdxxLx)y(xdLdAx T
TT
T
TTT �
� �
�
xxx
dLx)y(dLx T
TT �
�
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
264
Max CERF2018
2.2.2 Méthode BFGS
Résolution de l’équation sécante
On cherche x�Rn vérifiant :
• Pour qu’une solution existe, le vecteur LTd doit être colinéaire à x.
• En reportant dans l’équation :
• Pour qu’une solution existe, on doit avoir yTd > 0On obtient Hk :
Formule BFGS
• Mise à jour de Hk :
• Mise à jour symétrique, de rang 2• Mise à jour définie positive si• Initialisation : H0 = I ou H0 = WI avec W > 0
0dy 1kT
1-k !�
xxx
dLx)y(dLx T
TT �
�
HdddydLdL
HdddLx)y(dLdL T
TT2T
T2
TTT D�D
D�
� D
¸¹
ᬩ
§�D� o LdHd
HdddyLdy
dy1LA T
T
TT
T
HddxxdLx T2TT D �D
Tkkk AAH
1k1-kT
1k
1-kT
1k1k1-k
1kT
1-k
T1-k1k
1-kk dHdHddH
dyyyHH
��
��
�
� �� ¯®
� �
)g(x)g(xyxxdavec
1-kk1-k
1-kk1-k
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
265
Max CERF2018
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
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.
• Méthode élaborée par Broyden, Fletcher, Goldfarb, Shanno à la fin des années 1960o 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 à l’optimum, ou non défini positif loin de l’optimumo cas d’optimisation avec contraintes (hessien réduit du lagrangien positif z hessien complet)
)x(fHd)x(fdH k-1kkkkk �� ���
1kT
1-k
T1-k1k
1kT
1-k
T1-k1k1-
1-k1k
T1-k
T1-k1k1-
k yddd
yddyIH
ydydIH
�
�
�
�
�
� �¸¹
ᬩ
§�¸
¹
ᬩ
§� 0dysi 1k
T1-k !� ¯
®
� �
)g(x)g(xyxxdavec
1-kk1-k
1-kk1-k
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
266
Max CERF2018
2.2.2 Méthode BFGS
Algorithme BFGS• Direction de descente à l’itération k :
• Minimisation dans la direction uk-1 :
• Mise à jour de l’inverse du hessien
Propriété 1La mise à jour BFGS donne une matrice définie positive siCette condition est réalisée si xk est obtenu par minimisation exacte dans la direction
Propriété 2Pour une fonction f quadratique :
l’algorithme BFGS donne des directions successives vérifiant :
o directions conjuguées par rapport à Q�1
o convergence en n itérations avec à l’itération n :
0yd 1kT
1-k !�
)x(gH 1k-1
1-k ��
� �¯®
�o�
� ��
����
1k1ks
1k-1
1-k1k1k1kk suxfmins
)x(gHuavecsuxx
)x(gHu 1k-1
1-k1k �� �
xcQxx21)x(f TT �
¯®
dd dzd
��
�
ki0,uuQHkji0,0uQu
ii11
k
j1
i
QHn
1kT
1-k
T1-k1k
1kT
1-k
T1-k1k1-
1-k1k
T1-k
T1-k1k1-
k yddd
yddyIH
ydydIH
�
�
�
�
�
� �¸¹
ᬩ
§�¸
¹
ᬩ
§� 0dysi 1k
T1-k !� ¯
®
� �
)g(x)g(xyxxdavec
1-kk1-k
1-kk1-k
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
267
Max CERF2018
2.2.2 Méthode DFP
Méthode de résolution• Résolution de l’équation sécante sous la forme « inverse » :
• 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 :
• Mise à jour du hessien :
Comparaison DFP � BFGS• Formules identiques en permutant dk�1 et yk�1 pour mettre à jour le hessien ou l’inverse• Mise à jour symétrique, de rang 2• Mise à jour définie positive si o condition similaire à BFGS• Méthode DFP en général moins efficace que BFGS
1k1k-1k1k1kk dyHydH ���� �
1kT
1-k
T1-k1k
1kT
1-k
T1-k1k
1-k1k
T1-k
T1-k1k
k dyyy
dyydIH
dydyIH
�
�
�
�
�
� �¸¹
ᬩ
§�¸
¹
ᬩ
§�
1k1-
1-kT
1k
-11-k
T1k1k
-11-k
1kT
1-k
T1-k1k1-
1-k1-
k yHyHyyH
ydddHH
��
��
�
� �� ¯®
� �
)g(x)g(xyxxdavec
1-kk1-k
1-kk1-k
0yd 1kT
1-k !�
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
268
Max CERF2018
2.2.2 Méthode DFP
Algorithme DFP• Direction de descente à l’itération k :
• Minimisation dans la direction uk-1 :
• Mise à jour de l’inverse du hessien
Propriété 1La mise à jour DFP donne une matrice définie positive siCette condition est réalisée si xk est obtenu par minimisation exacte dans la direction
Propriété 2Pour une fonction f quadratique :
l’algorithme DFP donne des directions successives vérifiant :
o directions conjuguées par rapport à Qo convergence en n itérations avec à l’itération n :
1k1-
1-kT
1k
-11-k
T1k1k
-11-k
1kT
1-k
T1-k1k1-
1-k1-
k yHyHyyH
ydddHH
��
��
�
� �� ¯®
� �
)g(x)g(xyxxdavec
1-kk1-k
1-kk1-k
0yd 1kT
1-k !�
)x(gH 1k-1
1-k ��
� �¯®
�o�
� ��
����
1k1ks
1k-1
1-k1k1k1kk suxfmins
)x(gHuavecsuxx
)x(gHu 1k-1
1-k1k �� �
xcQxx21)x(f TT �
¯®
dd dzd
� ki0,uQuHkji0,0Quu
ii1
k
ji
QHn
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
269
Max CERF2018
2.2.2 Méthode SR1
Equation sécanteLa méthode SR1 construit une solution Hk de l’équation sécante
• Symétrique, de rang 1 (i.e. dépendante d’un seul vecteur u de Rn)• Non nécessairement définie positive.
Méthode de résolution• On cherche la matrice Hk à partir de Hk-1 sous la forme
• Equation sécante :
• On pose :
• On reporte u pour obtenir J :
• On exprime uuT en fonction de dk-1, yk-1, Hk-1
1k1kk ydH ��
T1-kk uuHH �
ududHyduudHdHy 1kT
1k1-k1k1kT
1k1-k1kk1k ������� ���
� �1k1-k1k1k1-k1k dHyuu1dHy ���� �J �J
��1kTdu1
� J
21k1-k1kT
1-k1kT
1k1-k1k1)dHy(dd)dHy(1J
���J J �����
o addition d’une matrice symétrique de rang 1
� �
°
°®
� J
�J
��
��
)dHy(d1dHyu
1k1-k1kT
1-k2
1k1-k1kT
1k1-k1k1k1-k1k2T )dHy)(dHy(uu ���� ��J �
)dHy(d)dHy)(dHy(uu
1k1-k1kT
1-k
T1k1-k1k1k1-k1kT
��
����
���
�
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
270
Max CERF2018
2.2.2 Méthode SR1
Formule SR1
• Mise à jour de Hk :
• 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)
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 :
la formule SR1 donne après n déplacements suivant des directions indépendantes dk :o ne nécessite pas de minimisation suivant dk
)dHy(d)dHy)(dHy(HH
1k1-k1kT
1-k
T1k1-k1k1k1-k1k
1-kk��
����
���
� ¯®
� �
)g(x)g(xyxxdavec
1-kk1-k
1-kk1-k
xcQxx21)x(f TT �
QHn
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
271
Max CERF2018
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 2Définie positive
Symétrique AAT
Rang 2Définie positive
Symétrique uuT
Rang 1Indéfinie
Minimisation dk Précision moyenne Précision forte Précision faible
Fonction quadratique Hessien exact : Hn=QDirections conjuguées Q-1
Hessien exact : Hn=QDirections conjuguées Q
Hessien exact : Hn=Q
Limitations Hessien de f indéfini Hessien de f indéfiniPrécision minimisation
Matrices Hknon définies positives
Méthode BFGS réputée la plus efficace
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
272
Max CERF2018
2.2.2 Exemple
Méthode de quasi-Newton à une variableLes formules BFGS et SR1 se simplifient pour une fonction à une variable.
• Fonction f(x) , x�R
• Mise à jour BFGS :
• Mise à jour SR1 :
o On retrouve la formule de la sécante appliquée au gradient de f.
1k
1k1-k1k1-k
1k1-k1kT
1-k
T1k1-k1k1k1-k1k
1-kk
ddHyH
)dHy(d)dHy)(dHy(HH
�
��
��
����
��
���
�
1-k1k
1k1-k
1k1-kT
1k
1-kT
1k1k1-k
1kT
1-k
T1-k1k
1-kk
HdyH
dHdHddH
dyyyHH
��
��
�
�
��
��
�
�
1-kk
1-kk
1k
1kk xx
)g(x)g(xdyH
��
��
�
1-kk
1-kk
1k
1kk xx
)g(x)g(xdyH
��
��
�
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
273
Max CERF2018
2.2.2 Exemple
Comparaison Newton � Quasi-Newton• Fonction :
• Dérivée :
• Quasi-Newton :
• Point initial : x0 = 3 o convergenceAutres points o divergence
ou maximum de f
x60x47x12x)x(f 234 ����
60x94x36x4)x('f 23 ����
-1,50
-1,25
-1,00
-0,75
-0,50
-0,25
0,00
0,25
2,75 3,00 3,25 3,50 3,75 4,00 4,25
NewtonQuasi - Newton
Itération x(k) f(x) f'(x) h(k) Erreur0 3,00000000 0,00000000 -6,00E+00 1,000 -4,56E-011 2,99900000 0,00600700 -6,01E+00 14,000 -4,57E-012 3,42857155 -1,31945027 -3,15E-01 13,267 -2,70E-023 3,45230465 -1,32362420 -3,79E-02 11,672 -3,28E-034 3,45554876 -1,32368634 -4,68E-04 11,527 -4,06E-055 3,45558934 -1,32368635 -7,27E-07 11,509 -6,32E-086 3,45558940 -1,32368635 -1,40E-11 11,509 -1,22E-127 3,45558940 -1,32368635 -5,68E-14 11,462 -4,44E-15
Itération x f(x) f'(x) f''(x) Erreur0 3,00000000 0,00000000 -6,00E+00 14,000 -4,56E-011 3,42857143 -1,31945023 -3,15E-01 11,796 -2,70E-022 3,45526446 -1,32368574 -3,74E-03 11,513 -3,25E-043 3,45558935 -1,32368635 -5,77E-07 11,509 -5,01E-084 3,45558940 -1,32368635 -5,68E-14 11,509 -4,88E-15
1-kk
1-kkk xx
)x('f)x('fh��
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
274
Max CERF2018
2.2.2 Exemple
Méthode DFP à 2 variables• Minimisation de
• Point initial : x0 = (0 0)
• Itération 1 :
• Mise à jour DFP de H-1
• Comparaison au vrai hessien :
2221
2121 xxx2x2xx)x(f ���� ¸
¹
ᬩ
§�����
�21
21
x2x21x2x41
)x(g
¸¹
ᬩ
§ �
1001
H 10 ¸
¹
ᬩ
§�
11
g0 ¸¹
ᬩ
§� � o �
11
gHu 01
01
¸¹
ᬩ
§��
o¸¹
ᬩ
§� o o� o¸
¹
ᬩ
§� �
11
g11
x1ss2s)s(Fminss
suxx 112
s101
¸¹
ᬩ
§� ¸
¹
ᬩ
§� o
¯®
� �
02
y,11
d)g(x)g(xyxxd
00010
010
¸¹
ᬩ
§�
� �¸
¹
ᬩ
§ �
2111
21H
2224
)x(H 1
¸¹
ᬩ
§
00
x0
¸¹
ᬩ
§�
� ¸
¹
ᬩ
§�¸
¹
ᬩ
§�
��¸
¹
ᬩ
§ ��
3111
21
0004
41
1111
21
1001
yHyHyyH
yddd
HH0
1-0
T0
-10
T00
-10
0T0
T001-
01-
1
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
275
Max CERF2018
2.2.2 Exemple
Méthode DFP à 2 variables
• Itération 2 :
• On obtient le minimum en 2 itérations (fonction quadratique) :
• Mise à jour DFP de H-1
• Comparaison au vrai hessien :
¸¹
ᬩ
§��
11
g1 ¸¹
ᬩ
§ � o �
10
gHu 11
12
¸¹
ᬩ
§ o¸
¹
ᬩ
§ � o o���� o¸
¹
ᬩ
§��
� 00
g5.11
x21s)s1()s1(31)s(Fmin
s11
suxx 222
s212
¸¹
ᬩ
§�
�
3111
21H 1-
1¸¹
ᬩ
§�
11
x1
¸¹
ᬩ
§ �
5.11
*x
¸¹
ᬩ
§ ¸
¹
ᬩ
§ o
¯®
� �
11
y,5.0
0d)g(x)g(xy
xxd11
121
121
¸¹
ᬩ
§�
� �¸
¹
ᬩ
§ �
2111
21H
2224
)x(H 1
¸¹
ᬩ
§�
� ¸
¹
ᬩ
§�¸
¹
ᬩ
§�¸
¹
ᬩ
§�
� ��
2111
21
1000
1000
21
3111
21
yHyHyyH
ydddHH
11-
1T1
-11
T11
-11
1T1
T111-
11-
2
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
276
Max CERF2018
2.2.2 Exemple
Méthode DFP à 2 variablesOn vérifie les propriétés de la méthode DFP appliquée à une fonction quadratique.
• Le minimum est obtenu en 2 itérations.
• Les directions successives u1 et u2 sont conjuguées par rapport à Q
• On vérifie également :
¸¹
ᬩ
§ o
2224
Q
002
10
11
2224
10
QuuTT
1T2 ¸
¹
ᬩ
§�¸¹
ᬩ
§ ¸
¹
ᬩ
§�¸¹
ᬩ
§¸¹
ᬩ
§
111
1 u11
11
4202
21
11
2224
3111
21QuH ¸
¹
ᬩ
§� ¸
¹
ᬩ
§�¸¹
ᬩ
§ ¸
¹
ᬩ
§�¸¹
ᬩ
§¸¹
ᬩ
§�
� �
¸¹
ᬩ
§¸¹
ᬩ
§�
�¸¹
ᬩ
§¸¹
ᬩ
§¸¹
ᬩ
§ ����
2
1T
2
1T
2
12221
2121 x
x1
1xx
2224
xx
21xxx2x2xx)x(f
221
2 u10
10
1001
10
2224
2111
21QuH ¸
¹
ᬩ
§ ¸
¹
ᬩ
§¸¹
ᬩ
§ ¸
¹
ᬩ
§¸¹
ᬩ
§¸¹
ᬩ
§�
� � 11
2 QHavec ��
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
277
Max CERF2018
2.2.2 Extensions BFGS
Initialisation BFGS• En pratique, le hessien n’est pas nécessairement défini positif partout.
Pour assurer la convergence, il est nécessaire de réinitialiser périodiquement H0 :- par évaluation du hessien (différences finies) → coûteux- par un multiple positif de l’identité → H0 = WI avec W > 0
• On peut réinitialiser H0 à partir du dernier déplacement de xk�1 à xk :
• JustificationOn note H le hessien en xk�1
H défini positif → admet une base orthonormée de vecteurs propres (vi)i=1à n avec H = OiviEn notant Om la plus grande valeur propre, on a approximativement :
→ approximation de Om
dyyyavecIH T
T
0 WW
¯®
� �
�
�
)x(g)x(gyxxd
1kk
1kk
mm
2m
2m
2m
T
T
mmmiii
mmii
dyyy
vvHdy
vvdO
ODOD
| Wo°°®
OD|OD |
D|D
¦¦
Hd)xx(Hy)xx(H)x(g)x(g
1kk
1kk1kk
�|o��|o
�
��
I1H 1-0 W o pour initialiser -1
0H
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
278
Max CERF2018
2.2.2 Extensions BFGS
Méthode damped BFGS• La méthode BFGS supposent que les matrices Hk restent définies positives.
Cette condition n’est pas nécessairement réalisée- pour une optimisation sans contrainte loin de l’optimum- pour une optimisation avec contrainte (hessien du lagrangien non nécessairement positif)
• BFGS standard :
La matrice H représente une approximation- du hessien de f pour un problème sans contrainte →- du hessien de L pour un problème avec contrainte →
• La matrice courante H est par hypothèse définie positive.La nouvelle matrice H’ doit rester définie positive.
• La mise à jour prend en compte la courbure suivant la direction de déplacement d.- le terme dTHd vient de la matrice courante H → par hypothèse > 0- le terme dTy vient de la variation du gradient → non nécessairement > 0
à modifier
)x(f)x(fy 1kxkx ���� ),x(L),x(Ly k1kxkkx O��O� �
ydyy
HddHHddHH' T
T
T
T
�� ® � �
®
�
��)x(g)x(gy
xxdetH'HHHavec
1kk
1kk
k
1k
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
279
Max CERF2018
2.2.2 Extensions BFGS
Méthode damped BFGS• La méthode damped BFGS (BFGS « amorti ») consiste à pondérer la mise à jour si dTy < 0.
On remplace la variation y par z : avec 0 ≤ T ≤ 1
La mise à jour BFGS « amortie » est :
Pour que la nouvelle matrice H’ soit définie positive, il suffit que dTz soit positif.
• On choisit la pondération T pour vérifier la condition :
Si dTy t D dTHd , on prend : z = y (BFGS standard)
Si dTy < D dTHd , on impose :
• La matrice H’ est une interpolation entre : la matrice H initiale (obtenue pour T = 0)la matrice BFGS standard (obtenue pour T = 1).
zdzz
HddHHddHH' T
T
T
T
�� → avec z au lieu de y
HddHdd)(1ydzd TTTT D T��T
2.0avecHddzd TT DDt
ydHddHdd)(1TT
T
�D�
T�
1 T�^
Hd)(1yz T��T
terme positifHdd)(1ydzd TTT T��T �
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
280
Max CERF2018
2.2.2 Extensions BFGS
Méthode L�BFGS• Pour un problème de grande dimension, on ne peut pas stocker les matrices Hk en mémoire.
La méthode L-BFGS (« Limited Memory ») est basée sur la mise à jour factorisée.
• On note pour simplifier : et
• On considère m itérations successives à partir de la matrice H0.
¯®
� �
��
��
)x(g)x(gyxxd
avec1kk1k
1kk1k
1kT
1-k
T1-k1k
1kT
1-k
T1-k1k1-
1-k1k
T1-k
T1-k1k1-
k yddd
yddyIH
ydydIH
�
�
�
�
�
� �¸¹
ᬩ
§�¸
¹
ᬩ
§�
T0000
-10
T0
-11 ddVHVH U�
� � � ��
T1111
T00
T1010
-10
T0
T1
T1111
-11
T1
-12 ddVddVVVHVVddVHVH U�U� U�
� � � � � � � �1-m1T00
T1
T1-m01-m10
-10
T0
T1
T1-m
T1-m1-m1m1-m
-11-m
T1-m
-1m VVddVVVVVHVVVddVHVH ���� U� U� �
� � � �1-m2T11
T2
T1-m1 VVddVV ��U�
T1-m1-m1m dd�U�
��
Tjjjj dyIV U�
jTj
j yd1
U Tjjjj
-1j
Tj
-11j ddVHVH U� o �
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
281
Max CERF2018
2.2.2 Extensions BFGS
Méthode L�BFGS• Le déplacement à l’itération m est :
sm = pas de déplacement
On peut évaluer la direction de déplacement sans calculer explicitement la matrice Hmen utilisant les vecteurs dj et yj des m itérations précédentes (j = 0 à m�1).
• On obtient le vecteur en réalisant 2 boucles successives.- une première boucle de j = m�1 à 0 pour calculer les termes de droite- une deuxième boucle de j = 0 à m�1 pour multiplier à gauche par et sommer
Ces opérations ne manipulent que des vecteurs, sans stockage de matrice.
)x(fgavecgHsd mmm-1mmm � �
� � � �� � � �� � � �
mT
1-m1-m1m
m1-m2T11
T2
T1-m1
m1-m1T00
T1
T1-m0
m1-m10-10
T0
T1
T1-mm
-1m
gdd
gVVddVV
gVVddVV
gVVVHVVVgH
�U�
�U�
U�
�
��
��
��Tjjjj dyIVavec U�
m-1mgH
m-1mgH
� � m1-mj gVV �� �T
jT
1-m VV �
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
282
Max CERF2018
2.2.2 Extensions BFGS
Méthode L�BFGS• Rappel de l’expression de
• La première boucle de j = m�1 à 0 calcule les termes
• On obtient à la fin de cette boucle :et les termes : D0 , … , Dm�1
¯®
D� U D
���
���
1m1mm1m
mmmT
1m1m1m
yqqgqavecqd
0à1mjpouryqq
qd
jj1jj
1jTjjj �
°°®
D�
U D
�
�
� � m1-m1jTjjj gVVd ��U D
m-1mgH
� � m1-m00 gVVq �
� � � �� � � �
� � � �
mT
1-m1m1-m
m1-m1jTjjj
T1j
T1-m
m1-m1T000
T1
T1-m
m1-m10-10
T0
T1
T1-mm
-1m
gdd
gVVddVV
gVVddVV
gVVVHVVVgH
�
��
U�
�
U�
�
U�
�
��
�
��
�� Tjjjj dyIVavec U�
→ j = 0 à m�1
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
283
Max CERF2018
2.2.2 Extensions BFGS
Méthode L�BFGS• Rappel de l’expression de
• La deuxième boucle de j = 0 à m�1 consiste à multiplier à gauche par
• Le premier terme de est issu de .Les termes suivants sont issus des Dj stockés lors de la première boucle.
On obtient à la fin de cette boucle la direction de déplacement :
� �� �
� �
1m1-m
jjT
1jT
1-m
00T
1T
1-m
0-10
T0
T1
T1-mm
-1m
d
dVV
dVV
qHVVVgH
�
�
D��
D�
�
D�
�
�
�
�
�
m-1mgH
¯®
D�E� U E �
000001
01
000T000
ddrrqHravecry
1mà0jpourddrr
ry
jjjjj1j
jTjjj �
°°®
D�E�
U E
�
� � jT
1jT
1-m dVV ��
0-100 qHr
Tjjj
Tj ydIVavec U�
→ j = 0 à m�1
� � m1-m1jTjjj gVVd ��U D
� � m1-m00 gVVqet �
m-1mgH
m-1mm gHr
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
284
Max CERF2018
2.2.2 Extensions BFGS
Méthode L�BFGSA l’itération numéro k, la direction de déplacement est construite à partir :- d’une matrice initiale- des m déplacements précédents (dj , yj)j=k�m à k�1
• On choisit la matrice initiale de la forme :
→ W�1 est une approximation de la plus grande valeur propre
• On construit la direction de déplacement par les 2 boucles successiveset le nouveau point avec un pas de déplacement sk
• La liste des m déplacements stockés est mise à jour :- on supprime en début de liste le déplacement numéro k�m (à partir des itérations k t m)- on ajoute en fin de liste le nouveau déplacement (dk , yk)
• RemarquePendant les m�1 premières itérations, la méthode L�BFGS est équivalente à BFGS si l’on conserve la même matrice initiale .
1kT
1k
1kT
1k1-k0, yy
dyavecIH��
�� WW
k-1kk gHr o
k-1kkk gHsd � o
-10
-1k0, HH
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.2 Minimisation
Techniques d’optimisation
285
Max CERF2018
2.2.3 Globalisation
� Convergence de la méthode de Newton
� Méthodes de globalisation
� Fonction mérite
� Filtre
� Point de Newton et de Cauchy
� Méthode d’homotopie
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
286
Max CERF2018
2.2.3 Convergence
Sensibilité au point initialLa méthode de Newton est très sensible au point initial.Une modification du point initial peut conduire à une solution différente ou à une divergence.o instabilité numérique (comportement chaotique)o bassins d’attraction en présence de plusieurs solutions
Exemple• On cherche à résoudre l’équation complexe : z3 = 1
• Les solutions sont les 3 racines complexes de l’unité :
• On applique la méthode de Newton à partir d’un point initial z0.
231u,
231u,1u 321
��
��
� �¯®
r o TS To T� � � TT
1r1)3cos(rk30)3(sinr1er1re1z 3
33.i33i3
2k
3k
2k
3k
k1k z31z2
z31zzz �
�� �
u1
u2
u3
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
287
Max CERF2018
2.2.3 Convergence
Bassin d’attraction• Le bassin d’attraction d’une racine u est l’ensemble des points initiaux z0
pour lesquels la méthode de Newton converge vers u.
• On observe dans le plan complexeles bassins d’attraction de u1, u2, u3.
• Les contours sont mal délimités.o aspect fractalo sensibilité au point initial
• La convergence est imprédictibleà partir de certains points initiaux.
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
288
Max CERF2018
2.2.3 Globalisation
Techniques de globalisation• La convergence d’une méthode de (quasi) Newton n’est pas garantie même près de la solution.
Il faut évaluer et si besoin modifier le point xN issu de l’itération de (quasi) Newton.
• Méthode d’évaluation d’une solution- fonction mérite → agrégation des objectifs avec pondérations- filtre → acceptation des solutions non dominées
• Méthode d’exploration locale- recherche linéaire → suivant la direction du point de Newton xN- région de confiance → à l’intérieur d’une sphère centrée sur le point initial
en utilisant les points de Newton xN et de Cauchy xC
Objectifs simultanésLe nouveau point doit minimiser simultanément plusieurs objectifs.
• Résolution d’équations :
• Minimisation sous contrainte :
0)x(g ^ `)x(g,,)x(gmin m1x�o
0)x(csous)x(fminx
^ `)x(c,,)x(c,)x(fmin m1x�o
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
289
Max CERF2018
2.2.3 Fonction mérite
Principe• On cherche à minimiser simultanément plusieurs fonctions :
• On définit une fonction mérite F(x) permettant de comparer différentes solutions.
Une solution x est meilleure qu’une solution y si
• La fonction mérite agrège les différents objectifs avec des pondérations (ou pénalisations).Le choix des coefficients permet de privilégier certains objectifs.
Exemples de fonctions mérites• Résolution d’équations :
• Minimisation sous contrainte :
- critère augmenté
- lagrangien augmenté
^ `)x(c,,)x(cmin m1x�
)y(F)x(F �
)x(c)x(f)x(F U� o
0)x(g )x(g)x(F o
0)x(csous)x(fminx
¦U o )x(g)x(F ii
→ norme 1, 2, …→ pénalisations Ui
)x(c)x(c)x(f)x(c),x(L)x(F
T U�O� U�O o
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
290
Max CERF2018
2.2.3 Filtre
Principe• On cherche à minimiser simultanément plusieurs fonctions :
• On définit une relation de dominance permettant de comparer différentes solutions.
Une solution x domine une solution y si → améliore tous les objectifs
• Le front de Pareto est l’ensemble des solutions non dominées.
^ `)x(c,,)x(cmin m1x�
°
°®
d
d
)y(c)x(c
)y(c)x(c
mm
11�
c2
c1
x
y
front de Paretoc2(x)
c1(x)
solutions dominées par x
solutions dominant x solutions non dominéespar x
solutions non dominéespar x
x
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
291
Max CERF2018
2.2.3 Filtre
Filtre• Le filtre est la liste des solutions non dominées obtenues au cours des itérations.
→ approximation du front de Pareto
• Evaluation d’un nouveau point- Le nouveau point est accepté s’il n’est dominé par aucun élément du filtre.- Le filtre est mis à jour en ajoutant le nouveau point et en éliminant les éléments dominés.
points du filtre
c2
c1
x1
x2
x3
x4
Région de solutions dominées→ rejetées par le filtre
Région de solutions non dominées→ acceptées par le filtre
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
292
Max CERF2018
2.2.3 Exemple
ExempleOn cherche à résoudre par la méthode de Newton le système d’équations :
→ solution
• Le déplacement de Newton est :
• On applique une recherche linéaire dans la direction de Newton :
• On compare l’évaluation par fonction mérite et par filtre à partir du point initial
La fonction mérite est :
0)xx(10x1)x,x(c 2
12
121 ¸
¹·
¨©§
�� ¸
¹·¨
©§ 11x*
Nsdx'x �
¸¹
ᬩ
§��
� ¸
¹
ᬩ
§�
�¸¹
ᬩ
§�
¸¹
ᬩ
§�
�¸¹
ᬩ
§ ���
�
211
1212
1
1212
1T
1N x)x2(x
x1)xx(10
x11x20
010101
)xx(10x1
100x201
d
ccd TN
���
¸¹
ᬩ
§��
��¸¹
ᬩ
§ ¸
¹
ᬩ
§
211
1
2
1
2
1
x)x2(xx1
sxx
'x'x
)xx(10x1)x,x(c)x,x(F 212112121 ���
¸¹·¨
©§ 00x0
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
293
Max CERF2018
2.2.3 Exemple
Fonction mérite• Le déplacement est accepté si la fonction mérite décroît.
→ nécessite
• La solution est obtenue en 11 itérations à partir du point initial
1)0,0(Favec)xx(10x1)x,x(c)x,x(F 212112121 ���
Itération Pas s x1 x2 F(x1,x2) c1 c2
0 0,0000 0,0000 0,0000 1,0000 1,0000 0,00001 0,0625 0,0625 0,0000 0,9766 0,9375 -0,03912 0,0625 0,1211 0,0076 0,9499 0,8789 -0,07103 0,0625 0,1760 0,0213 0,9207 0,8240 -0,09674 0,1250 0,2790 0,0588 0,9117 0,7210 -0,19075 0,1250 0,3691 0,1115 0,8789 0,6309 -0,24816 0,1250 0,4480 0,1728 0,8312 0,5520 -0,27927 0,2500 0,5860 0,3034 0,8139 0,4140 -0,39998 0,2500 0,6895 0,4347 0,7175 0,3105 -0,40709 0,5000 0,8448 0,6691 0,5998 0,1552 -0,4445
10 1,0000 1,0000 0,9759 0,2410 0,0000 -0,241011 1,0000 1,0000 1,0000 0,0000 0,0000 0,0000
¸¹·¨
©§ 00x0
près1.0àxx 212 r|
0,0
0,2
0,4
0,6
0,8
1,0
0,0 0,2 0,4 0,6 0,8 1,0
x2
x1
proche de la courbex2=x1²
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
294
Max CERF2018
2.2.3 Exemple
Filtre• Le déplacement est accepté si au moins l’une des composantes de c décroît.
• Le déplacement de Newton (s=1) est accepté à l’itération 1car la composante c1 décroît.
L’évaluation par fonction mérite aurait rejeté le pas s=1car la fonction mérite augmente de 1 à 10.
• La solution est obtenue en 2 itérations à partir du point initial
0,0
0,2
0,4
0,6
0,8
1,0
0,0 0,2 0,4 0,6 0,8 1,0
x2
x1
0)xx(10x1)x,x(c 2
12
121 ¸
¹·
¨©§
��
¸¹·¨
©§ 00x0
Itération Pas s x1 x2 F(x1,x2) c1 c2
0 0 0,0000 0,0000 1,0000 1,0000 0,0000
1 1 1,0000 0,0000 10,0000 0,0000 -10,0000
2 1 1,0000 1,0000 0,0000 0,0000 0,0000
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation
Techniques d’optimisation
295
Max CERF2018
2.2.3 Point de Newton et de Cauchy
Points particuliersDeux points particuliers sont définis à partir du modèle quadratique de f en xk :
• Point de Newton• Point de Cauchy
Point de NewtonLe 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.
o dN solution des équations de Newton
Point de CauchyLe point de Cauchy xC de f en xk minimise le modèle quadratique en xk dans la direction �gk.
solution de o minimum suivant la plus forte descente
Si f est convexe suivant –gk :
)x(xH)x(x21)x(xg)(xf(x)f kk
Tkk
Tkkkk �����
¯®
� �
)(xfH)(xfgavec
kk2
k
kkk
kCkC gαxx �
kkTk
kTk
C gHggg
α
o points utiles dans les algorithmes de globalisation
)αgf(xmin kk0α�
t
)f(x)df(xavecdxx kNk2
NkN �� ��
2 Optimisation sans contraintes2.2 Méthode de Newton2.2.3 Globalisation