DescentVerfahren

DescentVerfahren bezeichnet eine Klasse von Optimierungsverfahren, die darauf abzielen, eine gegebene Ziel-Funktion f: R^n -> R zu minimieren, indem wiederholt neue Suchpunkte x_{k+1} aus dem aktuellen Punkt x_k durch Verschiebung in eine Abwärtsrichtung bilden. Ein Descent-Verfahren wählt eine Descent-Richtung d_k mit der Eigenschaft, dass f(x_k + t d_k) für t > 0 ausreichend klein wird; typischerweise wird die Richtung so gewählt, dass f(x_k + α d_k) mit geeigneter Schrittweite α minimiert oder reduziert wird, etwa durch eine Backtracking-Line-Search oder durch Erfüllung der Armijo-Wolfe-Bedingungen.

Die einfachste Wahl einer Descent-Richtung ist die negative Gradientenrichtung d_k = -∇f(x_k) (Steilste Abstieg). Bei weiterer Information kann man Newton- oder Quasi-Newton-Verfahren einsetzen, z. B. d_k = -H_k^{-1} ∇f(x_k), wobei H_k die (approximierte) Hessianmatrix ist, oder konjugierte Richtungen in CG-Verfahren für große quadratische Probleme. Es existieren auch koordinierten Descent-Verfahren, bei denen nacheinander einzelne Koordinaten minimiert werden.

Die Schrittweite α_k wird oft durch Backtracking-Line-Search bestimmt, um sicherzustellen, dass f(x_k + α_k d_k) < f(x_k) und dass α_k nicht zu groß wird; alternativ kommen Vertrauen-Verfahren (trust-region) zum Einsatz. Konvergenz: Unter milden Annahmen (f differenzierbar, Lipschitz-Bunktion der Gradient) konvergieren Descent-Verfahren gegen eine stationäre Stelle; bei stark konvexen Funktionen ist oft lineare Konvergenz zu beobachten, bei quadratischen Problemen können CG- oder Newton-Verfahren in konstanter oder quadratischer Rate arbeiten.

Anwendungsgebiete umfassen maschinelles Lernen, Signalverarbeitung und Operations Research. Descent-Verfahren zeichnen sich durch einfache Implementierung, geringe Speicheranforderungen und ihre Eignung für große, spärliche oder nichtlineare Probleme aus.