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(𝐱)$, avec $𝐱\in {ℝ}^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{𝐩}_k=-\mathrm{\nabla }f({𝐱}_k)$

où $B_k$ est une approximation de la matrice Hessienne à l'étape $k$, et $\mathrm{\nabla }f({𝐱}_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 $cA{A}^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}({𝐱}_{k+1}-{𝐱}_k)=\mathrm{\nabla }f({𝐱}_{k+1})-\mathrm{\nabla }f({𝐱}_k)$.

Algorithme

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

1. Trouver ${𝐩}_k$ en résolvant : ${\mathrm{B}}_k{𝐩}_k=-\mathrm{\nabla }f({𝐱}_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 ${𝐱}_{k+1}={𝐱}_k+{\alpha }_k{𝐩}_k={𝐱}_k+{𝐬}_k$.
3. ${𝐲}_k=\mathrm{\nabla }f({𝐱}_{k+1})-\mathrm{\nabla }f({𝐱}_k)$.
4. ${\mathrm{B}}_{k+1}={\mathrm{B}}_k+({𝐲}_k{𝐲}_k^{\mathrm{\top }})/({𝐲}_k^{\mathrm{\top }}{𝐬}_k)-({\mathrm{B}}_k{𝐬}_k{𝐬}_k^{\mathrm{\top }}{\mathrm{B}}_k)/({𝐬}_k^{\mathrm{\top }}{\mathrm{B}}_k{𝐬}_k)$.

La fonction $f(𝐱)$ est la fonction à minimiser. La convergence peut être testée en calculant la norme du gradient, $|\mathrm{\nabla }f({𝐱}_k)|$. 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

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.

Voir aussi

• Méthode de Newton