Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung

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
• 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.