Optimierte Entscheidungsfindung mit Python

Notation und Abkürzungen

Dieses Kapitel ist zum Nachschlagen gedacht, nicht zum Durchlesen. Schlagen Sie hier nach, sobald Ihnen ein Symbol oder ein Kürzel begegnet, das Sie nicht sicher zuordnen können.

1. Die Symbole der Optimierung

1.1 Grundgrößen jedes Modells

Symbol Sprechweise Bedeutung Beispiel aus dem Buch
x „iks“ Entscheidungsvariable(n) — das, was der Solver festlegen darf Anzahl gestarteter Trading-Bots (Kapitel 1)
\mathbf{x} „Vektor iks“ Alle Entscheidungsvariablen als Spaltenvektor \mathbf{x} = (x_1, \dots, x_n)^\top
n „en“ Anzahl der Entscheidungsvariablen 10 Aktien \Rightarrow n = 10
m „em“ Anzahl der Nebenbedingungen 3 Ressourcen \Rightarrow m = 3
\mathbf{c} „Vektor ze“ Kosten- bzw. Ertragsvektor der Zielfunktion Gewinn je Bot-Typ: (150, 250)^\top
\mathbf{A} „Matrix a“ Technologiematrix — wie viel Ressource verbraucht welche Variable Zeile „RAM“: (4, 6)
\mathbf{b} „Vektor be“ Kapazitätsvektor, „rechte Seite“ der Ungleichungen (40, 60)^\top vCPU und GB
f(\mathbf{x}) „ef von iks“ Zielfunktion — die eine Zahl, die bewertet wird Tagesgewinn in Euro
g_i(\mathbf{x}) „ge i von iks“ i-te Ungleichungs-Nebenbedingung, Form g_i(\mathbf{x}) \le 0 „RAM-Verbrauch minus 60 GB“
h_j(\mathbf{x}) „ha j von iks“ j-te Gleichungs-Nebenbedingung, Form h_j(\mathbf{x}) = 0 „Summe der Gewichte minus 1“
s_i „es i“ Schlupfvariable — ungenutzte Reserve der Ressource i 1 GB RAM übrig \Rightarrow s_2 = 1
y_i,\ \lambda_i „y i“, „lambda i“ Dualvariable / Schattenpreis der Bedingung i 33,33 € je zusätzlicher Prüfstunde
M „groß em“ Big-M — hinreichend große Konstante zum Ein-/Ausschalten von Bedingungen x_j \le M \cdot y_j
z_i,\ y_i Binärvariable \in \{0,1\} — Ja/Nein-Schalter „Position i wird eröffnet“
\mathcal{F} „kalligrafisches ef“ Zulässiger Bereich — Menge aller erlaubten Lösungen das Polyeder aus Kapitel 2
Z,\ Z^* „zet“, „zet Stern“ Zielfunktionswert bzw. optimaler Zielfunktionswert Z^* = 2300 €
\mathbf{x}^* „iks Stern“ Die optimale Lösung. Der Stern markiert immer „im Optimum“ \mathbf{x}^* = (7, 5)^\top

1.2 Mengen und Zahlbereiche

Symbol Bedeutung Praktische Folge
\mathbb{R} Reelle Zahlen (beliebig teilbar) Variable darf 3,7 sein — LP, schnell lösbar
\mathbb{R}^n n-Tupel reeller Zahlen Der Raum, in dem \mathbf{x} lebt
\mathbb{Z} Ganze Zahlen Variable muss 3 oder 4 sein — MILP, NP-schwer
\mathbb{N}_0 Natürliche Zahlen einschließlich 0 Stückzahlen, nie negativ
\{0, 1\} Nur zwei Werte Ja/Nein-Entscheidung
\in „ist Element von“ x \in \mathbb{Z}: „x ist ganzzahlig“
\forall „für alle“ w_i \ge 0\ \forall i: jedes Gewicht ist nichtnegativ
\exists „es existiert“ seltener; „es gibt mindestens ein …“
\subseteq „ist Teilmenge von“ \mathcal{C} \subseteq \mathbb{R}^n
[a, b] Geschlossenes Intervall \theta \in [0,1]: \theta liegt zwischen 0 und 1

1.3 Operatoren und Schreibweisen

Symbol Bedeutung Lesehilfe
\sum_{i=1}^n a_i Summe „addiere a_1 bis a_n“
\mathbf{c}^\top \mathbf{x} Skalarprodukt „c_1 x_1 + c_2 x_2 + \dots“ — eine einzige Zahl
^\top Transponiert dreht Zeilen und Spalten; macht aus Spalten- einen Zeilenvektor
\mathbf{A}\mathbf{x} Matrix-Vektor-Produkt „berechne alle Ressourcenverbräuche auf einmal“
\min_x,\ \max_x Minimum/Maximum über x „wähle x so, dass … kleinst-/größtmöglich wird“
\arg\min Argument des Minimums nicht der Wert, sondern die Stelle des Minimums
\nabla f „Nabla ef“, Gradient Vektor aller partiellen Ableitungen — zeigt bergauf
\partial Z / \partial b_i Partielle Ableitung „wie ändert sich Z, wenn nur b_i sich ändert?“
\Vert \mathbf{v} \Vert_1 L_1-Norm Summe der Beträge: \vert v_1\vert + \vert v_2\vert + \dots
\Vert \mathbf{v} \Vert_2 L_2-Norm (euklidisch) die gewöhnliche Länge eines Pfeils
\mathbf{P} \succeq 0 positiv semidefinit alle Eigenwerte \ge 0; Funktion ist konvex
\mathbf{P} \succ 0 positiv definit alle Eigenwerte > 0; Funktion ist streng konvex
\mathbb{E}[\cdot] Erwartungswert gewichteter Mittelwert über alle Szenarien
\mathbb{1} oder \mathbf{1} Einsvektor (1,1,\dots,1)^\top; \mathbf{1}^\top\mathbf{w} ist die Summe aller w_i
\mathbf{I} Einheitsmatrix Diagonale 1, sonst 0
s.t. / u. d. N. subject to / unter den Nebenbedingungen leitet die Restriktionen ein

1.4 Symbole der Finanzkapitel (Teil IV)

Symbol Bedeutung Einheit / typischer Wert
\mathbf{w} Portfoliogewichte — Kapitalanteile je Titel dimensionslos, Summe = 1
w_i Anteil von Titel i 0{,}15 \equiv 15\,\%
\boldsymbol{\mu} „mü“ — Vektor der erwarteten Renditen z. B. 0{,}11 = 11 % p. a.
\boldsymbol{\Sigma} „Sigma“ — Kovarianzmatrix der Renditen N \times N, Einheit Rendite²
\sigma „sigma“ — Volatilität (Standardabweichung) 0{,}20 = 20 % p. a.
\sigma^2 Varianz Quadrat der Volatilität
\mathbf{S} Stichproben-Kovarianzmatrix (aus Daten geschätzt) verrauscht
\mathbf{F} Shrinkage-Target — strukturierte Vergleichsmatrix verzerrt, aber stabil
\delta „delta“ — Shrinkage-Intensität \in [0,1], z. B. 0{,}18
r_f risk-free rate, risikoloser Zins z. B. 0{,}03 = 3 % p. a.
R_{i,t} Diskrete Rendite von Titel i am Tag t P_t/P_{t-1} - 1
r_{i,t} Logarithmische Rendite (stetige Rendite) \ln(P_t/P_{t-1})
P_{i,t} Kurs (bereinigter Schlusskurs) von Titel i in Währungseinheiten
\lambda Risikoaversion / Gewichtung des Risikoterms Modellparameter, frei wählbar
\alpha Konfidenzniveau bei VaR/CVaR 0{,}95 = „schlechteste 5 % der Tage“
\gamma Hilfsvariable, schätzt den VaR (Kapitel 20); Diskontfaktor (Kapitel 13) kontextabhängig
\eta „eta“ — Marktimpact-Koeffizient Kapitel 13, Almgren-Chriss
X_t Verbleibender Aktienbestand zum Zeitpunkt t Kapitel 13
n_t In Periode t verkaufte Stückzahl Kapitel 13
S (kursiv, Skalar) Anzahl der Szenarien Kapitel 12, Kapitel 20
T Anzahl Zeitschritte bzw. Handelstage 252 Handelstage/Jahr
N Anzahl Titel im Universum z. B. 10 Aktien

1.5 Symbole der Verfahrenskapitel (Teil II und III)

Diese Zeichen kommen erst in den Kapiteln vor, die über das klassische LP hinausgehen.

Symbol Sprechweise Bedeutung Kapitel
\pi „pi“ Reihenfolge (Permutation): \pi(k) ist der Auftrag, der als k-ter läuft Kapitel 9
\Delta „delta“ Zugbewertung — um wie viel ein Nachbarschaftszug die Lösung verschlechtert (\Delta > 0) oder verbessert (\Delta \le 0) Kapitel 9
T „te“ Temperatur im Simulated Annealing — steuert, wie oft eine Verschlechterung angenommen wird Kapitel 9
e^{-\Delta/T} Annahmewahrscheinlichkeit (Metropolis-Kriterium): kleine Verschlechterungen fast immer, große fast nie Kapitel 9
\pi_i „pi i“ Dualpreis der Bedingung i im Master-LP — der Preis, mit dem das Pricing rechnet Kapitel 10
a_i „a i“ Wie oft Stück i in einem Schnittmuster vorkommt (eine Spalte des Masters) Kapitel 10
1 - \sum_i \pi_i a_i Reduzierte Kosten einer neuen Spalte. Negativ heißt: Das Muster lohnt sich, nimm es auf Kapitel 10
„x dominiert y“ Pareto-Dominanz: x ist in keinem Ziel schlechter und in mindestens einem besser Kapitel 14
\varepsilon „epsilon“ Schranke im \varepsilon-Constraint-Verfahren: ein Ziel wird zur Nebenbedingung, e(x) \le \varepsilon Kapitel 14
\hat{d}_t „d Dach t“ Prognostizierter Wert — das Dach unterscheidet die Schätzung vom später eintretenden Ist-Wert d_t Kapitel 15
a_{k,t} „a k t“ Anfahrvariable: Anlage k wird in Stunde t angefahren Kapitel 17
u_{k,t} „u k t“ Einsatzvariable: Anlage k läuft in Stunde t Kapitel 17
L_k „el k“ Mindestlaufzeit von Anlage k in Stunden Kapitel 17
\tau „tau“ Laufender Zeitindex innerhalb eines Fensters — dort, wo t schon den Fensteranfang bezeichnet Kapitel 17

⚠️ Achtung, Doppelbelegungen. In der Literatur — und deshalb auch hier — tragen einige Buchstaben je nach Kapitel verschiedene Bedeutungen. Die wichtigsten Fälle: \lambda ist in Kapitel 5 und Kapitel 11 ein Lagrange-Multiplikator/Schattenpreis, in Kapitel 19 und Kapitel 20 ein frei gewählter Risikoaversionsparameter. \gamma ist in Kapitel 13 der Diskontfaktor, in Kapitel 20 die VaR-Hilfsvariable. S bezeichnet als Matrix \mathbf{S} die Stichprobenkovarianz, als Skalar S die Szenarienzahl. \pi ist in Kapitel 9 eine Reihenfolge, in Kapitel 10 ein Dualpreis — beide Bedeutungen sind so verbreitet, dass ein Ausweichbuchstabe mehr verwirren als helfen würde. Der Kontext ist jeweils eindeutig, und die Kapitel weisen an der betreffenden Stelle darauf hin.

2. Abkürzungen — vollständig ausgeschrieben

2.1 Problemklassen und Verfahren

Kürzel Ausgeschrieben Deutsch Kapitel
OR Operations Research Unternehmensforschung / mathematische Entscheidungsoptimierung Kapitel 1
LP Linear Program(ming) Lineare Programmierung/Optimierung Kapitel 5
MILP Mixed-Integer Linear Program(ming) Gemischt-ganzzahlige lineare Optimierung Kapitel 6
MIP Mixed-Integer Program(ming) Oberbegriff, meist synonym zu MILP Kapitel 6
IP Integer Program(ming) Rein ganzzahlige Optimierung Kapitel 6
QP Quadratic Program(ming) Quadratische Optimierung Kapitel 11
MIQP Mixed-Integer Quadratic Program(ming) Ganzzahlig-quadratische Optimierung Kapitel 19
NLP Nonlinear Program(ming) Nichtlineare Optimierung Kapitel 11
MINLP Mixed-Integer Nonlinear Program(ming) Ganzzahlig-nichtlineare Optimierung Kapitel 3
CP Constraint Programming Bedingungsprogrammierung Kapitel 7
SAT Boolean Satisfiability Problem Erfüllbarkeitsproblem der Aussagenlogik Kapitel 7
CP-SAT Constraint Programming über SAT-Techniken Solver-Name von Google OR-Tools Kapitel 7
CDCL Conflict-Driven Clause Learning konfliktgetriebenes Klausellernen Kapitel 7
DP Dynamic Programming Dynamische Programmierung Kapitel 13
B&B Branch and Bound Verzweigen und Beschränken Kapitel 6
B&C Branch and Cut Verzweigen mit Schnittebenen Kapitel 6
KKT Karush–Kuhn–Tucker (Bedingungen) Optimalitätsbedingungen bei Restriktionen Kapitel 11
SLSQP Sequential Least Squares Programming sequentielle quadratische Optimierung Kapitel 11
RMT Random Matrix Theory Zufallsmatrizentheorie Kapitel 18
SA Simulated Annealing Simulierte Abkühlung — Metaheuristik, die Verschlechterungen mit fallender Wahrscheinlichkeit zulässt Kapitel 9
LNS Large Neighborhood Search Große Nachbarschaftssuche: Teil der Lösung verwerfen, Rest exakt neu bauen Kapitel 9
CG Column Generation Spaltengenerierung — Variablen erst erzeugen, wenn sie sich lohnen Kapitel 10
IIS Irreducible Infeasible Subset Kleinste widersprüchliche Teilmenge von Bedingungen Anhang C
MSE Mean Squared Error Mittlerer quadratischer Fehler — das Standardmaß für Prognosegüte Kapitel 15

2.2 Probleme mit Eigennamen

Kürzel Ausgeschrieben Deutsch Kapitel
TSP Traveling Salesperson Problem Problem des Handlungsreisenden Kapitel 8
VRP Vehicle Routing Problem Tourenplanungsproblem Kapitel 8
CVRP Capacitated VRP VRP mit Fahrzeugkapazitäten Kapitel 8
VRPTW VRP with Time Windows VRP mit Zeitfenstern Kapitel 8
CVRPTW Capacitated VRP with Time Windows mit Kapazitäten und Zeitfenstern Kapitel 8
MCNFP Minimum-Cost Network Flow Problem Kostenminimales Flussproblem Kapitel 8
MTZ Miller–Tucker–Zemlin (Formulierung) Kurzzyklus-Eliminierung Kapitel 8
JSSP Job-Shop Scheduling Problem Werkstattfertigungs-Reihenfolgeproblem Kapitel 7

2.3 Finanz- und Risikokennzahlen

Kürzel Ausgeschrieben Deutsch / Bedeutung Kapitel
MPT Modern Portfolio Theory Moderne Portfoliotheorie (Markowitz) Kapitel 19
GMV Global Minimum Variance (Portfolio) Portfolio kleinstmöglicher Varianz Kapitel 19
MVO Mean-Variance Optimization Erwartungswert-Varianz-Optimierung Kapitel 19
SR Sharpe Ratio Überrendite je Einheit Volatilität Kapitel 19
VaR Value at Risk Verlustschwelle bei gegebener Wahrscheinlichkeit Kapitel 20
CVaR Conditional Value at Risk mittlerer Verlust jenseits des VaR Kapitel 20
ES Expected Shortfall anderes Wort für CVaR Kapitel 20
CAGR Compound Annual Growth Rate durchschnittliche jährliche Wachstumsrate Kapitel 21
MDD Maximum Drawdown größter Rückgang vom Höchststand Kapitel 21
LW Ledoit–Wolf (Shrinkage) Schrumpfungsverfahren für Kovarianzmatrizen Kapitel 18
p. a. per annum pro Jahr Teil IV
bp Basispunkt 0,01 Prozentpunkt; 15 bp = 0,15 % Kapitel 20, Kapitel 21

2.4 Software, Solver und Schnittstellen

Kürzel Ausgeschrieben Was es ist Lizenz
HiGHS High Performance General-purpose Solver LP-, MILP- und QP-Solver in C++ Open Source (MIT)
OR-Tools Google Operations Research Tools Solver-Sammlung (CP-SAT, Routing, Wrapper) Open Source (Apache 2.0)
CVXPY Convex Python Modellierungssprache für konvexe Optimierung Open Source (Apache 2.0)
SciPy Scientific Python Wissenschaftliches Python-Paket; scipy.optimize liefert LP- (über HiGHS), Zuordnungs- (linear_sum_assignment) und NLP-Solver (minimize) Open Source (BSD)
GLOP Google Linear Optimizer LP-Solver in OR-Tools Open Source
SCIP Solving Constraint Integer Programs MILP/MINLP-Solver akademisch frei
CBC Coin-or Branch and Cut MILP-Solver des COIN-OR-Projekts Open Source
GLPK GNU Linear Programming Kit LP/MILP-Solver Open Source (GPL)
OSQP Operator Splitting Quadratic Program QP-Solver Open Source
ECOS Embedded Conic Solver konischer Solver Open Source
SCS Splitting Conic Solver konischer Solver Open Source
IPOPT Interior Point Optimizer NLP-Solver Open Source (EPL)
Gurobi, CPLEX, Xpress — kommerzielle Hochleistungs-Solver kostenpflichtig
API Application Programming Interface Programmierschnittstelle —
DSL Domain-Specific Language fachspezifische Sprache (hier: Modellierungssprache) —
CSR Compressed Sparse Row Speicherformat für dünnbesetzte Matrizen —
GIL Global Interpreter Lock Pythons Sperre, die echte Parallelität von Python-Code verhindert — Solverbibliotheken in C++ geben sie frei (Kapitel 23) —
JSON JavaScript Object Notation Textformat für strukturierte Daten; Austauschformat des Optimierungsdienstes —
RHS Right-Hand Side rechte Seite einer (Un-)Gleichung, der Vektor \mathbf{b} —
FFI Foreign Function Interface Aufruf von C/C++-Code aus Python —

2.5 Begriffe aus dem Solver-Alltag

Kürzel / Begriff Bedeutung Was Sie tun sollten
OPTIMAL Beweisbar beste Lösung gefunden Nichts — alles gut
FEASIBLE Zulässige Lösung gefunden, Optimalität nicht bewiesen Zeitlimit erhöhen oder Gap akzeptieren
INFEASIBLE Keine Lösung erfüllt alle Bedingungen Anhang C: Diagnose durchführen
UNBOUNDED Zielfunktion unbeschränkt verbesserbar Fehlende Nebenbedingung — Modell prüfen
MIP-Gap Relativer Abstand beste Lösung ↔︎ beste Schranke 1–2 % sind in der Praxis meist genug
Incumbent Beste bisher gefundene zulässige Lösung Referenz für das Pruning
Relaxation Modell mit weggelassener Ganzzahligkeit liefert die Schranke
Warm Start Solver startet von bekannter Lösung beschleunigt wiederholte Läufe
Slack Schlupf, ungenutzte Kapazität Slack = 0 → Engpass
Lookahead-Bias Nutzung von Daten aus der Zukunft Backtest ist wertlos — Kapitel 22

3. Konventionen in diesem Buch

Vektoren sind grundsätzlich Spaltenvektoren und werden fett gesetzt: \mathbf{x}. Ein transponierter Vektor \mathbf{x}^\top ist eine Zeile. Skalare bleiben mager: n, Z.

Matrizen sind fett und groß: \mathbf{A}, \boldsymbol{\Sigma}.

Der Stern markiert immer Optimalwerte: \mathbf{x}^*, Z^*, \lambda^*.

Minimierung ist die Standardform. Jede Maximierung lässt sich durch Vorzeichenwechsel in eine Minimierung überführen: \max f(\mathbf{x}) = -\min\,(-f(\mathbf{x})). Die meisten Solver — auch scipy.optimize.linprog — minimieren intern. Wer das vergisst, erhält systematisch das Gegenteil des Gewünschten; siehe Abschnitt 5.7.

Dezimaltrennzeichen. Im Fließtext und in Formeln steht das deutsche Komma (3{,}14), in Code und Programmausgaben der englische Punkt (3.14) — Python kennt nichts anderes.

Code-Sprache. Kommentare und Ausgaben der Beispielprogramme sind deutsch, Bezeichner überwiegend englisch, weil das der Konvention der verwendeten Bibliotheken entspricht und die Programme so anschlussfähig an die Originaldokumentation bleiben.

Anglizismen. Fachbegriffe werden bei der ersten Verwendung deutsch eingeführt und der englische Originalbegriff kursiv in Klammern ergänzt, weil Sie ihn für die Recherche brauchen: „zulässiger Bereich (feasible region)“.