Robuste Optimierung 1 - Cheatsheet

Grundkonzepte der robusten Optimierung

Definition:

Grundkonzepte der robusten Optimierung behandeln den Umgang mit Unsicherheiten in Optimierungsproblemen, um Lösungen zu finden, die auch unter variierenden Bedingungen brauchbar bleiben.

Details:

• Ziel: Lösungen finden, die auch bei Unsicherheit der Daten optimal oder nahe optimal bleiben.
• Unsicherheitsbereich: Menge aller möglichen Werte für die unsicheren Parameter (meistens als Polytop dargestellt).
• Robuste Machbarkeit: Eine Lösung ist robust machbar, wenn sie für alle möglichen Realisierungen der Unsicherheiten machbar bleibt.
• Robuste Zielfunktion: Zielfunktion ist robust, wenn sie bei allen Realisierungen der Unsicherheiten innerhalb eines akzeptablen Bereichs bleibt.
• Mathematische Formulierung: \[ \min_{x \in X} \max_{u \in U} c(x, u) \]
• Szenarioansatz: Betrachtung bestimmter Szenarien, um Unsicherheit zu modellieren.

Formulierung robuster Optimierungsprobleme

Definition:

Entwicklung von Optimierungsmodellen, die auch unter Unsicherheiten im Modell (z. B. Datenunsicherheiten) noch guten, zulässigen Lösungen liefern.

Details:

• Erfassung von Unsicherheiten durch Unsicherheitsmengen (Uncertainty Sets): \( \mathcal{U} \)
• Robustes Optimierungsproblem: \( \min_{x \in \mathcal{X}} \; \max_{u \in \mathcal{U}} \; f\left(x, u\right) \)
• Typische Unsicherheitsmengen: Polytopen, Ellipsoiden, Intervallunsicherheiten
• Wichtigkeit von konservativen vs. performanten Lösungen
• Gängige Ansätze: robuste lineare Optimierung, robuste konvexe Optimierung

Lösungstechniken wie Worst-Case-Optimierung

Definition:

Worst-Case-Optimierung ist eine Technik in der robusten Optimierung, um Lösungen zu finden, die unter den schlechtesten möglichen Bedingungen noch akzeptabel sind.

Details:

• Fokus auf den maximalen Verlust minimieren
• Modellierung der Unsicherheit als Reihe von Szenarien
• Ziel: Lösung, die in allen möglichen Szenarien eine zufriedenstellende Leistung erbringt
• Mathematisch formuliert als: \max_{x} \min_{u \in U} f(x,u)

Unterschiedliche Robustheitskriterien

Definition:

Unterschiedliche Robustheitskriterien bewerten, wie gut eine Lösung gegenüber Unsicherheiten im Modell schützt.

Details:

• Statische Robustheit: Lösung muss für alle Unsicherheiten innerhalb eines festgelegten Sets gültig sein.
• Verstellbare Robustheit: Anpassbare Lösungen, die sich durch zusätzliche Informationszuflüsse verbessern lassen.
• Proba­bilistische Robustheit: Lösungsvalidität wird per Wahrscheinlichkeit bestimmt, akzeptabel nur unter vorgegebener Wahrscheinlichkeit.
• Totale Robustheit: Setzt extrem restriktive Kriterien voraus, um Lösung für jede mögliche Unsicherheit gültig zu machen.
• Kostenbasierte Robustheit: Lösung minimiert erwartete Kosten oder Verluste durch Unsicherheiten.
• Verifizierungsfähig durch Formulierungen wie: Max-\textit{min}, Min-\textit{max}, VaR (Value-at-Risk), CVaR (Conditional Value-at-Risk)

Ansätze zur Robustheitsanalyse

Definition:

Ansätze zur Robustheitsanalyse untersuchen, wie sensitiv ein optimales Lösung in Bezug auf Unsicherheiten in den Parametern ist.

Details:

• Berücksichtigung von Unsicherheiten in Eingabedaten.
• Konservativer Ansatz: Worst-Case-Szenarien.
• Stochastischer Ansatz: Verteilung der Unsicherheiten bekannt.
• Trade-off zwischen Robustheit und optimaler Lösung.
• Mathematische Formulierung oft durch Unsicherheitsmengen.
• Ziel: Lösungen finden, die für eine Vielzahl möglicher Szenarien gut sind.

Dualitätsprinzipien und ihre Anwendung

Definition:

Konzepte der Dualität in mathematischer Optimierung, speziell zur Analyse und Lösung von Optimierungsproblemen.

Details:

• Primales Problem: Ursprüngliches Optimierungsproblem
• Dualproblem: Abgeleitetes Problem aus dem Primalen
• Schwach dual: Zielfunktionswerte des Dualproblems bilden obere Schranken für das primale Problem
• Stark dual: Optimallösungen beider Probleme entsprechen sich
• Dualitätssatz: Bei konvexen Problemen gilt starke Dualität
• Anwendung in robuster Optimierung: Lösung worst-case Szenarien durch Betrachtung von Dualproblemen
• Mathematisch ausgedrückt:
• Primales Problem: \(\text{Minimiere } f(x) \)
• Dualproblem: \( \text{Maximiere } g(y) \)
• Schwach dual: \(f(x) \geq g(y)\)
• Stark dual: \(f(x^*) = g(y^*)\)

Vergleich verschiedener Solver und Algorithmen

Definition:

Vergleich verschiedener Methoden zur Lösung von Optimierungsproblemen anhand von Performance, Genauigkeit und Robustheit.

Details:

• Solvertypen: Lineare Programmierung (LP), Ganzzahlige Programmierung (IP), Nichtlineare Programmierung (NLP), Gemischt-ganzzahlige Programmierung (MIP)
• Vergleichskriterien: Laufzeit, Lösungsqualität, Speicherbedarf, Skalierbarkeit, Robustheit gegenüber Störungen
• Beliebte Solver: Gurobi, CPLEX, IPOPT, CBC
• Algorithmen: Simplex, Branch-and-Bound, Interior-Point, Gradient-basierte Methoden
• Robustheit: Fähigkeit des Solvers/Algorithmus, unter Unsicherheiten oder Störungen verlässliche Lösungen zu liefern
• Praxisbeispiele: Transportproblem, Produktionsplanung, Netzwerkdesign

Mathematische Formulierung robuster Optimierungsprobleme

Definition:

Mathematische Formulierung robuster Optimierungsprobleme umfasst die Modellierung von Problemen, bei denen Unsicherheit in der Daten eine Rolle spielt, sodass Lösungen gegenüber Schwankungen und Störungen stabil bleiben.

Details:

• Allgemeine Formulierung: \( \min_{x \in X} \max_{u \in U} f(x, u) \), wobei \( X \) der Lösungsraum und \( U \) der Unsicherheitsraum ist.
• Robuste Zielfunktion: \[ \max_{u \in U} f(x, u) \]
• Robuste Nebenbedingungen: \[ G(x, u) \leq 0 \quad \forall u \in U \]