Definition - Newton-Verfahren für Minimierungsprobleme

• Generalisierungen:
  • Folge
• Eigenschaften:
  • Newton-Verfahren konvergiert für L-glatte und stark-konvexe Funktionen quadratisch
• Involvierte Definitionen:
  • Partielle Differenzierbarkeit
  • Gradient
  • Hessematrix
  • Globales Minimum einer Funktion
  • siehe auch Gradientenabstiegsverfahren
• Veranstaltung: MatheDS
• Referenz: @riedel2023 (Gleichung 3.14, S. 77 f.)

⠀

Tipp: Ziel des Newton-Verfahrens für Minimierungsprobleme

Sei eine partiell differenzierbare Funktion.

Ziel des Newton-Verfahrens ist es, eine globale Minimalstelle zu bestimmen, also

Definition: Newton-Verfahren für Minimierungsprobleme

Sei eine zweimal partiell differenzierbare Funktion.

Als Newton-Verfahren (für Minimierungsprobleme) definieren wir das folgende Verfahren zur Iteration in Richtung des jeweils steilsten Abstiegs von :

wobei

• der Startpunkt fest gewählt ist und
• die Folge mit beschreibt die Schrittweite des Verfahrens zur -ten Iteration. Die Folge wird oft mithilfe eines Backtrackings bestimmt.

Definition: Backtracking für die Folge der Schrittweiten

Sei eine zweimal partiell differenzierbare Funktion.
Seien und feste Parameter.
Sei der Newton-Schritt.

Als Backtracking zur Bestimmung der Schrittweite im Newton-Verfahren definieren wir das folgende Vorgehen:

Sei zunächst .

Wir iterieren nun: falls die folgende Gleichung gilt, so setze

Das erste , für das die Gleichung nicht mehr gilt, ist dann die Schrittweite im -ten Schritt.

Anmerkung

Newton-Verfahren in

Ist so gilt äquivalent:

Nachteile des Newton-Verfahrens und Ausblick

Das Newton-Verfahren konvergiert zwar lokal quadratischen (also wenn schon nah bei liegt), während das Gradientenabstiegsverfahren nur linear konvergiert.

Allerdings ist das Newton-Verfahren auch deutlich aufwändiger, da in jedem Iterationsschritt die Matrix invertiert (Aufwand von ) und ein passendes bestimmt werden muss.

In vielen Anwendungen ist das Gradientenverfahren daher dennoch effizienter.

Es existieren jedoch auch Erweiterungen des Newton-Verfahrens, die bspw. die Hessematrix nicht exakt berechnen, sondern ebenfalls approximieren oder es mit dem Gradientenverfahren kombinieren.

Herleitung

Die Herleitung funktioniert ähnlich wie die Herleitung des Gradientenabstiegsverfahrens.