Ce document décrit plusieurs méthodes d'optimisation sans contrainte, notamment les méthodes de descente, de Newton, de la métrique variable, et du gradient conjugué.
0 évaluation0% ont trouvé ce document utile (0 vote)
98 vues2 pages
Ce document décrit plusieurs méthodes d'optimisation sans contrainte, notamment les méthodes de descente, de Newton, de la métrique variable, et du gradient conjugué.
Ce document décrit plusieurs méthodes d'optimisation sans contrainte, notamment les méthodes de descente, de Newton, de la métrique variable, et du gradient conjugué.
Ce document décrit plusieurs méthodes d'optimisation sans contrainte, notamment les méthodes de descente, de Newton, de la métrique variable, et du gradient conjugué.
Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format docx, pdf ou txt
Vous êtes sur la page 1/ 2
Introduction
L’optimisation est une branche mathématique qui a une grande importance dans la modélisation et la résolution des problèmes rencontrés essentiellement dans le domaine de l’ingénierie industrielle et qui consistent à minimiser ou maximiser une fonction sur un ensemble.
Pour atteindre des solutions optimales à ces problèmes, on recourt à différentes méthodes tout en identifiant d’abord si l’optimisation est sous ou sans contrainte.
Nous intéressons au problème d’optimisation sans contrainte et pour la résolution de ce
problème, on peut baser sur différentes méthodes :
1- Méthodes de descente : Elles sont itératives. Pour passer de uk à uk+1, on se donne une direction de descente dk et on minimise f le long de cette direction, c’est-à -dire que l’on cherche ρk tel que f(uk + ρkdk) = inf f(uk + ρdk) ρ∈R . A défaut d’un tel ρk on peut se contenter d’avoir f(uk + ρkdk) < f(uk).
1.1-La méthode de la relaxation
Le principe de cette méthode est de descendre de façon cyclique le long de chacun des axes de coordonnées. La convergence est assurée si f est elliptique.
1.2-La méthode de la plus profonde descente (méthode du gradient)
Elle consiste à faire partir de u0 quelconque. Connaissant uk, on calcule ∇fuk et uk+1 = uk − ρk∇fuk avec ρk solution de f(uk − ρk∇fuk ) = inf ρ (uk − ρ∇fuk ). En principe on trouve ρk > 0.
2 -Méthode de Newton : Dans cette méthode si on a une fonction f régulière dont on sait calculer le gradient et la matrice hessienne, on peut tirer parti du fait qu’en un point uk, f est localement voisine de son développement de Taylor quadratique, c’est-`a-dire que
1 t 2 f(uk + d) ≈ f(uk) + dt .∇fuk + d .∇ fuk .d 2
Ainsi, si ∇2fuk est définie positive, l’approximation quadratique va voir un minimum qui vérifie
∇2 fuk dk = −∇fuk
Donc on peut déterminer la direction de descente dk et de définir l’itération par uk+1 = uk + dk
On démontre, comme pour la méthode de Newton pour la résolution des équations ϕ(x) = 0, que si le point de départ u0 est assez voisin de x∗ , et si ∇2f est définie positive, alors la méthode converge vers x∗ , et ceci de façon quadratique.
Si ∇2f n’est pas d´définie positive, cette méthode supporte certains aménagements (méthode de Newton modifiée).
Quand le calcul de ∇2f ne peut être fait, on peut aussi remplacer ∇2fuk dans l’approximation de Taylor par une matrice Hk qui se calcule itérativement (méthode de quasi Newton)
3- Méthode de la métrique variable :
1 - On peut observer que si f(x) = ||x||2−(b, x) la méthode de la plus profonde descente 2 converge en une seule itération.
1 - De la même façon , si f est la fonctionnelle quadratique f(x) = (Ax, x)− (b, x) ; à la 2 condition de remplacer la métrique ||x||2par |||x||∨¿2= ((x, x)) = (Ax, x).
- L’idée de la métrique variable, appliquée à une fonctionnelle non nécessairement
quadratique, consiste lors de chaque itération de la plus profonde descente `a choisir une métrique définie par la matrice hessienne de la fonctionnelle, permettant une accélération de la convergence. Mais il y a un prix à payer. Le calcul du gradient nécessite la connaissance d’une base orthogonale ; on peut l’obtenir par exemple par orthogonalisation de Grahm- Schmidt.
4- Méthode du gradient conjugué :
Cette méthode présente, sur la méthode de Newton, l’avantage de ne pas nécessiter le calcul de ∇2f, et sur la méthode de la plus profonde descente, celui de définir des directions de descente successives cohérentes et elle reprend l’idée de la métrique variable.
