Newton- und Quasi-Newton-Verfahren

Die Krümmung nutzen

Das Gradientenverfahren kennt nur die Steigung. Das Newton-Verfahren nutzt auch die Krümmung: Es ersetzt $f$ nahe dem aktuellen Punkt durch die Quadrik mit gleichem Wert, Gradienten und gleicher Hesse-Matrix und springt direkt zu deren Minimum. Der Schritt ist $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$. Bei einer exakt quadratischen Funktion trifft das das Minimum in einem einzigen Schritt, egal wie die Konditionszahl ist. In der Nähe des Minimums jeder glatten Funktion ist die Konvergenz quadratisch: Der Fehler wird pro Schritt etwa quadriert, die Zahl korrekter Stellen verdoppelt sich also ungefähr.

Das Newton-Verfahren hat einen Preis. Bei $n$ Parametern hat die Hesse-Matrix $n^2$ Einträge, und das Lösen mit ihr kostet etwa $n^3$ Operationen, das ist bei Hunderten Parametern in Ordnung und bei Millionen unmöglich. Weit vom Minimum entfernt oder wo $H$ nicht positiv definit ist, kann der Newton-Schritt sogar bergauf zeigen, deshalb dämpfen praktische Varianten ihn mit einer Liniensuche. Quasi-Newton-Verfahren behalten den Großteil der Geschwindigkeit ohne die Kosten. BFGS baut aus den beobachteten Änderungen $\mathbf s=\mathbf w_{k+1}-\mathbf w_k$ und $\mathbf y=\mathbf g_{k+1}-\mathbf g_k$ eine Näherung der inversen Hesse-Matrix auf und erzwingt die Sekantenbedingung $B\mathbf s=\mathbf y$. Es braucht nur Gradienten, kostet $O(n^2)$ pro Schritt und konvergiert superlinear. L-BFGS speichert nur die letzten $m$ Paare, typischerweise 5 bis 20, der Speicher ist also $O(mn)$. Es ist das übliche Arbeitspferd für glatte Kalibrierungen und Maximum-Likelihood-Schätzungen, etwa die Standardoptimierer in SciPy.

• Newton: $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$; ein Schritt bei einer Quadrik, quadratische Konvergenz nahe dem Minimum.
• BFGS: lernt aus Gradientendifferenzen eine Näherung der inversen Hesse-Matrix, ohne zweite Ableitungen.
• L-BFGS: speichert nur die letzten Paare und skaliert daher auf viele Parameter.

Lab: Was bewertet wird

• Der erste Newton-Schritt15 Pkt.
• Der zweite Newton-Schritt15 Pkt.
• Ein Newton-Schritt in zwei Variablen15 Pkt.
• Schritte bei einer Quadrik15 Pkt.
• Die Sekantenbedingung15 Pkt.
• Methoden und Ideen10 Pkt.
• Warum exaktes Newton bei riesigen Problemen vermieden wird15 Pkt.