Fallstudien der mathematischen Modellbildung - Cheatsheet.pdf

Lineare und nichtlineare Optimierung

Definition:

Optimierung zur Bestimmung maximaler/minimaler Werte einer Zielfunktion. Linear: Zielfunktion und Nebenbedingungen linear. Nichtlinear: mindestens eine nichtlineare Funktion.

Details:

• Lineare Optimierung: Probleme in Standardform \[\min c^T x \ \text{unter den Bedingungen} \ Ax \leq b, \ x \geq 0\] \[c, x \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m\]
• Nichtlineare Optimierung: Zielfunktion oder Nebenbedingungen nichtlinear, z.B. \[\min f(x) \ \text{unter den Bedingungen} \ g_i(x) \leq 0, i = 1, \ldots, m, \ h_j(x) = 0, j = 1, \ldots, p \ x \in \Omega\]
• Wichtige Begriffe: Konvexität, Khmer-Punkte, Lagrange-Multiplikatoren

Konvexität und Dualitätstheorie

Definition:

Eigenschaften konvexer Mengen und Funktionen, sowie ihre Anwendung in der Dualitätstheorie der Optimierung

Details:

• Eine Menge \(C\) ist konvex, wenn für alle \(x, y \in C\) und \(\theta \in [0,1]\) gilt: \(\theta x + (1-\theta) y \in C\)
• Eine Funktion \(f: \mathbb{R}^n \to \mathbb{R} \) ist konvex, wenn für alle \(x, y \in \text{dom}(f)\) und \(\theta \in [0,1]\) gilt: \(\theta f(x) + (1-\theta) f(y) \ge f(\theta x + (1-\theta) y)\)
• Beispiel: Lineare Funktionen sind konvex.
• Dualitätstheorie in der Optimierung: Jedes Optimierungsproblem (Primalproblem) \(P\) hat ein zugehöriges Dualproblem \(D\).
• Primalproblem (P): \( \min_{x \in X} f(x) \)
• Dualproblem (D): \(\text{max}_{y \in Y} g(y)\) wobei \(g(y)\) abhängig ist von den Constraints des Primalproblems.
• Schwache Dualität: \(f(x) \ge g(y)\) für alle zulässigen \(x\) und \(y\).
• Starke Dualität: Falls \(P\) konvex und unter bestimmten Voraussetzungen, gilt \(f(x^*) = g(y^*)\) für optimale Lösungen \(x^*\) und \(y^*\).
• Lagrange-Dualität: Lagrange-Funktion \(L(x, \lambda) = f(x) + \sum_{i} \lambda_i h_i(x)\).

Markov-Ketten und -Prozesse

Definition:

Markov-Ketten und -Prozesse modellieren stochastische Systeme, bei denen der zukünftige Zustand nur vom gegenwärtigen Zustand abhängt, nicht aber von den vorherigen Zuständen (Markov-Eigenschaft).

Details:

• Diskrete Markov-Kette: Zustandsraum ist endlich oder abzählbar, Übergangswahrscheinlichkeiten gegeben durch Matrix \(\textbf{P}\).
• Übergangsmatrix \( \textbf{P} = (p_{ij}) \) mit \( p_{ij} = P(X_{n+1} = j | X_n = i) \).
• Stadionsverteilung \( \boldsymbol{u} \) ist stationär, wenn \( \boldsymbol{u} \textbf{P} = \boldsymbol{u} \).
• Kontinuierlicher Markov-Prozess: Zustände ändern sich kontinuierlich, beschrieben durch Chapman-Kolmogorov-Gleichungen.
• Ergodisch, wenn Langzeitverhalten unabhängig vom Startzustand ist.

Numerische Integration und Differentiation

Definition:

Numerische Methoden zur näherungsweisen Berechnung von Integralen und Ableitungen.

Details:

• Numerische Integration: Trapezregel, Simpson-Regel.
• Numerische Differentiation: Vorwärts-, Rückwärts- und Zentrische Differenzquotienten.
• Fehleranalyse und Stabilität.
• Teilung des Intervalls zur Verbesserung der Genauigkeit.
• Trapezregel: \(\text{Integral} \approx \frac{h}{2} (f(x_0) + 2 \sum_{i=1}^{n-1}f(x_i) + f(x_n))\)
• Simpson-Regel: \(\text{Integral} \approx \frac{h}{3} (f(a) + 4 \sum_{i=1}^{n/2}f(x_{2i-1}) + 2 \sum_{i=1}^{n/2-1}f(x_{2i}) + f(b))\)
• Vorwärtsdifferenz: \(f'(x) \approx \frac{f(x+h) - f(x)}{h}\)
• Rückwärtsdifferenz: \(f'(x) \approx \frac{f(x) - f(x-h)}{h}\)
• Zentrische Differenz: \(f'(x) \approx \frac{f(x+h) - f(x-h)}{2h}\)

Fehleranalyse und Stabilität von Algorithmen

Definition:

Analyse der Fehler, die während der Berechnungen von Algorithmen auftreten, und Untersuchung, wie kleine Änderungen der Eingabedaten die Ausgabe beeinflussen.

Details:

• Absoluter Fehler: \(|x - \tilde{x}|\)
• Relativer Fehler: \(\frac{|x - \tilde{x}|}{|x|}\)
• Vorwärtsfehler: Abweichung der berechneten Lösung von der exakten Lösung.
• Rückwärtsfehler: Minimale Änderung der Eingabedaten, die benötigt wird, um die berechnete Lösung als exakt erscheinen zu lassen.
• Stabilität: Algorithmus ist stabil, wenn kleine Fehler in den Daten nur zu kleinen Fehlern in der Ausgabe führen.
• Kondition einer Aufgabe: Maß für die Empfindlichkeit der Lösung gegenüber Änderungen der Eingabedaten.
• Gut konditioniertes Problem: Kleine Änderungen der Eingaben führen zu kleinen Änderungen der Ergebnisse.
• Schlecht konditioniertes Problem: Kleine Änderungen der Eingaben führen zu großen Änderungen der Ergebnisse.

Validierung und Verifikation von Modellen

Definition:

Glaubwürdigkeit und Genauigkeit von Modellen sicherstellen.

Details:

• Validierung: Überprüfung, ob das Modell die realen Prozesse korrekt beschreibt - Vergleich mit realen Daten
• Verifikation: Überprüfung, ob das Modell korrekt implementiert ist - Konsistenz und Logikprüfung
• Mathematische Tests und Simulationen zur Unterstützung
• Wichtig für Zuverlässigkeit von Prognosen und Ergebnissen
• Iterativer Prozess: Anpassen des Modells basierend auf Testergebnissen
• Wesentlich in wissenschaftlicher Forschung und technischer Anwendung

Benutzung von Optimierungssoftware wie Gurobi und CPLEX

Definition:

Verwendung von Gurobi und CPLEX zur Lösung und Analyse mathematischer Optimierungsprobleme.

Details:

• Häufig in der linearen und ganzzahligen Programmierung eingesetzt.
• Syntax: Variablen, Ziele, und Randbedingungen definieren.
• Nutzerfreundliche Schnittstellen für verschiedene Programmiersprachen (Python, MATLAB etc.).
• Leistungsfähig bei großskaligen Problemen durch effiziente Algorithmen.
• Beispielcode für Gurobi in Python:

import gurobipy as gpfrom gurobipy import GRB# Model erstellenm = gp.Model()# Variablen hinzufügenx = m.addVar(name='x')y = m.addVar(name='y')# Ziel setzenm.setObjective(x + y, GRB.MAXIMIZE)# Randbedingungen hinzufügenm.addConstr(x <= 10, name='c0')m.addConstr(y <= 5, name='c1')# Optimierung durchführenm.optimize()# Ergebnisse ausgebenfor v in m.getVars():    print('%s %g' % (v.varName, v.x))print('Obj: %g' % m.objVal)