Liniensuchverfahren

Unter den Liniensuchverfahren (englisch: line search algorithms) versteht man in der Optimierung eine Reihe von iterativen Verfahren, um das lokale Minimum einer Funktion $f:\mathbb {R} ^{n}\to \mathbb {R}$ zu finden. Die grundlegende Idee ist es, die Funktion in jedem Schritt entlang einer bestimmten Richtung zu minimieren. Beispiele für Algorithmen, die dem Liniensuchverfahren zugeordnet werden können, sind das Gradientenverfahren (Verfahren des steilsten Abstiegs) und das Newton-Verfahren.

Beschreibung

Allen Liniensuchverfahren gemein ist die folgende grundlegende Vorgehensweise, um aus einem bestehenden Zwischenergebnis $x^{(k)}$ ein neues Zwischenergebnis $x^{(k+1)}$ zu berechnen:

1. Bestimme eine Suchrichtung in Form eines Vektors $s^{(k)}\in \mathbb {R} ^{n}$ .
2. Minimiere die eindimensionale Hilfsfunktion $F(\alpha )=f{\bigl (}x^{(k)}+\alpha s^{(k)}{\bigr )}$ mit Bezug auf $\alpha \in \mathbb {R}$.
3. Berechne die neue Lösung $x^{(k+1)}:=x^{(k)}+\alpha ^{(k)}s^{(k)}$, wobei $\alpha ^{(k)}$ die gefundene Schrittweite aus Schritt 2 ist.

Das Minimum der Hilfsfunktion aus Schritt 2 wird in der Regel nicht exakt bestimmt. Falls doch, spricht man von einem exakten Liniensuchverfahren.