BFGS

BFGS

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 souvent implémentée comme un algorithme à directions de descente.

L'idée principale de cette méthode est d'éviter de construire explicitement la 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 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.

Sommaire

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 de calculer B_{k+1}~ comme la matrice Hessienne au point \mathbf{x}_{k+1}~, la hessienne approchée à l'itération k est mise à jour en ajoutant deux matrices.

B_{k+1}=B_k+U_k+V_k~

Uk et Vk 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 c.a.aT, où a est une matrice colonne et c un scalaire.

De manière équivalente, U_k~ et 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 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 ).

Algorithme

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

  1. Trouver \mathbf{s}_k en résolvant: B_k \mathbf{s}_k = -\nabla f(\mathbf{x}_k).
  2. 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.
  3. \mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k).
  4. B_{k+1} = B_k + (\mathbf{s}_k \mathbf{s}_k^{\top}) / (\mathbf{s}_k^{\top} \mathbf{y}_k) - (B_k \mathbf{y}_k \mathbf{y}_k^{\top} B_k) / (\mathbf{y}_k^{\top} B_k \mathbf{y}_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 à celle de l'algorithme 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.

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.

Voir aussi

Références


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article BFGS de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • BFGS method — In mathematics, the Broyden Fletcher Goldfarb Shanno (BFGS) method is a method to solve an unconstrained nonlinear optimization problem. The BFGS method is derived from the Newton s method in optimization, a class of hill climbing optimization… …   Wikipedia

  • BFGS — Broyden Fletcher Goldfarb Shanno [algorithm] …   Medical dictionary

  • BFGS — • Broyden Fletcher Goldfarb Shanno [algorithm] …   Dictionary of medical acronyms & abbreviations

  • L-BFGS — and L BFGS B are software packages for solving nonlinear optimization problems. They are designed for large scale applications in which the Hessian matrix is not available or is expensive to compute. To accelerate convergence, the two codes… …   Wikipedia

  • L-BFGS — y L BFGS B son dos métodos de optimización quasi Newton de funciones con un gran número de parámetros o de una gran complejidad. Se trata de un método que hace un uso limitado de la memoria (usa mucha menos memoria que otros algoritmos para el… …   Wikipedia Español

  • Méthode du gradient conjugué — En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d équations linéaires dont la matrice est définie positive (et par conséquent symétrique). Cette méthode, imaginée en 1950 simultanément par… …   Wikipédia en Français

  • Davidon–Fletcher–Powell formula — The Davidon–Fletcher–Powell formula (or DFP; named after William C. Davidon, Roger Fletcher, and Michael J. D. Powell) finds the solution to the secant equation that is closest to the current estimate and satisfies the curvature condition (see… …   Wikipedia

  • Nonlinear conjugate gradient method — In numerical optimization, the nonlinear conjugate gradient method generalizes the conjugate gradient method to nonlinear optimization. For a quadratic function : The minimum of f is obtained when the gradient is 0: . Whereas linear conjugate… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Gauss–Newton algorithm — The Gauss–Newton algorithm is a method used to solve non linear least squares problems. It can be seen as a modification of Newton s method for finding a minimum of a function. Unlike Newton s method, the Gauss–Newton algorithm can only be used… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”