BFGS

Un article de Wikipédia, l'encyclopédie libre.

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 dérivée de la descente de gradient.

L'idée principale de cette méthode est d'éviter de construire explicitement la Hessienne et de construire à la place une approximation 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 permet l'application de la Méthode de 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.

[modifier] Base

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

$B_k \mathbf{p}_k = - \nabla f(\mathbf{x}_k)$ .

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

Plutôt que d'imposer que la matrice Hessienne au point $\mathbf{x}_{k+1}$ doit être calculée $B k + 1$ , la hessienne approchée à l'itération k est mise à jour en ajoutant les 2 matrices.

B k + 1 = B k + U k + V k

$U k$ et $V k$ sont des matrices de rang 1 mais ont des bases différentes. L'hypothèse d'avoir un rang 1 signifie:

$C=\mathbf{a}\mathbf{b}^T$

De manière équivalente, $U k$ et $V k$ produisent une matrice de rang 1 qui est robuste vis à vis des problème d'échelle, fréquent dans les méthodes de descente de gradient.

(Comme dans la méthode de Broyden, l'analogue multidimensionel de la méthode de la sécante). Les conditions imposées pour la mise à jour sont:

$B_{k+1} (\mathbf{x}_{k+1}-\mathbf{x}_k ) = - \left( \nabla f(\mathbf{x}_{k+1}) -\nabla f(\mathbf{x}_k ) \right )$ .

[modifier] Algorithme

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

Trouver $\mathbf{s}_k$ en résolvant: $B_k \mathbf{s}_k = -\nabla f(\mathbf{x}_k)$ .
Effectuer une recherche linéaire pour trouver le pas optimal $α 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{s}_k$ .
$\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)$ .
$B_{k+1} = B_k + (\mathbf{y}_k \mathbf{y}_k^{\top}) / (\mathbf{y}_k^{\top} \mathbf{s}_k) - (B_k \mathbf{s}_k \mathbf{s}_k^{\top} B_k) / (\mathbf{s}_k^{\top} B_k \mathbf{s}_k)$ .

$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, $B 0$ peut être initialisé avec $B 0 = I$ , et la première itération sera alors équivalente à la méthode de descente du gradient, mais les autres itérations le raffineront de plus en plus grâce à $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.

[modifier] Bibliographie

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