Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung

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

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.