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

Le but est de minimiser ${\displaystyle f(\mathbf {x} )}$, avec ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ et ${\displaystyle f}$ une fonction différentiable à valeurs réelles.

La recherche de la direction de descente ${\displaystyle \mathrm {p} _{k}}$ à l'étape ${\displaystyle k}$ est donnée par la solution de l'équation suivante, équivalente à l'équation de Newton :

${\displaystyle \mathrm {B} _{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$

où ${\displaystyle B_{k}}$ est une approximation de la matrice Hessienne à l'étape ${\displaystyle k}$, et ${\displaystyle \nabla f(\mathbf {x} _{k})}$ est le gradient de ${\displaystyle f}$ évalué en ${\displaystyle \mathrm {x} _{k}}$.

Une recherche linéaire dans la direction ${\displaystyle \mathrm {p} _{k}}$ est alors utilisée pour trouver le prochain point ${\displaystyle \mathrm {x} _{k+1}}$.

Plutôt que d'imposer de calculer ${\displaystyle B_{k+1}~}$ comme la matrice Hessienne au point ${\displaystyle \mathrm {x} _{k+1}}$, la hessienne approchée à l'itération ${\displaystyle k}$ est mise à jour en ajoutant deux matrices :

${\displaystyle \mathrm {B} _{k+1}=\mathrm {B} _{k}+\mathrm {U} _{k}+\mathrm {V} _{k}}$

où ${\displaystyle \mathrm {U} _{k}}$ et ${\displaystyle \mathrm {V} _{k}}$ 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 ${\displaystyle cAA^{T}}$, où ${\displaystyle A}$ est une matrice colonne et ${\displaystyle c}$ un scalaire.

De manière équivalente, ${\displaystyle \mathrm {U} _{k}}$ et ${\displaystyle \mathrm {V} _{k}}$ 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 (en), l'analogue multidimensionnel de la méthode de la sécante). Les conditions imposées pour la mise à jour sont :

${\displaystyle \mathrm {B} _{k+1}(\mathbf {x} _{k+1}-\mathbf {x} _{k})=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$.

Algorithme

À partir d'une valeur initiale ${\displaystyle {\textbf {x}}_{0}}$ et une matrice Hessienne approchée ${\displaystyle \mathrm {B} _{0}}$ les itérations suivantes sont répétées jusqu'à ce que ${\displaystyle {\textbf {x}}}$ converge vers la solution.

1. Trouver ${\displaystyle \mathbf {p} _{k}}$ en résolvant : ${\displaystyle \mathrm {B} _{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$.
2. Effectuer une recherche linéaire pour trouver le pas optimal ${\displaystyle \alpha _{k}}$ dans la direction trouvée dans la première partie, et ensuite mettre à jour ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}=\mathbf {x} _{k}+\mathbf {s} _{k}}$.
3. ${\displaystyle \mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$.
4. ${\displaystyle \mathrm {B} _{k+1}=\mathrm {B} _{k}+(\mathbf {y} _{k}\mathbf {y} _{k}^{\top })/(\mathbf {y} _{k}^{\top }\mathbf {s} _{k})-(\mathrm {B} _{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\top }\mathrm {B} _{k})/(\mathbf {s} _{k}^{\top }\mathrm {B} _{k}\mathbf {s} _{k})}$.

La fonction ${\displaystyle f(\mathbf {x} )}$ est la fonction à minimiser. La convergence peut être testée en calculant la norme du gradient, ${\displaystyle \left|\nabla f(\mathbf {x} _{k})\right|}$. En pratique, ${\displaystyle \mathrm {B} _{0}}$ peut être initialisé avec ${\displaystyle \mathrm {B} _{0}=\mathrm {I} }$, 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 à ${\displaystyle \mathrm {B} }$, 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

• C. G. Broyden, « The Convergence of a Class of Double-rank Minimization Algorithms », Journal of the Institute of Mathematics and Its Applications, vol. 6,‎ 1970, p. 76-90.
• R. Fletcher, « A New Approach to Variable Metric Algorithms », Computer Journal, vol. 13,‎ 1970, p. 317-322.
• D. Goldfarb, « A Family of Variable Metric Updates Derived by Variational Means », Mathematics of Computation, vol. 24,‎ 1970, p. 23-26.
• D. F. Shanno, « Conditioning of Quasi-Newton Methods for Function Minimization », Mathematics of Computation, vol. 24,‎ 1970, p. 647-656.
• Mordecai Avriel, Nonlinear Programming : Analysis and Methods, Dover Publishing, 2003, 512 p. (ISBN 0-486-43227-0, lire en ligne).

Voir aussi

• Méthode de Newton

Références

• (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).

v · m Optimisation mathématiques et algorithmiques
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Algorithme évolutionniste Algorithme génétique Essaims Forêts aléatoires Boosting
Liste

• Portail de l'analyse