Robust optimization II - Cheatsheet

Definition und Eigenschaften der robusten Optimierung

Definition:

Formale Methode zur Entscheidungsfindung unter Unsicherheit; zielt darauf ab, Lösungen zu finden, die gegenüber Schwankungen in den Parametern unempfindlich sind.

Details:

• Ziel: Minimierung des schlimmstmöglichen Falles (Worst-Case-Optimierung)
• Unsicherheitsmenge \(\mathcal{U}\): Definiert mögliche Abweichungen von nominalen Parametern
• Robustes Optimierungsproblem: \[ \min_{x \in X} \max_{u \in \mathcal{U}} f(x, u) \]
• Vergleich zu stochastischer Optimierung: Keine Wahrscheinlichkeitsverteilungen, nur Unsicherheitsmengen berücksichtigt
• Anwendungen: Supply Chain Management, Finanzplanung, Ingenieurwesen

Unterschiede zu klassischen Optimierungsmethoden

Definition:

Unterschiede zwischen robusten und klassischen Optimierungsmethoden.

Details:

• Robuste Optimierung zielt auf Lösungen, die unter Unsicherheit stabil sind.
• Klassische Optimierung maximiert/minimiert eine Zielfunktion unter festen Bedingungen.
• Robuste Optimierung verwendet \textit{Unsicherheitsmengen} zur Modellierung der Datenunsicherheit.
• Klassische Methoden sind oft sensibler gegenüber Parameteränderungen.
• Robuste Optimierung führt Lösungen ein, die für alle möglichen Szenarien innerhalb der Unsicherheitsmenge gültig sind.
• Erfordert oft mehr Rechenleistung und komplexere Algorithmen.

Mathematische Formulierung von Optimierungsproblemen

Definition:

Mathematische Formulierung von Optimierungsproblemen bezieht sich auf die präzise Darstellung eines Optimierungsproblems in mathematischen Ausdrücken.

Details:

• Objektivfunktion: \( \text{minimize/maximize } f(x) \)
• Entscheidungsvariablen: Vektoren oder Matrizen, die die zu optimierenden Größen darstellen
• Einschränkungen: Bedingungen, die die zulässigen Lösungen beschränken \( g_i(x) \leq 0, \ h_j(x) = 0 \)
• Zustandsraum: Menge aller möglichen Lösungskandidaten
• Lösungsverfahren: Methoden zur Bestimmung einer optimalen Lösung, z.B. Lagrange-Multiplikatoren, Simplex-Algorithmus

Einführung in Unsicherheitsmodellierung und -management

Definition:

Einführung in die Methoden und Konzepte zur Modellierung und zum Management von Unsicherheiten in mathematischen und informatischen Kontexten.

Details:

• Unsicherheitsarten: stochastisch vs. nicht-stochastisch
• Modelle zur Erfassung von Unsicherheiten: Wahrscheinlichkeitsverteilungen, Intervallmethoden
• Management-Techniken: Sensitivitätsanalyse, Szenarioanalyse, robuste Optimierung
• Ziel: Entwicklung von Systemen, die zuverlässig unter Unsicherheiten arbeiten können

Konzepte der konvexen Optimierung und Dualität

Definition:

Zentrale Themen der Optimierung: Konvexe Funktionen/Mengen, starke/Schwache Dualität

Details:

• Eine Menge C ist konvex, wenn für alle x, y ∈ C und \( \theta \in [0,1] \) gilt: \[ \theta x + (1 - \theta) y \in C \]
• Eine Funktion f ist konvex, wenn für alle x, y im Definitionsbereich und \( \theta \in [0,1] \) gilt: \[ f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta) f(y) \]
• Primalproblem: \[ \min_{x \in \mathbb{R}^n} f(x) \]
• Dualproblem: \[ \max_{\lambda \geq 0} g(\lambda) \]
• Schwache Dualität: \[ f(x^*) \geq g(\lambda^*) \]
• Starke Dualität gilt unter bestimmten Bedingungen (z.B. Slater-Bedingung)

Speziell angepasste Algorithmen für robuste Optimierung

Definition:

Optimierungsalgorithmen, die an Unsicherheiten in den Daten oder Modellen angepasst sind, um robuste Lösungen zu garantieren.

Details:

• Fokussiert auf Widerstandsfähigkeit gegen Unsicherheiten in Eingabedaten
• Methoden: Szenarien-Ansatz, Verfeinerung von Bertsimas und Sim Algorithmus
• Beispiel: Berücksichtigung von Bandbreiten für Parameter anstelle fixer Werte
• Nicht zu verwechseln mit einfacherer Sensitivitätsanalyse
• Verwendet oft lineare und nichtlineare Programmierung
• Wichtige Methoden: Schnittverfahren, Approximationstechniken
• Ziel: Lösungensspaces minimieren und robuste Optimallösungen erreichen
• Einsatz in Lieferketten, Finanzplanung, Ingenieurswesen

Stabilität und Sensitivitätsanalyse von Lösungen

Definition:

Untersuchung der Robustheit von Lösungen bei Änderungen der Eingabedaten oder Parameter.

Details:

• Stabilität: Analyse der Variations- und Fehleranfälligkeit einer Lösung.
• Sensitivitätsanalyse: Messen, wie Änderungen der Eingabedaten die Lösung beeinflussen.
• Mathematisch oft durch partielle Ableitungen oder numerische Methoden untersucht.
• Wichtige Konzepte: bedingte Nummer (condition number), Worst-Case-Analyse und Szenarienanalyse.
• Stabilitätskriterien: Konvergenz und Konsistenz.
• Ziel: Sicherstellen, dass die Lösung unter realistischen Bedingungen brauchbar bleibt.

Numerische Verfahren und Implementierungsdetails

Definition:

Berechnungsmethoden und Implementierungstechniken zur Lösung robuster Optimierungsprobleme.

Details:

• Vermeide naive Algorithmen - bevorzuge effizientere Methoden wie Simplex oder Interior-Point.
• Verwendete numerische Verfahren hängen von speziellen Anforderungen und Problemstruktur ab.
• Software-Implementierungen sollten Präzision und Stabilität der numerischen Berechnungen sicherstellen.
• Bewertung der Komplexität und des Speicherbedarfs der Algorithmen.
• Beispiele für Software-Tools: MATLAB, Python (SciPy, NumPy), C++ (COIN-OR).