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
- Mathematische Grundlagen
- Grundlagen aus der Linearen Algebra
- Definitionen und Bezeichnungen der Optimierungstheorie
- Optimalitätsbedingungen
- Das Konvergenzverhalten iterativer Verfahren
- Quasi-Newton-Verfahren zur Lösung von unrestringiertem Optimierungspro-
blemen
- Grundidee des Newton-Verfahrens
- Idee des BFGS-Verfahrens
- Algorithmus und Konvergenz
- Lokales BFGS-Verfahren
- Globalisiertes BFGS-Verfahren
- Effizienzanalyse
- Penalty-Verfahren anhand der quadratischen Penalty-Funktion
- Idee des Verfahrens und Konstruktion von Penalty-Funktionen
- Algorithmus und Konvergenz
- Effizienzanalyse
- Penalty-Lagrange-Methode
- Exakte Penalty-Funktionen
- Idee des Verfahrens und Konstruktion von Penalty-Lagrange-Funktionen
- Algorithmus und Konvergenz
- Erweiterung auf Ungleichungsrestriktionen
- Effizienzanalyse
- Barriere-Verfahren anhand der logarithmischen Barriere-Funktion
- Idee des Verfahrens und Konstruktion von Barriere-Funktionen
- Algorithmus und Konvergenz
- Effizienzanalyse
- Innere-Punkte-Verfahren
- Grundidee der Verfahren anhand linearer Probleme
- Grundlagen der linearen Optimierung
- Logarithmische Barriere, zentraler Pfad
- Anwendung des Newton-Verfahrens in Innere-Punkte-Verfahren
- Allgemeiner Algorithmus
- Pfad-Verfolgungs-Verfahren und Konvergenz
- Grundzüge der primal-dualen Innere-Punkte-Verfahren für nichtlineare
Probleme
- Barriere-Problem und gestörte Optimalitätsbedingungen nichtlinearer primaler Probleme
- Globalisierung des Verfahrens
- Backtracking-Methode für unrestringierte Probleme
- Backtracking-Schrittweitenbestimmung mit dem Filteransatz
- Algorithmus mit Korrekturschritten
- Grundidee der Verfahren anhand linearer Probleme
- Numerische Fallstudie
- Implementierung
- Parameter
- Numerische Tests
- ANHANG
- Anhang
- Anhang
- Anhang
- Tabellenverzeichnis
- Abbildungsverzeichnis
- Algorithmenverzeichnis
- Literaturverzeichnis
Zielsetzung und Themenschwerpunkte
Die Bachelorarbeit beschäftigt sich mit der nichtlinearen Optimierung, die das Problem der Minimierung oder Maximierung einer nichtlinearen Funktion unter Berücksichtigung einer endlichen Anzahl von Nebenbedingungen behandelt. Ziel der Arbeit ist es, verschiedene numerische Verfahren zur Lösung dieser Aufgaben vorzustellen, ihre theoretischen Grundlagen zu erläutern und ihre Effizienz anhand von numerischen Tests zu vergleichen.
- Theoretische Grundlagen verschiedener Verfahren der nichtlinearen Optimierung
- Konvergenzanalyse der Verfahren unter Berücksichtigung von Korrektheit und Effizienz
- Praktische Implementierung der Verfahren in C++ unter Verwendung der numerischen Bibliothek FLENS
- Numerische Fallstudie zur Evaluierung der Effizienz der Verfahren anhand von Testproblemen
Zusammenfassung der Kapitel
Die Arbeit beginnt mit einer Einführung in die mathematischen Grundlagen der nichtlinearen Optimierung. Es werden wichtige Definitionen und Sätze aus der Linearen Algebra, Analysis und Numerik zusammengestellt, die für die Herleitung und Konvergenzanalyse der behandelten Verfahren benötigt werden.
Im zweiten Kapitel wird das Quasi-Newton-Verfahren, insbesondere das BFGS-Verfahren, vorgestellt. Es wird die Grundidee des Newton-Verfahrens skizziert und anschließend die Herleitung des BFGS-Verfahrens erläutert. Die Konvergenzeigenschaften des Verfahrens werden unter Verwendung von Konvergenzkriterien analysiert und ein Algorithmus für die numerische Behandlung des Verfahrens vorgestellt.
Das dritte Kapitel widmet sich dem Penalty-Verfahren anhand der quadratischen Penalty-Funktion. Die Idee des Verfahrens, die Konstruktion der Penalty-Funktion und die zugehörigen Algorithmen werden vorgestellt. Die Konvergenz des Verfahrens und seine Effizienz, insbesondere die Verschlechterung der Kondition, werden untersucht.
Das vierte Kapitel behandelt die Penalty-Lagrange-Methode. Es wird die Klasse der exakten Penalty-Funktionen eingeführt und ihre Vorteile gegenüber der quadratischen Penalty-Funktion aufgezeigt. Anschließend wird die Penalty-Lagrange-Methode als Erweiterung des quadratischen Penalty-Verfahrens vorgestellt. Es werden die Konstruktion der Penalty-Lagrange-Funktion, die zugehörigen Algorithmen und die Konvergenzeigenschaften des Verfahrens erläutert.
Im fünften Kapitel wird das Barriere-Verfahren anhand der logarithmischen Barriere-Funktion vorgestellt. Die Idee des Verfahrens, die Konstruktion der Barriere-Funktion und die zugehörigen Algorithmen werden erläutert. Die Konvergenz des Verfahrens und seine Effizienz, insbesondere die Verschlechterung der Kondition, werden untersucht.
Das sechste Kapitel gibt einen Einblick in die Grundlagen der Innere-Punkte-Methoden. Die Grundidee des Verfahrens wird an einem Spezialfall, nämlich linearen Problemen, erläutert. Es werden wichtige Konzepte wie der zentrale Pfad und die gestörten Optimalitätsbedingungen eingeführt. Anschließend werden die inneren Iterationen des Verfahrens, die auf dem Newton-Verfahren basieren, vorgestellt. Es wird ein Algorithmus für ein zulässiges primal-duales Innere-Punkte-Verfahren für lineare Probleme beschrieben und die Konvergenzeigenschaften des Verfahrens analysiert.
Das Kapitel schliesst mit einer Erweiterung des Verfahrens auf allgemeine nichtlineare Probleme. Es werden die Barriere-Probleme und die gestörten Optimalitätsbedingungen für nichtlineare Probleme definiert. Anschließend werden die zentralen Elemente des Verfahrens, wie die Berechnung der Suchrichtungen und die Globalisierungsmethoden, erläutert.
Das letzte Kapitel der Arbeit befasst sich mit einer numerischen Fallstudie. Es werden die Implementierung der vorgestellten Verfahren in C++ unter Verwendung der numerischen Bibliothek FLENS und die Auswahl der Steuerparameter erläutert. Die Ergebnisse von numerischen Tests mit 35 Testproblemen werden präsentiert und die Effizienz der Verfahren anhand von verschiedenen Kriterien wie Laufzeit, Anzahl der Iterationen und Auswertungen der Funktionen verglichen.
Schlüsselwörter
Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen die nichtlineare Optimierung, verschiedene numerische Verfahren, Konvergenzanalyse, Effizienz, Implementierung in C++, numerische Fallstudie, Testprobleme, Penalty-Verfahren, Penalty-Lagrange-Methode, Barriere-Verfahren, Innere-Punkte-Verfahren, BFGS-Verfahren, Newton-Verfahren, Schrittweitenbestimmung, Filteransatz, Korrekturschritte, und die numerische Bibliothek FLENS.
- Quote paper
- Nadeshda Botschkarewa (Author), 2010, Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung, Munich, GRIN Verlag, https://www.grin.com/document/274017
