Diese Arbeit beschäftigt sich mit numerischen Verfahren zur Lösung nichtlinearer Optimierungsaufgaben.
Es werden theoretische Grundlagen von mehreren Verfahren unter
den Gesichtspunkten der Korrektheit und der Effizienz ausgearbeitet und durch Beispiele und mit Matlab R2008a erzeugten Abbildungen aufgelockert.
In dem folgenden einleitenden Kapitel sind Definitionen und Sätze aus Optimierungstheorie, Linearer Algebra, Analysis und Numerik zusammengestellt und Kriterien zur Konvergenzanalyse erklärt. Da die Lösung von drei der behandelten Verfahren auf die Lösung von sogenannten unrestringierten Problemen oder eines Gleichungssystems zurückgeführt wird, wird zuerst ein Newton-artiges Verfahren vorgestellt und wünschenswerte Eigenschaften, wie globale Konvergenz, hohe Konvergenzordnung des Verfahrens, erörtert.
Im nächsten Kapitel wird das sogenannte Penalty-Verfahren anhand einer Penalty-Funktion mit einem Algorithmus für eine numerische Behandlung vorgestellt und seine Konvergenzeigenschaften anhand der im ersten Kapitel erklärten Konvergenzkriterien analysiert. Die Nachteile des in dem Kapitel vorgestellten Verfahrens werden durch eine Anwendung von sogenannten exakten Penalty-Funktionen aufgehoben, was auch kurz erläutert wird. Auf der Grundlage des Penalty-Verfahrens wird die Penalty-Lagrange-
Methode mit einer vollständigen algorithmischen Darstellung der theoretischen Herleitung vorgestellt und eine Konvergenzanalyse durchgeführt. Das sogenannte Barriere- Verfahren wird nach dem gleichen Schema vorgestellt, basierend auf der Idee und einigen im Rahmen des Barriere-Verfahrens getroffenen Aussagen wird eine Version aus der Klasse der Innere-Punkte-Verfahren erörtert. Den Schlußpunkt der Arbeit setzen numerische Fallstudien im letzten Abschnitt, wobei die Effizienz der Verfahren im Mittelpunkt der Untersuchung steht.
Inhaltsverzeichnis
Einleitung
1 Mathematische Grundlagen
1.1 Grundlagen aus der Linearen Algebra
1.2 Definitionen und Bezeichnungen der Optimierungstheorie
1.3 Optimalitätsbedingungen
1.4 Das Konvergenzverhalten iterativer Verfahren
2 Quasi-Newton-Verfahren zur Lösung von unrestringierten Optimierungsproblemen
2.1 Grundidee des Newton-Verfahrens
2.2 Idee des BFGS-Verfahrens
2.3 Algorithmus und Konvergenz
2.3.1 Lokales BFGS-Verfahren
2.3.2 Globalisiertes BFGS-Verfahren
2.4 Effizienzanalyse
3 Penalty-Verfahren anhand der quadratischen Penalty-Funktion
3.1 Idee des Verfahrens und Konstruktion von Penalty-Funktionen
3.2 Algorithmus und Konvergenz
3.3 Effizienzanalyse
4 Penalty-Lagrange-Methode
4.1 Exakte Penalty-Funktionen
4.2 Idee des Verfahrens und Konstruktion von Penalty-Lagrange-Funktionen
4.3 Algorithmus und Konvergenz
4.4 Erweiterung auf Ungleichungsrestriktionen
4.5 Effizienzanalyse
5 Barriere-Verfahren anhand der logaritmischen Barriere-Funktion
5.1 Idee des Verfahrens und Konstruktion von Barriere-Funktionen
5.2 Algorithmus und Konvergenz
5.3 Effizienzanalyse
6 Innere-Punkte-Verfahren
6.1 Grundidee der Verfahren anhand linearer Probleme
6.1.1 Grundlagen der linearen Optimierung
6.1.2 Logarithmische Barriere, zentraler Pfad
6.1.3 Anwendung des Newton-Verfahrens in Innere-Punkte-Verfahren
6.1.4 Allgemeiner Algorithmus
6.2 Pfad-Verfolgungs-Verfahren und Konvergenz
6.3 Grundzüge der primal-dualen Innere-Punkte-Verfahren für nichtlineare Probleme
6.3.1 Barriere-Problem und gestörte Optimalitätsbedingungen nichtlinearer primaler Probleme
6.4 Globalisierung des Verfahrens
6.4.1 Backtracking-Methode für unrestringierte Probleme
6.4.2 Backtracking-Schrittweitenbestimmung mit dem Filteransatz
6.4.3 Algorithmus mit Korrekturschritten
7 Numerische Fallstudie
7.1 Implementierung
7.2 Parameter
7.3 Numerische Tests
8 ANHANG
A Anhang
B Anhang
C Anhang
Zielsetzung & Themen
Diese Arbeit widmet sich der numerischen Lösung nichtlinearer Optimierungsprobleme. Das primäre Ziel ist es, die theoretischen Grundlagen ausgewählter Verfahren unter Berücksichtigung ihrer Korrektheit und Effizienz zu untersuchen, zu analysieren und mittels Softwareimplementierungen in C++ und Matlab zu veranschaulichen.
- Grundlagen der Optimierungstheorie und numerische Konvergenzanalyse.
- Untersuchung von Quasi-Newton-Verfahren (BFGS) für unrestringierte Probleme.
- Analyse von Penalty-, Penalty-Lagrange- und Barriere-Verfahren für restringierte Probleme.
- Einführung in Innere-Punkte-Verfahren und deren Globalisierung durch Filteransätze.
- Numerische Validierung der Verfahren anhand einer Fallstudie mit Testproblemen.
Auszug aus dem Buch
2.1 Grundidee des Newton-Verfahrens
Um die Idee und die Herleitung von Quasi-Newton-und Innere-Punkte-Verfahren verständlich vorstellen zu können, betrachten wir die Grundidee und grundlegende Definitionen des (lokalen) Newton-Verfahrens zur Lösung nichtlinearer Gleichungssysteme und nichtlinearer unrestringierter Optimierungsprobleme. Wir behandeln zuerst ein nichtlineares Gleichungssystem der Gestalt
F(x)=0, (2.1)
wobei F : Rn → Rn eine zumindest stetig differenzierbare Funktion ist.
Wir gehen davon aus, dass xk eine aktuelle Näherung für die Lösung x* des Gleichungssystems (2.1) ist. Wir approximieren die Funktion F lokal durch die Linearisierung
Fk(x) := F(xk) + F'(xk)(x - xk)
um die aktuelle Näherung xk und bestimmen dann die nächste Näherung xk+1 für die gesuchte Lösung x* als Nullstelle der linearisierten Funktion Fk. Dies führt auf die Vorschrift
xk+1 := xk - F'(xk)-1F(xk)
mit der Inversen der Jacobi-Matrix F'(xk)-1. Um die explizite Bestimmung der inversen Matrix zu vermeiden, bestimmt man einen Korrekturvektor Δxk durch das Lösen des Gleichungssystems
F'(xk)Δxk = -F(xk),
das als Newton-Gleichung bezeichnet wird. Die nächste Iterierte erhalten wir anschließend durch
xk+1 := xk + Δxk.
Zusammenfassung der Kapitel
1 Mathematische Grundlagen: Dieses Kapitel stellt die mathematischen Definitionen, Optimalitätsbedingungen und Kriterien zur Konvergenzanalyse bereit, die als Fundament für die gesamte Arbeit dienen.
2 Quasi-Newton-Verfahren zur Lösung von unrestringierten Optimierungsproblemen: Hier wird das Newton-Verfahren eingeführt und das BFGS-Verfahren zur effizienten Approximation der Hesse-Matrix inklusive Globalisierungsstrategien erläutert.
3 Penalty-Verfahren anhand der quadratischen Penalty-Funktion: Dieses Kapitel behandelt die Transformation von restringierten in unrestringierte Probleme durch Strafterme, wobei die Konvergenz und die Konditionsprobleme analysiert werden.
4 Penalty-Lagrange-Methode: Hier wird die Penalty-Lagrange-Funktion eingeführt, um die schlechte Kondition klassischer Penalty-Methoden durch Einbeziehung dualer Variablen zu vermeiden.
5 Barriere-Verfahren anhand der logaritmischen Barriere-Funktion: Dieses Kapitel diskutiert Verfahren, die durch Barriere-Terme sicherstellen, dass Iterierten innerhalb des zulässigen Bereichs verbleiben.
6 Innere-Punkte-Verfahren: Dieser zentrale Teil erläutert die Theorie der primal-dualen Innere-Punkte-Methoden, die mittels einer Barriere-Iteration und Newton-Schritten globale Konvergenz erreichen.
7 Numerische Fallstudie: Hier erfolgt die praktische Evaluierung der behandelten Verfahren anhand einer Testdatenbank, wobei Effizienz und Genauigkeit gegenübergestellt werden.
8 ANHANG: Dieser Abschnitt enthält detaillierte Tabellen zu Testläufen sowie weiterführende Informationen zur Implementierung in C++.
Schlüsselwörter
Nichtlineare Optimierung, Numerische Mathematik, Newton-Verfahren, BFGS-Verfahren, Penalty-Funktion, Barriere-Verfahren, Innere-Punkte-Verfahren, Primal-duale Methoden, Konvergenzanalyse, Optimierungsalgorithmen, Globalisierung, Filteransatz, KKT-Bedingungen, numerische Fallstudie, Funktionsminimierung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Theorie und Numerik von Verfahren zur Lösung nichtlinearer Optimierungsprobleme, wobei sowohl unrestringierte als auch restringierte Ansätze analysiert werden.
Welche zentralen Themenfelder werden bearbeitet?
Die Schwerpunkte liegen auf Newton-basierten Methoden, Penalty- und Barriere-Verfahren sowie den modernen Innere-Punkte-Methoden.
Was ist das primäre Ziel oder die Forschungsfrage?
Ziel ist die theoretische Ausarbeitung und algorithmische Analyse verschiedener Verfahren hinsichtlich ihrer Korrektheit, Effizienz und Konvergenzeigenschaften.
Welche wissenschaftlichen Methoden werden verwendet?
Die Arbeit nutzt mathematische Beweisführungen für Konvergenzeigenschaften sowie numerische Simulationen in C++ und Matlab, um die Effizienz der Algorithmen zu vergleichen.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in mathematische Grundlagen, Quasi-Newton-Verfahren, Penalty- und Penalty-Lagrange-Methoden, Barriere-Verfahren sowie eine tiefgehende Analyse der Innere-Punkte-Verfahren.
Welche Schlüsselwörter charakterisieren die Arbeit?
Zu den wichtigsten Begriffen zählen nichtlineare Optimierung, BFGS-Verfahren, Penalty-Methoden, Barriere-Verfahren, Innere-Punkte-Verfahren und Konvergenzgeschwindigkeit.
Wie unterscheidet sich die Penalty-Lagrange-Methode vom Standard-Penalty-Verfahren?
Die Penalty-Lagrange-Methode verwendet zusätzlich duale Variablen, um die Verschlechterung der Kondition des Optimierungsproblems bei steigendem Penalty-Parameter zu vermeiden.
Welche Rolle spielt die "Restaurationsphase" bei den Innere-Punkte-Verfahren?
Sie dient dazu, bei unzulässigen Punkten oder schlecht konditionierten Problemen einen zulässigen Punkt wiederherzustellen, wenn der Standard-Schrittweitenalgorithmus keinen hinreichenden Fortschritt erzielt.
Warum sind die untersuchten Verfahren für die Praxis relevant?
Da viele reale Entscheidungsprozesse in Wirtschaft und Industrie auf Optimierungsproblemen basieren, ist die effiziente und korrekte numerische Lösung dieser Aufgaben durch moderne Rechner essenziell.
- Citation du texte
- Nadeshda Botschkarewa (Auteur), 2010, Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung, Munich, GRIN Verlag, https://www.grin.com/document/274017
