Innere-Punkte-Verfahren mit Redundanzerkennung für die Quadratische Optimierung (eBook)

Philipp Schade (Autor)

eBook Download: PDF

2009 | 2008
XIII, 217 Seiten
Betriebswirtschaftlicher Verlag Gabler
978-3-8349-8130-1 (ISBN)

Infos

Philipp Schade stellt Kriterien für quadratische Optimierungsprobleme vor, die es erlauben, überflüssige Nebenbedingungen frühzeitig zu identifizieren. Er integriert diese Kriterien in die derzeit führende Klasse von Lösungsverfahren zur quadratischen Optimierung und stellt ein modifiziertes Innere-Punkte-Verfahren vor.

Dr. Philipp Schade ist wissenschaftlicher Mitarbeiter von Prof. Dr. Peter Recht am Fachgebiet Operations Research und Wirtschaftsinformatik der Technischen Universität Dortmund.

Inhalt

Vorwort 6
Inhaltsverzeichnis 8
Abbildungsverzeichnis 11
Tabellenverzeichnis 12
1 Einführung 13
1.1 Zielstellung dieser Arbeit 19
1.2 Aufbau der Arbeit 22
1.3 Verwendete Notation 23
2 Innere-Punkte-Verfahren für die Quadratische Optimierung 26
2.1 Quadratische Optimierung 27
2.2 Überblick und Klassifizierung von Innere- Punkte- Verfahren 33
2.3 Primal-duale Innere-Punkte-Verfahren und der Zentrale Pfad 41
2.4 Das Innere-Punkte-Verfahren nach Mehrotra/ Gondzio 54
3 Über die Identifikation nicht-aktiver Restriktionen 63
3.1 Historischer Überblick zur Redundanzerkennung 64
3.2 Kriterien zur Identifikation nicht-aktiver Restriktionen für die quadratische Optimierung 72
4 Über die Elimination überflüssiger Nebenbedingungen 79
4.1 Logarithmische Barriere-Funktion und Pfadverfolgungsverfahren 79
4.2 Abstandsmaße zum zentralen Pfad 90
4.3 Vorschläge für ein Verfahren zur Elimination nicht- aktiver Restriktionen 112
4.4 Algorithmus für ein modifiziertes primal- duales Innere- Punkte- Verfahren ( MPCE) 136
4.5 Ein simultanes Build-Down-Schema zur Redundanzerkennung 138
5 Implementierung eines modifizierten Innere- Punkte- Verfahrens 142
5.1 Quadratische Problemformulierung für die Implementierung 143
5.2 Ein spezialisierter, kombinierter Programmcode für die Quadratische Optimierung – qipp 160
5.3 Identifikation und Elimination nicht-aktiver Restriktionen 167
5.4 Arbeiten mit dem Solver 173
6 Numerische Ergebnisse und rechentechnischer Vergleich 179
6.1 Problemgenerator für Beispielinstanzen 179
6.2 Ergebnisse für generierte Beispiele 180
6.3 Beispiele der Sammlung von Maros/M´esz´aros 186
7 Zusammenfassung und Ausblick 190
Kritische Einschätzung der Arbeit 191
Weiterführende Forschung 193
A Mathematischer Anhang 196
A.1 Herleitung des erweiterten KKT-Systems 196
A.2 Berechnung der Dualitätslücke 204
A.3 Berechnung des Abstands zum zentralen Pfad 205
B Ergänzungen 207
B.1 Terminierungscodes für qipp 207
Stichwortverzeichnis 208
Literaturverzeichnis 211

Produkt-Details

• Erscheint lt. Verlag: 24.4.2009
• Zusatzinfo: XIII, 217 S.
• Verlagsort: Wiesbaden
• Sprache: deutsch
• Themenwelt: Wirtschaft ► Allgemeines / Lexika
• Schlagworte: Innere-Punkte-Verfahren • Lösungsverfahren • Nebenbedinungen • Optimierung • Optimierungsproblem • Optimierungsprobleme • Zentraler Pfad
• ISBN-10: 3-8349-8130-3 / 3834981303
• ISBN-13: 978-3-8349-8130-1 / 9783834981301