Theorem - Newton-Verfahren konvergiert für L-glatte und stark-konvexe Funktionen quadratisch

• Involvierte Definitionen:
  • Newton-Verfahren für Minimierungsprobleme und Backtracking
  • L-glatt
  • mu-stark konvexe Funktion
  • Hessematrix
  • Lipschitz-stetig
  • Globales Minimum einer Funktion
  • Totale Differenzierbarkeit
• Veranstaltung: MatheDS
• Referenz: @riedel2023 (Theorem 3.3.18)

⠀

Theorem: Newton-Verfahren konvergiert für L-glatte und -stark-konvexe Funktionen quadratisch

Sei zweimal total differenzierbar.
Sei außerdem -glatt und -stark Konvex.
Sei zudem Lipschitz-stetig.
Sei ein globales Minimum von .

Sei die durch das Newton-Verfahren definierte Folge mit

• beliebigem Startpunkt und
• Schrittweiten anhand der Backtracking-Methode.

Dann gilt:

Das heißt: es existiert eine Iteration , ab gilt, dass quadratisch gegen konvergiert.