Université des Sciences et de la Technologie Houari Boumediene
Faculté de Génie Electrique
Département d’Automatique
Module : Optimisation
Année Universitaire 2024/2025
OPTIMISATION SANS CONTRAINTES
TP 03 Méthodes de recherche Multidimensionnelle
I-Rappel sur quelque méthodes
d’optimisation :
a- Méthode du gradient à pas optimal : dans le cas quadratique :
L'algorithme de la méthode du gradient à pas optimal dans le cas quadratique est:
𝑑𝑘 = −(𝐴𝑥𝑘 + 𝑏)
𝑑𝑘𝑇 𝑑𝑘
𝜌𝑘 = 𝑇
𝑑𝑘 𝐴𝑑𝑘
{𝑥𝑘+1 = 𝑥𝑘 + 𝜌𝑘 𝑑𝑘
b- Méthode du gradient conjugué :
L'algorithme de la méthode du gradient conjugué:
- Initialement 𝑑0 = −𝛻𝑓(𝑥0 ), 𝑔0 = 𝛻𝑓 (𝑥0 ).
𝑔𝑘𝑇 𝑑𝑘
𝜌𝑘 = − 𝑇
𝑑𝑘 𝐴𝑑𝑘
𝑥𝑘+1 = 𝑥𝑘 + 𝜌𝑘 𝑑𝑘
𝑔𝑘+1 = 𝛻𝑓(𝑥𝑘+1 )
𝑇
𝑔𝑘+1 𝐴𝑑𝑘
𝛽𝑘 = 𝑇
𝑑𝑘 𝐴𝑑𝑘
{𝑑𝑘+1 = −𝑔𝑘+1 + 𝛽𝑘 𝑑𝑘
c- Méthode de Newton dans le cas quadratique
L’algorithme de la méthode de Newton s'écrit comme:
𝑥𝑘+1 = 𝑥𝑘 − 𝐻 −1 (𝑥𝑘 )𝛻𝑓(𝑥𝑘 )
On a: ∇𝑓 (𝑥𝑘 ) = 𝐴𝑥𝑘 + 𝑏, et 𝐻(𝑥𝑘 ) = 𝐴.
d- Méthode de Levenberg-Marquardt
L'algorithme de la méthode de Levenberg-Marquardt est :
𝑥𝑘+1 = 𝑥𝑘 − (𝐻(𝑥𝑘 ) + 𝜌𝐼)−1 𝛻𝑓(𝑥𝑘 )
II- Application :
Soit : 𝑓: 𝑅2 → 𝑅 définie par : 𝑓(𝑥1 , 𝑥2 ) = 2𝑥12 + 6𝑥22 − 5𝑥1 − 4𝑥2 .
1) Tracer la fonction 𝑓.
1
2) Réécrire 𝑓 sous la forme quadratique 𝑓(𝑥1 , 𝑥2 ) = 𝑥 𝑇 𝐴𝑥 + 𝑏𝑇 𝑥. Avec 𝐴
2
symétrique.
Le point initial : 𝑥0 = (0,0).
3) En utilisant le logiciel Matlab, après combien d'itérations les algorithmes
suivants convergent vers le point (𝑥1 , 𝑥2 ) = (1.2500,0.3333).
Méthode de gradient à pas fixe avec 𝜌 = 0.1.
Méthode de gradient à pas optimal.
Méthode de gradient conjugué.
Méthode de Levenberg-Marquardt avec 𝜌 = 0.1.