quasiNewtonVerfahren

Quasi-Newton-Verfahren sind eine Klasse von Iterationsmethoden zur Minimierung differenzierbarer Funktionen. Sie verbessern Newtons Methode, indem sie eine Näherung der Hessian-Matrix oder ihrer Inversen verwenden, die im Verlauf der Optimierung aus Gradientenunterschieden rekonstruiert wird. Dadurch benötigen sie im Allgemeinen nur Gradientenberechnungen und keine explizite Berechnung der zweiten Ableitungen.

Das zentrale Prinzip besteht darin, die Aktualisierung der Hesse-Matrix so zu gestalten, dass der Secant-Zusammenhang Y_k = grad f(x_{k+1}) − grad f(x_k) und der Schritt s_k = x_{k+1} − x_k erfüllt sind. Die häufigsten Aktualisierungen sind rank-two-Updates, die die bisherige Matrix so anpassen, dass sie die beobachtete Änderung des Gradienten reflektiert. Typischerweise wird die Instanz der Inversen-Hessianen-Matrix H_k verwendet, um den Suchrichtungsvektor p_k = −H_k grad f(x_k) zu berechnen und anschließend eine Schrittweite durch eine Linien-Suche zu bestimmen. Ein wichtiger Aspekt ist die Bedingung y_k^T s_k > 0, die unter Verwendung von Linien-Suche und Dämpfung sicherstellt, dass die Aktualisierung die positive Definitheit erhält und die Konvergenz fördert.

Zu den bekanntesten Vertretern gehören das DFP-Verfahren und das Broyden–Fletcher–Goldfarb–Shanno-Verfahren (BFGS). Letzteres ist heute das am verbreitetsten eingesetzte Quasi-Newton-Verfahren, da es robust ist und die Positive-Definitheit unter der Kurvaturbedingung gewährleistet. Es gibt auch speichereffiziente Varianten wie L-BFGS, das die Matrix durch wenige Vektorpaare ersetzt, was es für großdimensionale Probleme geeignet macht.

Anwendung finden Quasi-Newton-Verfahren vor allem in der unbeschränkten Optimierung, oft mit Linien-Suche oder Trust-Region-Techniken, sowie in numerischen Bibliotheken für maschinelles Lernen und wissenschaftliche Berechnungen. Ihre Erwartung ist eine schnelle, meist superlinear konvergierende Lösung mit moderatem Rechenaufwand pro Iteration.