Methods and applications of mathematical optimization - Cheatsheet

Simplex-Algorithmus und Dualitätstheorie

Definition:

Methode zur Lösung linearer Optimierungsprobleme und dazugehörige Analyse der Beziehung zwischen Primal- und Dualproblem

Details:

• Simplex-Algorithmus: Iteratives Verfahren zur Lösung von LP-Problemen
• Schrittweise Verbesserung der Zielfunktion entlang der Kanten des zulässigen Bereichs
• Kriterium zur Wahl der Pivot-Elemente: Eingangs- und Ausgangsvariablen
• Dualität: Jedes LP-Problem hat ein zugehöriges Dualproblem
• Schwache Dualität: Wert des Dualproblems ist Schranke für den Wert des Primalproblems
• Starke Dualität: Optimale Lösungen beider Probleme haben gleiche Zielfunktionswerte
• Dualitätssätze: Verbindung zwischen Lösungen von Primal- und Dualproblem
• Primal und Dual - Lösungen liefern Sensitivitätsanalysen und ökonomische Interpretationen

Schattenpreise und Sensitivitätsanalyse

Definition:

Schattenpreise spiegeln den impliziten Wert einer Knotenpunktressource wider, Sensitivitätsanalyse zeigt, wie optimale Lösungen auf Änderungen der Inputparameter reagieren.

Details:

• Schattenpreise: Lagrange-Multiplikatoren \(\lambda\) für Nebenbedingungen
• Geben an, wie sich der Zielfunktionswert ändert, wenn sich die rechte Seite einer Nebenbedingung um eine Einheit ändert
• Sensitivitätsanalyse untersucht Robustheit des Optimierungsproblems
• Analyse der zulässigen Wertebereiche für Parameteränderungen: Rechtsseiten- und Zielfunktionskoeffizienten
• Sensitivitätsintervalle: \[ b_i^- , b_i^+ \] , \[ c_j^- , c_j^+ \]

Lokale vs. globale Optima

Definition:

Lokales Optimum: Extremwert (Minimum oder Maximum) einer Funktion innerhalb eines bestimmten Bereichs. Globales Optimum: Extremwert (Minimum oder Maximum) der gesamten Funktion.

Details:

• Lokales Minimum: \[ f(x) \text{ hat ein lokales Minimum bei } x = a \text{, wenn } f(a) \text{ kleiner ist als } f(x) \text{ für alle } x \text{ in der Umgebung von } a. \]
• Globales Minimum: \[ f(x) \text{ hat ein globales Minimum bei } x = a \text{, wenn } f(a) \text{ kleiner ist als } f(x) \text{ für alle } x \text{ im gesamten Definitionsbereich.} \]
• Lokales Maximum: \[ f(x) \text{ hat ein lokales Maximum bei } x = a \text{, wenn } f(a) \text{ größer ist als } f(x) \text{ für alle } x \text{ in der Umgebung von } a. \]
• Globales Maximum: \[ f(x) \text{ hat ein globales Maximum bei } x = a \text{, wenn } f(a) \text{ größer ist als } f(x) \text{ für alle } x \text{ im gesamten Definitionsbereich.} \]
• Unterschied: Lokale Optima sind nur in einem eingeschränkten Bereich optimal, während globale Optima im gesamten Definitionsbereich der Funktion optimal sind.
• Methoden zum Finden: Gradient Descend (lokales Optimum), Genetische Algorithmen (globales Optimum).

Branch-and-Bound-Methoden

Definition:

Verfahren zur ganzzahligen und kombinatorischen Optimierung, das systematisch den Lösungsraum durch Zerlegung in Teilprobleme durchsucht und durch Schrankenbildung Unzulässigkeiten eliminiert.

Details:

• Wichtig für Integer-Programmierung und NP-schwere Probleme
• Verzweigung: Problem wird in kleinere Teilprobleme zerlegt
• Schranken: Obere und untere Schranken zur Bewertung der Teilprobleme
• Bounding: Wenn Schranken die optimale Lösung ausschließen, wird das Teilproblem verworfen
• Ziel: Reduzierung der Anzahl der zu prüfenden Lösungen
• Anwendungsbeispiel: Traveling Salesman Problem (TSP)

Bellmansche Gleichungen und dynamische Programmierung

Definition:

Betrifft eine Methode zur Lösung von Optimierungsproblemen über mehrere Perioden hinweg durch Zerlegung in einfachere Teilprobleme.

Details:

• Dynamische Programmierung: Technik zur Lösung komplexer Probleme durch Aufteilung in einfachere Teilprobleme.
• Bellmansche Gleichung: Rekursive Gleichung, die den optimalen Wert an jedem Entscheidungszeitpunkt beschreibt.
• Formel: \[ V(s) = \max_{a} \{R(s, a) + \gamma V(T(s, a))\} \]
• \( V(s) \): Wertfunktion im Zustand \( s \).
• \( R(s, a) \): Sofortige Belohnung bei Aktion \( a \) im Zustand \( s \).
• \( \gamma \): Diskontfaktor (\( 0 < \gamma < 1 \)).
• \( T(s, a) \): Übergangsfunktion (neuer Zustand nach Aktion \( a \) in Zustand \( s \)).

Nash-Gleichgewichte in der Spieltheorie

Definition:

Strategisches Gleichgewicht, in dem kein Spieler durch einseitige Strategieänderung profitieren kann.

Details:

• Für jedes Spieler-Paar (i,j), Strategien (s_i, s'_i): U_i(s_i, s_{-i}) ≥ U_i(s'_i, s_{-i})
• U = Nutzenfunktion
• s = Strategie
• Voraussetzung: Rationalität und vollständige Informationen

Evolutionäre Spieltheorie

Definition:

Untersucht die Anpassung und das Verhalten von Strategien in Populationen.

Details:

• Zentral: Replikatordynamik - beschreibt Veränderung der Strategiehäufigkeit
• Gleichgewicht: Evolutionär stabiles Gleichgewicht (ESG)
• Formel: Replikatordynamik \(\frac{dx_i}{dt} = x_i [f_i(x) - \bar{f}(x)]\)
• Beispiele: Gefangenendilemma, Falken-Tauben-Spiel
• Anwendung: Analyse von Wettbewerb, Kooperation und Evolution in Märkten