Ecole Nationale Polytechnique de Constantine Pr. K.
KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------
Chapitre II : Optimisation sans contraintes unidimensionnelle
On suppose que la fonction 𝑓 est uni-modale dans le domaine [𝑥1 , 𝑥2 ]. Il existe deux types de
méthodes :
• Méthodes à dérivée (indirectes) ;
• Méthodes d’élimination de régions (directes).
II.1Méthodes indirectes
. II.1.1Méthode de Newton-Raphson
La première condition nécessaire de 𝑓(𝑥) pour déterminer l’optimum local est que 𝑓 ′′ (𝑥 ) = 0.
Par conséquent, on peut résoudre 𝑓 ′ (𝑥 ) = 0 par la méthode de Newton-Raphson. L’expression
du développement de Taylor tronquée au deuxième terme s’écrit :
1 (1)
𝑓(𝑥) = 𝑓(𝑥𝑘 ) + 𝑓 ′ (𝑥𝑘 ). (𝑥 − 𝑥𝑘 ) + 𝑓 ′′ (𝑥𝑘 ). (𝑥 − 𝑥𝑘 )2
2
⟹ 𝑓 ′ (𝑥 ) = 𝑓 ′ (𝑥𝑘 ) + 𝑓 ′′ (𝑥𝑘 ). (𝑥 − 𝑥𝑘 ) = 0
𝑓′(𝑥𝑘 )
⟹ 𝑥𝑘+1 = 𝑥𝑘 −
𝑓′′(𝑥𝑘 )
II.1.2. Méthode de la Sécante
Le modèle approximé est analogue à l’équation (1) :
𝑓 ′ (𝑥 𝑘 ) + 𝑚 (𝑥 − 𝑥 𝑘 ) = 0
𝑚𝑥 − 𝑓 ′ (𝑥 ) 𝑓′(𝑥𝑘 )
⟹ 𝑥𝑘 = =𝑥−
𝑚 𝑚
Où : 𝑚 est la pente de la droite qui connecte 𝑥𝑝 et le seconde point 𝑥𝑞 donné par :
𝑓 ′ (𝑥𝑞 ) − 𝑓′(𝑥𝑝)
𝑚=
𝑥𝑞 − 𝑥𝑝
Alors, on obtient :
𝑓 ′ (𝑥𝑘 ). (𝑥𝑞 − 𝑥𝑝)
𝑥𝑘+1 = 𝑥𝑘 +
𝑓 ′ (𝑥𝑞 ) − 𝑓 ′ (𝑥𝑝)
Ecole Nationale Polytechnique de Constantine Pr. K. KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------
II.1.3. Méthode Quasi-Newton
Cette méthode est similaire à la méthode de Newton-Raphson. Si (𝑓𝑥 ) est donné par une formule
compliquée où on ne peut pas trouver analytiquement ses dérivées. On peut remplacer l’équation
(1) par l’approximation avec les différences finies.
𝑓(𝑥 + Δ𝑥) − 𝑓(𝑥 − Δ𝑥) Centrée
𝑓 ′ (𝑥) =
2Δ𝑥
𝑓(𝑥 + Δ𝑥) − 𝑓(𝑥) En avant
𝑓 ′ (𝑥) =
Δ𝑥
𝑓(𝑥) − 𝑓(𝑥 − Δ𝑥) En arrière
𝑓 ′ (𝑥) =
Δ𝑥
𝑓 (𝑥 + Δ𝑥 ) − 2𝑓 (𝑥 ) + 𝑓(𝑥 − Δ𝑥)
𝑓 ′′ (𝑥 ) =
Δ𝑥 2
Alors :
𝑓(𝑥𝑘 + Δ𝑥 ) − 𝑓(𝑥𝑘 − Δ𝑥)
𝑥𝑘+1 = 𝑥𝑘 − 2Δ𝑥
𝑓 𝑥𝑘 + Δ𝑥 − 2𝑓 (𝑥𝑘 ) + 𝑓(𝑥𝑘 − Δ𝑥)
( )
Δ𝑥 2
Δ𝑥 𝑓(𝑥 + Δ𝑥 ) − 𝑓(𝑥 − Δ𝑥)
⟹ 𝑥𝑘+1 = 𝑥𝑘 −
2 𝑓(𝑥 + Δ𝑥 ) − 2𝑓(𝑥 ) + 𝑓(𝑥 − Δ𝑥)
II.2.Méthodes directes
Le principe des méthodes directes est l’évaluation successive de la fonction jusqu’à l’obtention
de l’optimum. L’évaluation de la fonction en un seul point 𝑥1 ∈ [𝑎, 𝑏] ne donne aucune
indication où se trouve l’optimum. Par contre, si on prend un deuxième point 𝑥2 et on calcule
𝑓(𝑥2 ), on peut calculer l’optimum.
1er cas : 𝑓(𝑥1 ) < 𝑓(𝑥2 )
On doit éliminer la région [𝑥2, 𝑏] et l’optimum se trouve à gauche de 𝑥2.
2ème cas : 𝑓(𝑥1 ) > 𝑓(𝑥2 )
On doit éliminer la région [𝑎, 𝑥1 ] et l’optimum se trouve à droite de 𝑥1 .
Ecole Nationale Polytechnique de Constantine Pr. K. KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------
3ème cas : 𝑓(𝑥1 ) = 𝑓(𝑥2 )
On doit éliminer les deux régions [𝑎, 𝑥1 ] et [𝑥2 , 𝑏], et l’optimum se trouve dans l’intervalle
[𝑥1 , 𝑥2 ].
Le principe de chaque méthode directe est comment placer 𝑥1 et 𝑥2, puis réduire l’intervalle de
recherche progressivement.
II.2.1.Méthode des intervalles égaux
En plaçant [𝑥1 , 𝑥2 ] de façon que :
𝑥1 − 𝑎 = 𝑥2 − 𝑥1 = 𝑏 − 𝑥2
Pour réduire les
intervalles, il faut calculer
𝑓(𝑥1 ) et 𝑓(𝑥2 ).
2
𝐿1 = 𝐿
3 0
2
𝐿2 = 𝐿
3 1
2
𝐿3 = 𝐿
3 2
2
Donc, l’itération 𝑘 sera : 𝐿𝑘 = 𝐿𝑘−1
3
Et on définit la réduction après 𝑛 itération comme étant :
𝐿𝑛 2 𝑛
𝑅= =( )
𝐿0 3
II.2.2. Méthode de dichotomie
Le principe est de positionner
deux points 𝑥1 et 𝑥2 de part et
d’autre du milieu de
l’intervalle [𝑎, 𝑏 ] tel que :
𝑥2 − 𝑥1 = 𝜖
Ecole Nationale Polytechnique de Constantine Pr. K. KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------
𝐿0 1 𝑘 𝐿𝑘 1 𝑘
𝐿1 = ⟹ 𝐿𝑘 = ( ) . 𝐿0 et : 𝑅 = =( )
2 2 𝐿0 2
II.2.3.Méthode de section d’or (Golden Section Search)
Pour minimiser la fonction :
𝑏 𝑎 𝑏
Soit 𝜙 = , et à partir de la similarité des échelles : = =𝜙
𝑎 𝑎+𝑏 𝑎
𝑎 𝑎+𝑏 𝑏
⇒ = =1+ =1+𝜙
𝑏 𝑎 𝑎
⇒ 𝜙2 − 𝜙 − 1 = 0
√5−1
Alors : 𝜙 = = 0,618 (Nombre d’or)
2
A partir du graphe :
𝑥2 − 𝑥𝐿 𝑥𝑢 − 𝑥1
𝜙= = = 0,618
𝑥𝑢 − 𝑥𝐿 𝑥𝑢 − 𝑥𝐿
• Si 𝑓(𝑥2 ) < 𝑓(𝑥1 ) : on elimine [𝑥𝐿, 𝑥1 ]
Donc : 𝑥𝐿 ← 𝑥1 et on calcule la nouvelle valeur de 𝑥1 : 𝑥1 ← ?
(1)
𝑥𝑢 − 𝑥1 (1)
= 0,618 ⇒ 𝑥1 = 𝑥𝑢 − 𝜙(𝑥𝑢 − 𝑥𝐿 )
𝑥𝑢 − 𝑥𝐿
• Si 𝑓(𝑥1 ) < 𝑓 (𝑥2 ) : on elimine [𝑥2, 𝑥𝑢 ]
Donc : 𝑥𝑢 ← 𝑥2 et on calcule la nouvelle valeur de 𝑥2 : 𝑥2 ← ?
(1)
𝑥 2 = 𝑥 𝐿 + 𝜙 (𝑥 𝑢 − 𝑥 𝐿 )
Remarque : pour la maximisation de la fonction, la procédure pour les deux cas sera
inversée.
Ecole Nationale Polytechnique de Constantine Pr. K. KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------
II.2.4. Méthode d’approximation polynomiale
Le principe de cette méthode est basé sur l’approximation des fonctions objectif par des
polynômes du 2ème et 3ème degré, et dans ce cas on dira que c’est une approximation quadratique
(2ème degré) ou cubique (3 ème degré).
II.2.4.1. Méthode d’approximation quadratique
L’idée de cette méthode, en cas de la minimisation, est :
• D’approximer la fonction objectif 𝑓(𝑥) par une fonction quadratique 𝑃2 (𝑥), en démarrant
avec 3 points, et leurs valeurs de la fonction objectif dans l’ordre croissant (qui inclut le
minimum).
• De renouveler les 3 points en remplaçant l’un des trois avec le point minimal de 𝑃2 (𝑥).
Considérons les trois points {(𝑥0 ; 𝑓 (𝑥0 )), (𝑥1 , 𝑓 (𝑥1 )) , (𝑥2 , 𝑓(𝑥2 ))}
La fonction objectif est approchée par un polynôme :
𝑃2 (𝑥 ) = 𝑎 + 𝑏𝑥 + 𝑐𝑥 2
Et l’optimum est obtenu par : 𝑃2′ (𝑥 ) = 𝑏 + 2𝑐𝑥 = 0
−𝑏
⇒ 𝑥𝑜𝑝𝑡 = où ; 𝑎, 𝑏 𝑒𝑡 𝑐 sont calculés par la résolution du système :
2𝑎
𝑃2 (𝑥0 ) = 𝑎 + 𝑏𝑥0 + 𝑐𝑥02
{𝑃2 (𝑥1 ) = 𝑎 + 𝑏𝑥 + 𝑐𝑥12
𝑃2 (𝑥2 ) = 𝑎 + 𝑏𝑥2 + 𝑐𝑥22
−𝑏
En substituant les expressions de 𝑎, 𝑏 𝑒𝑡 𝑐 dans l’expression 𝑥𝑜𝑝𝑡 = , on aura :
2𝑎
1 𝑓(𝑥0 ). (𝑥12 − 𝑥22 ) + 𝑓 (𝑥1 ). (𝑥22 − 𝑥02 ) + 𝑓(𝑥2 ). (𝑥02 − 𝑥12 )
𝑥3 = .
2 𝑓 (𝑥0 ). (𝑥1 − 𝑥2 ) + 𝑓 (𝑥1 ). (𝑥2 − 𝑥0 ) + 𝑓(𝑥2 ). (𝑥0 − 𝑥1 )
On calcule 𝑓(𝑥3 ), et on élimine le point qui donne la grande valeur de la fonction (dans le cas de
la minimisation). Et pour l’itération suivante, on aura les deux points initiaux et le nouveau point
𝑥3. On recalcule le nouveau point 𝑥4 de la même manière jusqu’à la valeur absolue :
|𝑥𝑘+1 − 𝑥𝑘 | < 𝜖
Ecole Nationale Polytechnique de Constantine Pr. K. KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------
Cas particulier :
Dans le cas où les 3 points sont équi-distants :
3𝑓 (𝑥0 ) − 4𝑓 (𝑥1 ) + 𝑓(𝑥2 )
𝑥3 = 𝑥0 + ℎ
2(−𝑓 (𝑥0 ) + 2𝑓 (𝑥1 ) + 𝑓 (𝑥2 ))
La règle pour trouver les 3 points est la suivante :
Si 𝑥0 < 𝑥3 < 𝑥1
On prend {𝑥0 , 𝑥3 , 𝑥1 } ou {𝑥3 , 𝑥1 , 𝑥2 }, et les nouveaux points dépendent à ce que
𝑓(𝑥3 ) < 𝑓(𝑥1 ) ou 𝑓(𝑥3 ) > 𝑓 (𝑥1 )
Si 𝑥1 < 𝑥3 < 𝑥2
On prend {𝑥0 , 𝑥1 , 𝑥3 } ou {𝑥1 , 𝑥3 , 𝑥2 }, et les nouveaux points dépendent à ce que
𝑓(𝑥3 ) < 𝑓(𝑥1 ) ou non.
II.2.4.2. Méthode d’approximation cubique
C’est le même principe que l’approximation quadratique, seulement la fonction objectif sera
approximée à un polynôme du 3 ème degré :
𝑃3 (𝑥 ) = 𝑎1 𝑥 3 + 𝑎2 𝑥 2 + 𝑎3 𝑥 + 𝑎4
Il faut donc 4 points pour calculer les coefficients :
𝑥13 𝑥12 𝑥1 1 𝑓(𝑥1 ) 𝑎1
𝑥23 𝑥22 𝑥2 1 𝑓 (𝑥 2 ) 𝑎2
𝑋= 3 , 𝐹𝑇 = ,𝐴= [𝑎 ]
𝑥3 𝑥32 𝑥3 1 𝑓 (𝑥 3 ) 3
[𝑥43 𝑥42 𝑥4 1] [ 𝑓 (𝑥 4 )] 𝑎4
𝐹 = 𝑋. 𝐴
Et l’optimum de 𝑓(𝑥 ) est obtenu en mettant 𝑓 ′ (𝑥 ) = 0
𝑑𝑓(𝑥)
= 0 ⇒ 3𝑎1 𝑥 2 + 2𝑎2 𝑥 + 𝑎3 = 0
𝑑𝑥
∗
−2𝑎1 ± √4𝑎12 − 12𝑎1 𝑎3
⇒ 𝑥𝑜𝑝𝑡 =
6𝑎1
Ecole Nationale Polytechnique de Constantine Pr. K. KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------
Après la prédiction du point optimum 𝑥𝑜𝑝𝑡 ∗ , il sera utilisé comme le nouveau point dans la
prochaine itération, et le point qui donne la plus grande valeur de la fonction sera écarté (toujours
dans le cas de la minimisation).
Cas particulier
Si (𝑥1 , 𝑓 (𝑥1 ), 𝑓 ′ (𝑥1 )) et (𝑥2 , 𝑓 (𝑥2 ), 𝑓 ′ (𝑥2 )) sont donnés, l’optimum sera :
∗
𝑓 ′ (𝑥 2 ) + 𝑤 − 𝑧
𝑥𝑜𝑝𝑡 = 𝑥2 − [ ] (𝑥2 − 𝑥1 )
𝑓(𝑥2 ) − 𝑓 ′ (𝑥1 ) + 2𝑤
Où :
3(𝑓 (𝑥1 ) − 𝑓(𝑥2 )
𝑧=
(𝑥2 − 𝑥1 ) + 𝑓 ′ (𝑥1 ) + 𝑓 ′ (𝑥2 )
𝑤 = √𝑧 2 − 𝑓 ′ (𝑥1 ). 𝑓 (𝑥2 )
Ecole Nationale Polytechnique de Constantine Pr. K. KAABECHE-DJERAFI
5ème année Génie des procédés
Cours : Optimisation
-------------------------------------------------------------------------------------------------------------------------------