Eine Kombination von Bundle- und Trust-Region-Verfahren zur Lösung nichtdifferenzierbarer Optimierungsprobleme

H. Schramm: Eine Kombination von Bundle- und Trust-Region-Verfahren zur Lösung nichtdifferenzierbarer Optimierungsprobleme
in: PhD thesis, viii +205 pp., Bayreuth, Germany, 1989

Smart-Link: http://bms.math.uni-bayreuth.de/all_books.html#vol_30
MR Nummer: 1001035
Zentralblattnummer: 0683.90069
Keywords: bundle method; trust-region methods; non-differentiable optimization
Mathematics Subject Classification Code: 90C30 (49A52 49D37 90C25)


Abstract:

In dieser Arbeit wird ein neues Verfahren zur Minimierung nichtdifferenzierbarer Funktionen unter linearen Nebenbedingungen vorgestellt. Die Grundlage bilden die Bundle-Idee der nichtglatten und die Trust-Region-Idee der glatten Optimierung. Von den Bundle-Verfahren wird die Bildung einer Modellfunktion und deren sukzessive Verbesserung übernommen; von den Trust-Region-Verfahren greifen wir die folgende Strategie auf: wir passen die Umgebung des aktuellen Iterationspunktes, auf der das Modell minimiert wird, an die „Güte“ des Modells an. Der resultierende „Bundle-Trust-Algorithmus“ wird zunächst für konvexe, unrestringierte Probleme untersucht; es wird die Konvergenz der Iterationspunkte gegen ein Minimum der Zielfunktion gezeigt. Die Konvergenzaussagen werden für stückweise lineare Funktionen verschärft und auf den linear restringierten Fall übertragen. Schließlich werden noch die Erweiterungen für Probleme mit konvexen Nebenbedingungen, für nichtkonvexe Zielfunktionen und die Einbeziehung der Variable-Metrik-Idee betrachtet.

Das numerische Verhalten des Algorithmus wird an verschiedenen, auch in den Anwendungen relevanten Beispielen untersucht und mit einem Bundle-Verfahren verglichen. Es werden dabei gute Resultate erzielt.

Inhaltsverzeichnis:

1. Einleitung
1.1 Einführung in die Thematik
1.2 Überblick über die Resultate
2. Bezeichnungen, Definitionen und konvexe Funktionen
2.1 Bezeichnungen
2.2 Definitionen und Eigenschaften konvexer Funktionen
3. Das Trust-Region-Konzept
3.1 Trust-Region-Methoden für glatte Funktionen
3.2 Trust-Region-Methoden für nichtglatte Funktionen
4. Bundle-Algorithmen
5. Das Bundle-Trust-Problem im nichtdifferenzierbaren Fall
5.1 Das Modell der Funktion
5.2 Das Bundle-Trust-Region-Konzept
5.3 Zur Lösung des Bundle-Trust-Problems
5.4 Eigenschaften von I(t)
5.5 Eigenschaften der Funktion d(t)
6. Der Bundle-Trust-Algorithmus (BT)
6.1 Das Abbruchkriterium
6.2 Kriterien für die Wahl des nächsten Iterationspunktes
6.3 Bestimmung von yk+1
6.4 Der BT-Algorithmus
7. Konvergenz des BT-Algorithmus
8. Endlichkeit für stückweise lineare Funktionen
9. Lineare Nebenbedingungen im konvexen Fall
9.1 Problemstellung
9.2 Optimalitätsbedingungen
9.3 Modifikationen des BT-Algorithmus
9.4 Der BT-Algorithmus für lineare Restriktionen
9.5 Konvergenz
9.6 Endlichkeit für stückweise lineare Funktionen
10. Erweiterungen des BT-Algorithmus
10.1 Ein Konzept zur Behandlung nichtlinearer Nebenbedingungen
10.2 Wahl anderer Normen
10.3 Der nichtkonvexe Fall
11. Numerische Tests
11.1 Verfahren zur Lösung unrestringierter konvexer Probleme
11.2 Akademische Testbeispiele
11.3 Einige höherdimensionale Testbeispiele
11.4 Verhalten des Algorithmus ohne Variation von t
11.5 Verhalten für stückweise lineare Funktionen
11.6 Travelling-Salesman-Probleme
11.7 Theta-Funktion
11.8 Verfahren für linear restringierte konvexe Probleme
11.9 Zusammenfassung der Ergebnisse

Chair -

|  University of Bayreuth -