Liniensuchverfahren

Unter den Liniensuchverfahren (englisch: line search algorithms), auch allgemeine Abstiegsverfahren mit Richtungssuche[1] genannt, versteht man in der Optimierung eine Reihe von iterativen Verfahren, um das lokale Minimum einer Funktion $f\colon \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 den Liniensuchverfahren zugeordnet werden können, sind das Gradientenverfahren (Verfahren des steilsten Abstiegs) und das Newton-Verfahren.[2]

Beschreibung

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

Bestimme eine Suchrichtung in Form eines Vektors $s^{(k)}\in \mathbb {R} ^{n}$ .
Berechne eine Schrittweite $\alpha ^{(k)}$ durch Minimierung der eindimensionalen Hilfsfunktion $F(\alpha )=f{\bigl (}x^{(k)}+\alpha s^{(k)}{\bigr )}$ mit Bezug auf $\alpha \in \mathbb {R}$ . Dieser Schritt wird auch Liniensuche genannt.
Berechne die neue Lösung $x^{(k+1)}:=x^{(k)}+\alpha ^{(k)}s^{(k)}$

Das Minimum der Hilfsfunktion aus Schritt 2 wird in der Regel nicht exakt bestimmt. Falls doch, spricht man von einer exakten Liniensuche.[3]

Einzelnachweise

Rüdiger Reinhardt, Armin Hoffmann, Tobias Gerlach: Nichtlineare Optimierung. Springer-Verlag, Berlin Heidelberg 2013, Kap. 3.3, doi:10.1007/978-3-8274-2949-0.
Josef Kallrath: Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis. 2. Auflage. Springer Fachmedien Wiesbaden, 2013, S. 107, doi:10.1007/978-3-658-00690-7.
Markos Papageorgiou, Marion Leibold, Martin Buss: Optimierung. 4. Auflage. Springer-Verlag, Berlin Heidelberg 2015, S. 43 ff., doi:10.1007/978-3-662-46936-1.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Rüdiger Reinhardt, Armin Hoffmann, Tobias Gerlach: Nichtlineare Optimierung. Springer-Verlag, Berlin Heidelberg 2013, Kap. 3.3, doi:10.1007/978-3-8274-2949-0.

[:0-2] Josef Kallrath: Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis. 2. Auflage. Springer Fachmedien Wiesbaden, 2013, S. 107, doi:10.1007/978-3-658-00690-7.

[3] Markos Papageorgiou, Marion Leibold, Martin Buss: Optimierung. 4. Auflage. Springer-Verlag, Berlin Heidelberg 2015, S. 43 ff., doi:10.1007/978-3-662-46936-1.