Grundlagen und Verfahren der Optimierung Flashcards
Formelle Definition eines Optimierungsproblems
Formell:
min 𝑓(𝒙)(Zielfunktion)
mit 𝑔1…𝑛g(𝒙) ≤ 0 (Ungleichheitsbedingungen)
und ℎ1…𝑛h(𝒙) = 0 (Gleichheitsbedingungen)
Gesucht: 𝒙∗ = arg min 𝑓(𝒙)
(Entwurfsvariable, die 𝑓 minimiert)
Optimierungsaufgaben werden in der Literatur als Minimierungsaufgaben behandelt. Maximierungsaufgaben können immer in Minimierungsaufgaben umgewandelt werden über max(f(x))=min(-f(x))
Definition: Optimalitätsbedingung
Ist die Zielfunktion 𝑓 zweimal stetig differenzierbar, dann gilt für ein Minimum:
∇𝑓(𝑥∗) = 0 → verschwindender Gradient am Punkt 𝑥∗
∇2𝑓(𝑥∗) = 𝑯 → HESSE-Matrix 𝑯 positiv-definit am Punkt 𝑥∗ (nur positive Eigenwerte)
Definition: Optimum
Gibt es in einem Bereich x um den Punkt keinen weiteren Punkt mit einen niedrigeren Funktionswert dann liegt ein Optimum (pl. Optima) vor.
Optimierungsalgorithmen
Optimierungsprobleme werden allgemein iterativ gelöst, durch gezieltes Explorieren, Evaluieren und Variieren/Kombinieren von Lösungen
Einteilung in:
gradientenbasierte
und
gradientenfreie
Definition: Optimierungsalgorithmus
Satz mathematischer Schritte zur Lösung eines Optimierungsproblems
Definition: Gradientenbasierte Optimierungsalgorithmus
Nutzen lokaler Ableitungsinformationen (1. u./o. 2. Ableitung),
um ausgehend von einem Startpunkt schrittweise in Richtung fallender Zielfunktion „abzusteigen“
Vorstellung: Kugel, die Hang hinabrollt
Notwendigkeit, die Schrittweite 𝜂 passend zu wählen
Eigenschaften von Gradientenbasierte Optimierungsalgorithmen
Auch bei vielen Entwurfsvariablen (große Suchräume!) sehr schnell, wenn Ableitungen effizient bestimmbar
Garantierte Konvergenz für konvexe Probleme
Lösung hängt vom Startpunkt ab
→ Gefahr, in lokale Minima zu laufen
Definition: Grandientenfreie Optimierungsalgorithmus
Iterative Auswertung und Variation eines Satzes Lösungskandidaten
Synthese neuer Kandidaten durch gezielte Kombination bekannter Kandidaten
Suchverfahren können deterministisch sein, z.B. Nelder-Mead-Verfahren.
Naturinspirierte Verfahren (z.B. genetische Algorithmen) beinhalten oft zusätzlich zufallsbasierte Variationen zur verstärkten Suchraum-Exploration
Eigneschaften: Gradientenfreie Optimierungsalgorithmen
Keine Ableitungsinformationen nötig
Bieten die Möglichkeit, lokalen Minima zu entkommen
Oft langsame Konvergenz und zahlreiche Funktionsaufrufe
Definition: Nebenbedingungen
Nebenbedingungen, auch „Restriktionen“ genannt, können …
den Entwurfsraum 𝑥 und/oder…
den Zustandsraum 𝑓(𝑥) …
beschränken
Es gibt
Ungleichheits- (𝑔) und
Gleichheits-Restriktionen (ℎ)
Lösungstechniken: Restringierte Optimierung
Straffunktionen 𝑠(𝒙) addieren
- Einfache Implementierung
- aber die Nebenbedingung wird nicht exakt eingehalten
„Geschicktes Formulieren des Problems“
Lagrange-Funktion 𝐿 aufstellen + Prüfen der
Karush-Kuhn-Tucker-Bedingungen
KKT-Bedingungen
Karush-Kuhn-Tucker-Bedingungen:
Es gibt keinen Satz hinreichender Bedingungen für allgemeine Optimierungs-probleme, der eine direkte Bestimmung des Optimums ermöglicht
Dies ist nur für bestimmte Optimierungsprobleme möglich, z.B. unter Slater-Bedingungen:
- Zielfunktion 𝑓 ist konvex,
- Ungleichheits-NB 𝑔1…𝑛g
sind konvex oder affin-linear
- Gleichheits-NB ℎ1…𝑛h
sind affin-linear
Für Slater-Optimierungsprobleme gilt: Erfüllt ein Punkt 𝒙∗ die KKT-Bedingungen, so ist 𝒙∗ auch das globale (!) Optimum
Slater-Bedingungen für lineare Elastostatik mit SIMP-Topologieoptimierung praktisch erfüllt
es gibt fünf KKT-Bedingungen
Kritische Bemerkungen zum Thema Optimierung
Vielzahl von Optimierungsverfahren verfügbar:
- Es gibt kein „bestes“ Optimierungsverfahren
Globales Optimum wünschenswert, aber:
- Ohne Vorwissen über die Zielfunktion 𝑓 kann ein globales Optimum nicht garantiert werden
