BFGS-Verfahren

Das Broyden–Fletcher–Goldfarb–Shanno (BFGS) Verfahren ist ein numerisches Verfahren zur Lösung von nichtlinearen Optimierungsproblemen. Das Verfahren wurde von den Mathematikern Broyden, Fletcher, Goldfarb und Shanno im Jahre 1970 unabhängig voneinander entwickelt und in vier wissenschaftlichen Artikeln publiziert.

Beispiellauf des BFGS-Verfahrens mit der Rosenbrock-Funktion ("Bananenfunktion")

Es gehört zu der Gruppe der Quasi-Newton-Verfahren. Als solches vermeidet es die direkte Berechnung der Hesse-Matrix, indem es die Hesse-Matrix iterativ approximiert. Bei quadratischen Funktionen benötigen sowohl das Newton-Verfahren als auch Quasi-Newton-Verfahren ca. N² Funktionsaufrufe (wenn man die Ableitungen über Differenzenquotienten approximiert); dies gilt auch für das Verfahren der konjugierten Gradienten. Allerdings hat sich insbesondere das BFGS-Verfahren in der Praxis besonders bewährt (z. B. ist es relativ tolerant gegenüber Fehlern bei der Schrittweitensteuerung).

Literatur

• Charles G. Broyden: The convergence of a class of double-rank minimization algorithms. In: Journal of the Institute of Mathematics and Its Applications. Band 6, 1970, S. 76–90, doi:10.1093/imamat/6.1.76.
• Roger Fletcher: A New Approach to Variable Metric Algorithms. In: Computer Journal. Band 13, Nr. 3, 1970, S. 317–322, doi:10.1093/comjnl/13.3.317.
• Donald Goldfarb: A Family of Variable Metric Updates Derived by Variational Means. In: Mathematics of Computation. Band 24, Nr. 109, 1970, S. 23–26, doi:10.1090/S0025-5718-1970-0258249-6.
• David F. Shanno: Conditioning of quasi-Newton methods for function minimization. In: Mathematics of Computation. Band 24, Nr. 111, Juli 1970, S. 647–656, doi:10.1090/S0025-5718-1970-0274029-X.