Méthode de Broyden-Fletcher-Goldfarb-Shanno
En mathématiques, la méthode de Broyden-Fletcher-Goldfarb-Shanno (BFGS) est une méthode permettant de résoudre un problème d'optimisation non linéaire sans contraintes.
La méthode BFGS est une solution souvent utilisée lorsque l'on veut un algorithme à directions de descente.
L'idée principale de cette méthode est d'éviter de construire explicitement la matrice hessienne et de construire à la place une approximation de l'inverse de la dérivée seconde de la fonction à minimiser, en analysant les différents gradients successifs. Cette approximation des dérivées de la fonction conduit à une méthode quasi-Newton (une variante de la méthode de Newton) de manière à trouver le minimum dans l'espace des paramètres.
La matrice hessienne n'a pas besoin d'être recalculée à chaque itération de l'algorithme. Cependant, la méthode suppose que la fonction peut être approchée localement par un développement limité quadratique autour de l'optimum.
Base
[modifier | modifier le code]Le but est de minimiser , avec et une fonction différentiable à valeurs réelles.
La recherche de la direction de descente à l'étape est donnée par la solution de l'équation suivante, équivalente à l'équation de Newton :
où est une approximation de la matrice Hessienne à l'étape , et est le gradient de évalué en .
Une recherche linéaire dans la direction est alors utilisée pour trouver le prochain point .
Plutôt que d'imposer de calculer comme la matrice Hessienne au point , la hessienne approchée à l'itération est mise à jour en ajoutant deux matrices :
où et sont des matrices symétriques de rang 1 mais ont des bases différentes. Une matrice est symétrique de rang 1 si et seulement si elle peut s'écrire sous la forme , où est une matrice colonne et un scalaire.
De manière équivalente, et produisent une matrice de mise à jour de rang 2 qui est robuste vis-à-vis des problèmes d'échelle qui pénalisent souvent les méthodes de gradient (comme la méthode de Broyden, l'analogue multidimensionnel de la méthode de la sécante). Les conditions imposées pour la mise à jour sont :
- .
Algorithme
[modifier | modifier le code]À partir d'une valeur initiale et une matrice Hessienne approchée les itérations suivantes sont répétées jusqu'à ce que converge vers la solution.
- Trouver en résolvant : .
- Effectuer une recherche linéaire pour trouver le pas optimal dans la direction trouvée dans la première partie, et ensuite mettre à jour .
- .
- .
La fonction est la fonction à minimiser. La convergence peut être testée en calculant la norme du gradient, . En pratique, peut être initialisé avec , et la première itération sera alors équivalente à celle de l'algorithme du gradient, mais les autres itérations le raffineront de plus en plus grâce à , l'approximation de la hessienne.
On peut calculer l'intervalle de confiance de la solution à partir de l'inverse de la matrice hessienne finale.
Bibliographie
[modifier | modifier le code]- C. G. Broyden, « The Convergence of a Class of Double-rank Minimization Algorithms », Journal of the Institute of Mathematics and Its Applications, vol. 6, , p. 76-90.
- R. Fletcher, « A New Approach to Variable Metric Algorithms », Computer Journal, vol. 13, , p. 317-322.
- D. Goldfarb, « A Family of Variable Metric Updates Derived by Variational Means », Mathematics of Computation, vol. 24, , p. 23-26.
- D. F. Shanno, « Conditioning of Quasi-Newton Methods for Function Minimization », Mathematics of Computation, vol. 24, , p. 647-656.
- Mordecai Avriel, Nonlinear Programming : Analysis and Methods, Dover Publishing, , 512 p. (ISBN 0-486-43227-0, lire en ligne).
Voir aussi
[modifier | modifier le code]Références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « BFGS method » (voir la liste des auteurs).
