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 $f(\mathbf {x} )$, avec $\mathbf {x} \in \mathbb {R} ^{n}$ et $f$ une fonction différentiable à valeurs réelles.

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

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

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

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

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

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

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

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

$\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 ${\textbf {x}}_{0}$ et une matrice Hessienne approchée $\mathrm {B} _{0}$ les itérations suivantes sont répétées jusqu'à ce que ${\textbf {x}}$ converge vers la solution.

1. Trouver $\mathbf {p} _{k}$ en résolvant : $\mathrm {B} _{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})$.
2. Effectuer une recherche linéaire pour trouver le pas optimal $\alpha _{k}$ dans la direction trouvée dans la première partie, et ensuite mettre à jour $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}=\mathbf {x} _{k}+\mathbf {s} _{k}$.
3. $\mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})$.
4. $\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 $f(\mathbf {x} )$ est la fonction à minimiser. La convergence peut être testée en calculant la norme du gradient, $\left|\nabla f(\mathbf {x} _{k})\right|$. En pratique, $\mathrm {B} _{0}$ peut être initialisé avec $\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 à $\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).