# 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.
* Trouver $\mathbf {p} _{k}$ en résolvant : $\mathrm {B} _{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})$.
* 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}$.
* $\mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})$.
* $\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.