Robuste Optimierung 1 - Cheatsheet

Definition und Bedeutung der robusten Optimierung

Definition:

Robuste Optimierung befasst sich mit der Lösung von Optimierungsproblemen unter Unsicherheit in den Parametern, wobei das Ziel darin besteht, Lösungen zu finden, die gegenüber diesen Unsicherheiten robust sind.

Details:

• Ziel: Optimierung mit Unsicherheiten sicherstellen
• Vorteil: Vermeiden worst-case Szenarien
• Modell: Parameter unsicher, bleiben innerhalb bekannter Mengen (Unsicherheitsmengen)
• Notation: Entscheidungsvariable \(x\), Unsicherheitsparameter \(u\)
• Optimierungsproblem: \[\min_{x} \max_{u \in U} f(x, u)\]
• Wettbewerb mit anderen Methoden: Stochastische Optimierung

Vergleich zwischen robuster und klassischer Optimierung

Definition:

Vergleich der Unterschiede zwischen robuster Optimierung und klassischer Optimierung, insbesondere im Umgang mit Unsicherheiten.

Details:

• Klassische Optimierung: Optimierung unter festen Parametern, keine Berücksichtigung von Unsicherheiten.
• Robuste Optimierung: Berücksichtigung von Unsicherheiten, Ziel ist eine Lösung, die unter allen erdenklichen Szenarien gut funktioniert.
• Formulierung: Robuste Optimierung löst Probleme der Form \(\min_{x} \max_{u \in \mathcal{U}} f(x,u)\), wobei \( \mathcal{U} \) die Unsicherheitsmenge darstellt.
• Flexibilität: Robuste Optimierung führt oft zu konservativeren aber stabileren Lösungen.

Modellierung von Unsicherheiten: Stochastische vs. robuste Modelle

Definition:

Modellierung von Unsicherheiten in Optimierungsproblemen; Vergleich zwischen stochastischen und robusten Modellen.

Details:

• Stochastische Modelle:
• Unsicherheiten durch Wahrscheinlichkeitsverteilungen modelliert.
• Ziel: Erwartungen oder Wahrscheinlichkeiten optimieren.
• Beispiel: \[\min_{x \in X} \mathbb{E}[f(x,\xi)] \]
• Robuste Modelle:
• Keine Wahrscheinlichkeiten, stattdessen Unsicherheiten als Szenarios.
• Ziel: Lösung, die unter allen Szenarien gut ist.
• Beispiel: \[\min_{x \in X} \max_{\xi \in \Xi} f(x,\xi) \]

Methoden zur Lösung linearer robuster Optimierungsprobleme

Definition:

Methoden zur Bestimmung optimaler Lösungen für Optimierungsprobleme unter Unsicherheit.

Details:

• Lineare robuste Optimierungsprobleme basieren auf dem Modell: \min_{x \in X} \textstyle\max_{u \in U} c^T x , \quad\text{s.t.} \quad A(u)x \leq b(u)
• Zentrale Methode: Szenarienansatz
• Alternative: Unsicherheitsmengen mittels Polyeder oder Ellipsoide definieren
• Konservativer Ansatz: Robustheit mit Sicherheitsmargen
• Iterative Algorithmen: Column-and-Constraint-Generation (CCG) oder Benders-Dekomposition
• Komplexität erhöhen bei großer Unsicherheitsmenge

Heuristische und exakte Algorithmen zur robusten Optimierung

Definition:

Methoden zur Lösung von robusten Optimierungsproblemen, entweder durch Näherungsverfahren (heuristische) oder durch präzise Berechnung (exakte).

Details:

• Heuristische Algorithmen nutzen Näherungstechniken, um schnelle und oft gute, aber nicht immer optimale Lösungen zu finden.
• Exakte Algorithmen garantieren die optimale Lösung, sind jedoch oft langsamer und komplexer.
• Bekannte heuristische Methoden: Genetische Algorithmen, Simulated Annealing, Tabu-Suche.
• Bekannte exakte Methoden: Branch-and-Bound, Simplex-Verfahren, Schnittebenenverfahren.
• Trade-off: Präzision vs. Rechenzeit und Komplexität.
• Typische Anwendungen: Logistik, Finanzplanung, Maschinelles Lernen, Netzwerkrouting.

Sensitivitätsanalyse und Bewertung von Unsicherheiten in Modellen

Definition:

Sensitivitätsanalyse untersucht, wie die Variation von Modellenparametern die Ergebnissen beeinflusst. Bewertung von Unsicherheiten in Modellen hilft, die Robustheit der Lösungen zu bestimmen.

Details:

• Wichtige Methoden: One-at-a-Time (OAT), Monte-Carlo-Simulationen, Partielle Ableitungen
• Ziele: Identifizierung kritischer Parameter, Einschätzung der Modellzuverlässigkeit und Robustheit
• Sensitivitätsmaß: \(S_i = \frac{\frac{\text{d} y}{\text{d} p_i}}{y} \)
• Unsicherheitsmaß: Varianz, Konfidenzintervalle, Worst-Case-Analyse
• Werkzeuge in der Robustheitsoptimierung: Szenario-Analysen, Stochastic Programming

Approximationsmethoden und iterative Lösungsansätze

Definition:

Methoden zur Annäherung an optimale Lösung oder iterativ verbessernde Verfahren.

Details:

• Iterative Lösungsmethoden: Starten mit einer initialen Schätzung und schrittweise Annäherung an die Lösung.
• Gradientenverfahren: Aktualisierung der Lösung anhand des Gradienten der Zielfunktion.
• Newton-Verfahren: Nutzen der zweiten Ableitung zur Verbesserung der Schätzung.
• Verwendung von Heuristiken und Metaheuristiken: Annäherung durch Näherungsverfahren wie genetische Algorithmen oder Simulated Annealing.
• Robuste Optimierung: Sicherstellung, dass Lösungen unter variierenden Parametern robust bleiben.

Anwendung in der Finanzoptimierung unter Unsicherheit

Definition:

Anwendung robuster Optimierung für Finanzentscheidungen, die unter Unsicherheit getroffen werden müssen.

Details:

• Robuste Optimierung: Stärkere Modellierung bei Unsicherheit.
• Zielfunktion: Maximierung des erwarteten Nutzens unter Berücksichtigung des Risikos.
• Parameter: Unsichere Parameter als Intervalle oder Verteilung modellieren.
• Formulierung: \min_{x \in X} \max_{u \in U} c(x, u)
• Beispiel: Portfoliomanagement - Minimierung des maximalen Verlusts.