Die Optimierung ist ein sehr wichtiger Bestandteil unserer heutigen Gesellschaft geworden.
Sie ist in allen Lebens- und Geschäftsbereichen wieder zu erkennen. Es wird immer
danach gestrebt den Lebensstandard der Menschen zu verbessern bzw. zu optimieren.
Dies beginnt in kleinen Betrieben und endet in großen Konzernen und weltweit erfolgreichen
Unternehmen. So wird stets versucht den größtmöglichen Gewinn zu erzielen und
die dabei entstehenden Kosten bestmöglichst zu minimieren. Dies gelingt am besten mit
verschiedenen Optimierungsmethoden.
Da die Optimierung immer stärker in Naturwissenschaften, Wirtschaftswissenschaften
und Technik vertreten ist, gewinnt diese immer mehr an Bedeutung. Demzufolge reifen
die mathematischen Theorien, sowie die Software zunehmend aus. Es wird versucht
anwendungsrelevante Probleme durch mathematische Formulierungen und die Implementierung
von Optimierungsverfahren zu lösen.
Im Folgenden wird das Teilgebiet der konvexen, nichtglatten Optimierung behandelt. In
diesem Bereich der Optimierung werden Probleme betrachtet, bei denen das Minimum
einer konvexen Funktion berechnet werden soll, wobei diese Funktion aber nicht überall
differenzierbar ist.
Ziel dieser Arbeit besteht darin, verschiedene Methoden zu untersuchen und zu implementieren,
die solche Optimierungsprobleme lösen. Diese Arbeit orientiert sich hauptsächlich an dem Buch Numerische Verfahren der konvexen, nichtglatten Optimierung
von Walter Alt. Als Erstes werden ein paar Grundlagen der Konvexität gelegt, danach
wird neben dem Gradientenverfahren auch das Subgradientenverfahren vorgestellt und als Letztes wird das Bundel-Verfahren behandelt. Die besprochenen Verfahren werden durch programmierte Beispiele in C/C++ vertieft und mit Hilfe von Scilab graphisch veranschaulicht. Im Anhang benden sich die Quellcodes der Beispiele.
Inhaltsverzeichnis
1. Einleitung
2. Grundlagen
2.1. Konvexe Mengen und Funktionen
2.1.1. Konvexe Mengen
2.1.2. Konvexe Funktionen
2.2. Lokale Lipschitz-Stetigkeit
2.3. Subdifferential und Richtungsableitung
2.4. Konvexe Optimierungsprobleme
2.4.1. unrestringierte Optimierungsaufgaben
2.5. Abstiegsrichtungen
2.6. Lagrange-Multiplikatoren
3. Das Gradientenverfahren
3.1. Das Verfahren
3.2. Schrittweitenbestimmung
3.2.1. Armijo-Regel
3.2.2. Wolfe-Powell-Regel
3.2.3. Bisektion
3.3. Beispiele
3.3.1. Bananen-Funktion
3.3.2. Himmelblau-Funktion
3.3.3. Wolfe-Funktion
4. Das Subgradientenverfahren
4.1. Das Verfahren
4.2. Konvergenzbetrachtungen
4.3. Beispiele
4.3.1. Betragsfunktion
4.3.2. Wolfe-Funktion
5. Approximatives Abstiegsverfahren
6. Bundle-Verfahren
6.1. Verwendung eines Bundles
6.2. Verfahren mit approximativer Suchrichtung
6.3. Das Schrittweitenverfahren
6.4. Konstruktion des Bundles
6.5. Ein implementierbares Abstiegsverfahren
6.6. Allgemeiner Ablauf des Bundle-Verfahrens
6.7. Wolfe-Funktion
7. Schlussbemerkung
Zielsetzung & Themen
Die vorliegende Bachelorarbeit befasst sich mit der Theorie und praktischen Implementierung verschiedener mathematischer Optimierungsverfahren, insbesondere für den Bereich der konvexen, nichtglatten Optimierung, bei der Zielfunktionen nicht überall differenzierbar sind.
- Grundlagen der Konvexität, Subdifferentiale und Richtungsableitungen
- Analyse und Anwendung des klassischen Gradientenverfahrens
- Untersuchung des Subgradientenverfahrens zur Bewältigung nichtglatter Funktionen
- Einführung und mathematische Herleitung von approximativen Abstiegsverfahren
- Detaillierte Erläuterung und algorithmische Struktur von Bundle-Verfahren
Auszug aus dem Buch
3.1. Das Verfahren
In diesem Kapitel wird als erstes konkretes Verfahren, das sogenannte Gradientenverfahren, häufig auch das Verfahren des steilsten Abstiegs bezeichnet, untersucht. Bei diesem Verfahren bestimmt man im Punkt x(k) diejenigen Richtungen d(k), in der f am stärksten abnimmt. Außerdem bedarf es dazu einer stetig differenzierbaren Zielfunktion. Um dies zu verdeutlichen wurde dieses Verfahren in C/C++ implementiert und auf ein Beispiel, auf das später genauer eingegangen wird, angewendet.
Algorithmus 3.1.1.[6] (Gradientenverfahren)
Wähle einen Startpunkt x(0) ∈ Rn und setze k := 0.
1. Berechne ∇f(x(k)).
2. Abbruchkriterium: Falls ∇f(x(k)) = 0n, dann stoppe das Verfahren.
3. Berechne zu d(k) = −∇f(x(k)) eine Schrittweite tk > 0 durch Lösung des eindimensionalen Minimierungsproblems mint≥0 h(t) := f(x(k) + td(k)).
4. Setze x(k+1) := x(k) + tkd(k), k := k + 1 und gehe zu 1 zurück.
Zu Beginn des Verfahrens wird ein Startpunkt x(0) ∈ Rn gewählt, wobei k = 0 gilt. Außerdem wird der Gradient der Zielfunktion f(x(k)) berechnet. Nun gibt es zwei verschiedene Möglichkeiten um das Verfahren weiterzuführen:
1. Falls ∇f(x(k)) = 0n gilt, wird das Verfahren abgebrochen.
2. Falls ∇f(x(k)) ≠ 0n gilt, so wird eine Suchrichtung d(k) = −∇f(x(k)), also die Richtung des steilsten Abstiegs, in f in x(k) bestimmt.
Zusammenfassung der Kapitel
1. Einleitung: Diese Einleitung führt in die Bedeutung der Optimierung ein und skizziert das Ziel der Arbeit, verschiedene Verfahren zur Lösung konvexer, nichtglatter Probleme zu untersuchen und zu implementieren.
2. Grundlagen: Hier werden die mathematischen Basisvoraussetzungen, wie konvexe Mengen, Funktionen, lokale Lipschitz-Stetigkeit, Subdifferentiale und Lagrange-Multiplikatoren, theoretisch erarbeitet.
3. Das Gradientenverfahren: Dieses Kapitel erläutert das Gradientenverfahren für differenzierbare Funktionen, inklusive verschiedener Schrittweitenstrategien und praktischer Beispiele wie der Bananen-Funktion.
4. Das Subgradientenverfahren: Es wird untersucht, wie das Gradientenverfahren auf nicht differenzierbare, konvexe Funktionen durch die Verwendung von Subgradienten erweitert werden kann.
5. Approximatives Abstiegsverfahren: Dieses Kapitel dient der theoretischen Vorbereitung für komplexere Verfahren durch die Einführung von Approximationen des Subdifferentials und der Richtungsableitung.
6. Bundle-Verfahren: Dies ist das zentrale Kapitel zur Lösung nichtglatter Optimierungsprobleme, das die Konstruktion und Anwendung von Bundles zur Bestimmung von Abstiegsrichtungen detailliert beschreibt.
7. Schlussbemerkung: Die Arbeit schließt mit einer zusammenfassenden Bewertung, wobei das Bundle-Verfahren als die genaueste und schnellste der behandelten Methoden hervorgehoben wird.
Schlüsselwörter
Konvexe Optimierung, Nichtglatte Optimierung, Gradientenverfahren, Subgradientenverfahren, Bundle-Verfahren, Subdifferential, Richtungsableitung, Schrittweitensteuerung, Zielfunktion, Konvergenz, Minimierung, Lagrange-Multiplikatoren, Lipschitz-Stetigkeit, Numerische Verfahren, Optimierungsalgorithmen.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der numerischen Lösung von Optimierungsproblemen, insbesondere unter der Bedingung, dass die Zielfunktionen konvex sind und nicht notwendigerweise überall differenzierbar vorliegen.
Was sind die zentralen Themenfelder?
Die Schwerpunkte liegen auf der mathematischen Theorie der konvexen Optimierung, dem Gradientenverfahren, dem Subgradientenverfahren sowie der Implementierung und Analyse fortgeschrittener Bundle-Verfahren.
Was ist das primäre Ziel oder die Forschungsfrage der Arbeit?
Das Ziel ist die Untersuchung und praktische Implementierung von Verfahren, die in der Lage sind, Minimierungsprobleme für konvexe Funktionen zu lösen, selbst wenn diese an bestimmten Stellen nicht differenzierbar sind.
Welche wissenschaftliche Methode wird verwendet?
Es werden mathematische Beweise und Definitionen aus der Optimierungstheorie verwendet, kombiniert mit einer algorithmischen Implementierung in C/C++ und der grafischen Veranschaulichung der Ergebnisse mittels Scilab.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in theoretische Grundlagen, die Behandlung von Gradienten- und Subgradientenverfahren, die Einführung approximativer Abstiegsverfahren sowie eine detaillierte Ausarbeitung der Bundle-Verfahren.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich am besten durch Begriffe wie konvexe Optimierung, Bundle-Verfahren, Subdifferential, nichtglatte Funktionen und numerische Optimierung beschreiben.
Warum ist das einfache Gradientenverfahren für nichtglatte Funktionen oft nicht ausreichend?
Bei nichtglatten Funktionen existiert der Gradient nicht an allen Stellen, was dazu führen kann, dass das Standard-Gradientenverfahren bei der Suche nach einem globalen Optimum in Schwierigkeiten gerät oder das Abbruchkriterium nicht korrekt erfüllt wird.
Wie unterscheidet sich das Bundle-Verfahren von den anderen Methoden?
Das Bundle-Verfahren aggregiert Informationen aus mehreren Subgradienten, um eine präzisere und stabilere Abstiegsrichtung zu berechnen, was es besonders für nicht differenzierbare Funktionen sehr effizient macht.
- Citar trabajo
- Bachelor of Science Irene Filipiak (Autor), 2010, Nichtglatte Optimierung, Múnich, GRIN Verlag, https://www.grin.com/document/232845
