Kapitel 13: Dynamische Programmierung — Die Bellman-Gleichung und Order-Execution

13.1 In 5 Minuten gelöst

Der optimale Weg beginnt mit dem teureren ersten Abschnitt. Start → Süd kostet 6 Minuten, Start → Nord nur 4. Wer vorne spart, landet bei 21 Minuten statt 14 — 50 % mehr:

Der Grund steht in der zweiten Ausgabezeile. Restkosten je Ort ist die Wertfunktion: Sie sagt für jeden Ort, was der ganze Rest von dort aus noch kostet, wenn man ab dort optimal weiterfährt. Und dort steht das Entscheidende: Von Nord aus sind es noch 17 Minuten, von Süd nur 8. Die vier gesparten Minuten am Anfang werden später mit neun zusätzlichen bezahlt.

🎯 Merksatz Eine Entscheidung ist nie für sich zu bewerten, sondern nur zusammen mit allem, was danach kommt. Genau das leistet die Wertfunktion: Sie fasst die gesamte Zukunft eines Zustands in einer einzigen Zahl zusammen. Und weil man die Zukunft kennen muss, bevor man die Gegenwart bewerten kann, rechnet dynamische Programmierung rückwärts.

Warum funktioniert das? Weil man den Rest des Weges nicht neu durchdenken muss, sobald man einmal an einem Ort steht: Wie man dorthin gekommen ist, ist für die Zukunft egal. Diese Eigenschaft heißt Bellmansches Optimalitätsprinzip und ist der Grund, warum aus einem Problem mit exponentiell vielen Wegen eine Rechnung mit wenigen Zeilen wird. Bei fünf Orten fällt das kaum auf — bei fünfzig ist es der Unterschied zwischen Sekunden und Jahren.

13.2 Lernziele

Nach diesem Kapitel können Sie …

1. … das Bellmansche Optimalitätsprinzip formulieren und erklären, warum es gilt.
2. … Zustand, Stufe, Aktion und Wertfunktion für ein gegebenes Problem benennen.
3. … eine Rückwärtsinduktion von Hand für ein kleines Problem durchführen.
4. … das Almgren-Chriss-Ausführungsproblem lösen und die Lösung interpretieren.
5. … einschätzen, wann DP funktioniert und wann der „Fluch der Dimensionalität“ zuschlägt.
6. … die Wertfunktion als Nachschlagetabelle lesen: Sie liefert keine Planfolge, sondern eine Regel, die auch bei Abweichungen gilt.
7. … einen Zustandsraum auf Vollständigkeit prüfen und erkennen, wann eine Kostenart Vorgeschichte erfordert.

13.3 Das Bellmansche Optimalitätsprinzip

Richard Bellman formulierte 1957 das Grundprinzip der Dynamischen Programmierung (DP):

Optimalitätsprinzip. Eine optimale Strategie hat die Eigenschaft, dass — unabhängig vom Anfangszustand und der Anfangsentscheidung — die verbleibenden Entscheidungen eine optimale Strategie bezüglich des Zustands bilden, der aus der ersten Entscheidung resultiert.

Ohne Fachsprache: Jedes Teilstück einer optimalen Route ist selbst eine optimale Route. Wenn der beste Weg von Hamburg nach München über Kassel führt, dann ist der Teil von Kassel nach München auch der beste Weg von Kassel nach München. Sonst könnte man ihn ersetzen und wäre insgesamt besser.

Die vier Bausteine eines DP-Modells

🎯 Die Kunst liegt in der Zustandsdefinition Der Zustand muss alles enthalten, was für die Zukunft relevant ist — und nichts mehr. Zu wenig: Das Modell ist falsch (Markov-Eigenschaft verletzt). Zu viel: Der Zustandsraum explodiert. Diese Abwägung ist die eigentliche Modellierungsleistung bei DP.

Die Bellman-Gleichung

V_t(S_t) = \min_{a_t\in\mathcal{A}(S_t)}\Big\{\,C(S_t,a_t) \;+\; \gamma\cdot\mathbb{E}\big[V_{t+1}(S_{t+1})\mid S_t,a_t\big]\Big\}

mit der Endbedingung V_T(S_T) = g(S_T).

📐 Formel-Lesehilfe * V_t(S_t) — „Was kostet mich der Rest, wenn ich zum Zeitpunkt t im Zustand S_t bin und ab jetzt optimal handle?“ * C(S_t,a_t) — die sofortigen Kosten der Aktion a_t. * V_{t+1}(S_{t+1}) — die Restkosten danach, wieder optimal. * \gamma — Diskontfaktor (bei kurzen Horizonten meist \gamma = 1). * \mathbb{E}[\cdot] — Erwartungswert, falls der Übergang zufällig ist.

Ohne Formel gesagt: „Der Wert von hier ist: die Kosten des nächsten Schritts plus der Wert von dort — und zwar für denjenigen nächsten Schritt, bei dem diese Summe am kleinsten ist.“

Warum rückwärts? Weil V_{t+1} bekannt sein muss, bevor man V_t berechnen kann. Am Ende (t = T) ist der Wert bekannt — dort fängt man an und arbeitet sich nach vorn.

✏️ Handrechnung 13.1: Rückwärtsinduktion von Hand

Problem: Sie müssen 3 Einheiten in 2 Perioden verkaufen. Sofortkosten je Periode: C(n) = n^2 (großer Verkauf drückt den Preis überproportional). In der letzten Periode muss alles weg.

Schritt 1 — Endstufe t = 2: Es sind keine Perioden mehr übrig, also V_2(0) = 0, alle anderen Zustände sind unzulässig.

Schritt 2 — Stufe t = 1 (letzte Verkaufsperiode, alles muss weg):

Zustand X_1	erzwungene Aktion	Kosten	V_1
0	0	0	0
1	1	1	1
2	2	4	4
3	3	9	9

Schritt 3 — Stufe t = 0 (Start mit X_0 = 3), alle Aktionen prüfen:

Aktion n_0	Sofortkosten n_0^2	Rest X_1	V_1(X_1)	Summe
0	0	3	9	9
1	1	2	4	5
2	4	1	1	5
3	9	0	0	9

Ergebnis: V_0(3) = 5, erreicht durch n_0 = 1 (dann n_1 = 2) oder n_0 = 2 (dann n_1 = 1). Zwei gleichwertige Optima.

Die Lehre: Alles auf einmal zu verkaufen kostet 9, gleichmäßiges Aufteilen nur 5. Das ist der Kern des Ausführungsproblems: Bei überproportionalen Kosten lohnt sich Stückelung. Und beachten Sie, dass wir nur 4 + 4 = 8 Kombinationen bewertet haben statt aller Verkaufspfade — bei größeren Problemen ist dieser Unterschied dramatisch.

#!/usr/bin/env python3

# Bellman_Minimalbeispiel.py
"""
Kapitel Dynamische Programmierung: Die Handrechnung zur Rueckwaertsinduktion als Code.
Zeigt die Wertfunktionstabelle und die optimale Politik Schritt fuer Schritt.
"""

import numpy as np

GESAMT = 3          # zu verkaufende Einheiten
PERIODEN = 2        # Anzahl Verkaufsperioden


def kosten(menge: int) -> float:
    """Ueberproportionale Marktauswirkung: doppelte Menge kostet vierfach."""
    return float(menge ** 2)


def loese_rueckwaerts():
    # V[t, x] = minimale Restkosten, wenn zu Beginn von Periode t noch x Stueck offen sind
    V = np.full((PERIODEN + 1, GESAMT + 1), np.inf)
    politik = np.zeros((PERIODEN, GESAMT + 1), dtype=int)

    # Endbedingung: nach der letzten Periode darf nichts mehr offen sein
    V[PERIODEN, 0] = 0.0

    print("=" * 70)
    print("  RUECKWAERTSINDUKTION SCHRITT FUER SCHRITT")
    print("=" * 70)

    for t in range(PERIODEN - 1, -1, -1):
        letzte_periode = (t == PERIODEN - 1)
        print(f"\nStufe t = {t}" + ("  (letzte Periode: alles muss weg)" if letzte_periode
                                    else "  (freie Wahl der Menge)"))
        print(f"  {'Zustand x':>10} | {'beste Aktion':>12} | {'Sofortkosten':>13} | "
              f"{'V[t+1]':>9} | {'V[t]':>8}")
        print("  " + "-" * 62)

        for x in range(GESAMT + 1):
            aktionen = [x] if letzte_periode else range(x + 1)
            bester_wert, beste_aktion, beste_teile = np.inf, 0, (0.0, 0.0)

            for n in aktionen:
                rest = x - n
                sofort = kosten(n)
                zukunft = V[t + 1, rest]
                gesamt = sofort + zukunft
                if gesamt < bester_wert:
                    bester_wert, beste_aktion = gesamt, n
                    beste_teile = (sofort, zukunft)

            V[t, x] = bester_wert
            politik[t, x] = beste_aktion
            print(f"  {x:>10} | {beste_aktion:>12} | {beste_teile[0]:>13.1f} | "
                  f"{beste_teile[1]:>9.1f} | {bester_wert:>8.1f}")

    return V, politik


if __name__ == "__main__":
    V, politik = loese_rueckwaerts()

    # --- Vorwaertspfad: der optimalen Politik folgen ---------------------
    print("\n" + "=" * 70)
    print("  OPTIMALER PFAD (Vorwaertssimulation)")
    print("=" * 70)
    bestand = GESAMT
    gesamtkosten = 0.0
    for t in range(PERIODEN):
        aktion = politik[t, bestand]
        gesamtkosten += kosten(aktion)
        print(f"  Periode {t}: Bestand {bestand} -> verkaufe {aktion} "
              f"(Kosten {kosten(aktion):.1f}) -> Rest {bestand - aktion}")
        bestand -= aktion

    print(f"\n  Gesamtkosten: {gesamtkosten:.1f}  (V[0, {GESAMT}] = {V[0, GESAMT]:.1f})")
    assert abs(gesamtkosten - V[0, GESAMT]) < 1e-9, "Pfadkosten != Wertfunktion!"

    # --- Vergleich mit naiven Strategien ---------------------------------
    alles_sofort = kosten(GESAMT)
    print(f"\n  Zum Vergleich - alles in Periode 0 verkaufen: {alles_sofort:.1f}")
    print(f"  Ersparnis durch Stueckelung: {alles_sofort - gesamtkosten:.1f} "
          f"({(1 - gesamtkosten/alles_sofort)*100:.0f} %)")
    print("=" * 70)

13.4 Das Almgren-Chriss-Problem: optimale Orderausführung

Ein klassisches OR-Problem an Börsen: Ein institutioneller Händler muss X_0 = 100\,000 Aktien innerhalb von T Handelsperioden verkaufen.

Der Zielkonflikt:

1. Marktauswirkung (market impact, Slippage). Verkauft man zu schnell, bricht das Orderbuch ein — der Ausführungspreis verschlechtert sich. Diese Kosten wachsen überproportional mit der Ordergröße.
2. Zeitrisiko (timing risk). Wartet man zu lange, schwankt der Marktpreis. Je größer der noch offene Restbestand, desto mehr Geld liegt im Risiko.

Das Modell nach Almgren und Chriss (2000) minimiert die Summe aus beidem:

C(n_t, X_t) = \underbrace{\eta\,n_t^2}_{\text{Marktauswirkung}} \;+\; \underbrace{\lambda\,\sigma^2 X_t^2}_{\text{Risiko des Restbestands}}

📐 Formel-Lesehilfe * n_t — in Periode t verkaufte Stückzahl. Quadriert, weil doppelte Menge mehr als doppelten Preisdruck erzeugt. * \eta („eta“) — Slippage-Koeffizient. Wie stark reagiert der Markt auf Volumen? * X_t — Restbestand nach dem Verkauf. Quadriert, weil Varianz quadratisch mit der Positionsgröße wächst. * \lambda — Risikoaversion: Wie sehr stört mich Schwankung im Vergleich zu Slippage? * \sigma — Volatilität je Periode.

Ohne Formel gesagt: „Schnell verkaufen kostet Preisabschlag. Langsam verkaufen kostet Nervenkitzel. Finde die Mitte.“

Die zwei Extremfälle: * \lambda \to 0 (risikoneutral): gleichmäßiges Aufteilen auf alle Perioden minimiert \sum n_t^2 bei fester Summe. * \lambda \to \infty (extrem risikoscheu): sofort alles verkaufen, um kein Risiko zu tragen.

⚠️ Zur Kalibrierung des Risikoparameters

Ein häufiger Fehler ist ein undokumentierter Skalierungsfaktor im Risikoterm, etwa:

holding_risk = risk_aversion * (sigma_period ** 2) * (remaining ** 2) * 1e5

Woher eine solche Zahl kommt, bleibt dann unklar. Faktisch wirkt sie als versteckte Erhöhung der Risikoaversion um fünf Größenordnungen — ein Parameter wie risk_aversion = 1e-6 würde dann in Wahrheit 0{,}1 bedeuten. Solche „magischen Zahlen“ machen ein Modell unkalibrierbar: Niemand kann sagen, ob 1e-6 viel oder wenig ist.

Der Parameter lässt sich stattdessen herleiten. Beide Kostenterme werden in Euro gerechnet: * Marktauswirkung: \eta \cdot n_t^2 mit \eta in €/Stück². * Risiko: \tfrac{\lambda}{2}\cdot \sigma_{\text{Periode}}^2 \cdot P_0^2 \cdot X_t^2 — die Varianz des Werts der offenen Position, multipliziert mit der Risikoaversion.

Durch die Multiplikation mit P_0^2 (dem Quadrat des Aktienkurses) stimmen die Einheiten, und \lambda wird interpretierbar: Es ist der Preis, den man je Einheit Wertvarianz zu zahlen bereit ist.

#!/usr/bin/env python3

# Mehrperiodige_Order_Execution.py
"""
Kapitel Dynamische Programmierung: Dynamische Programmierung fuer optimale Orderausfuehrung
(Almgren-Chriss-Rahmen, geloest per Rueckwaertsinduktion).

Eigenschaften:
  * Risikoterm sauber hergeleitet ueber den Aktienkurs P0 (Einheiten: EUR),
    ohne undokumentierte Skalierungsfaktoren
  * Vergleich mit der analytischen Almgren-Chriss-Loesung
  * Vergleich mit naiven Strategien (alles sofort / gleichmaessig)
  * Sensitivitaet gegenueber der Risikoaversion
"""

import os

import numpy as np
import pandas as pd
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

OUTPUT_DIR = os.path.join(os.path.dirname(os.path.abspath(__file__)), "output")
os.makedirs(OUTPUT_DIR, exist_ok=True)

# --- Parameter -------------------------------------------------------------
GESAMTBESTAND = 100_000        # X_0, zu verkaufende Aktien
PERIODEN = 5                   # T Handelsperioden
KURS = 50.0                    # P_0 in EUR, zur Skalierung des Risikoterms
ETA = 2.5e-6                   # EUR je Stueck^2 (Slippage-Koeffizient)
VOLA_JAHR = 0.30               # 30 % p.a.
HANDELSSTUNDEN_JAHR = 252 * 6.5
RISIKOAVERSION = 1e-5          # 1/EUR; kalibriert, siehe Kommentar unten
SCHRITTWEITE = 1000            # Diskretisierung des Zustandsraums

# Kalibrierungshinweis: Die dimensionslose Kennzahl des Modells ist
#     kappa_tilde^2 = lambda * sigma_periode^2 * P0^2 / eta
# Sie entscheidet ueber den Charakter der Loesung:
#     << 1  -> praktisch gleichmaessige Aufteilung (Risiko spielt keine Rolle)
#     ~  1  -> ausgewogener Kompromiss  <- hier: 0.55
#     >> 1  -> fast alles sofort verkaufen
# Genau diese Interpretierbarkeit geht mit einem undokumentierten
# Skalierungsfaktor verloren.

VOLA_PERIODE = VOLA_JAHR / np.sqrt(HANDELSSTUNDEN_JAHR)


def periodenkosten(verkauf: float, restbestand: float) -> float:
    """
    Sofortkosten einer Periode in EUR:
      (1) Marktauswirkung: eta * n^2
      (2) Risiko des Restbestands: lambda/2 * sigma^2 * P0^2 * X^2
          -> P0^2 macht aus "Stueck^2" einen EUR^2-Wert; lambda hat damit
             die Einheit 1/EUR und ist interpretierbar.
    """
    marktauswirkung = ETA * verkauf ** 2
    wertvarianz = (VOLA_PERIODE ** 2) * (KURS ** 2) * (restbestand ** 2)
    risiko = 0.5 * RISIKOAVERSION * wertvarianz
    return marktauswirkung + risiko


def loese_dp():
    """Rueckwaertsinduktion ueber den diskretisierten Zustandsraum."""
    zustaende = np.arange(0, GESAMTBESTAND + SCHRITTWEITE, SCHRITTWEITE)
    anzahl = len(zustaende)

    V = np.full((PERIODEN + 1, anzahl), np.inf)
    politik = np.zeros((PERIODEN, anzahl), dtype=int)
    V[PERIODEN, 0] = 0.0                     # am Ende muss alles verkauft sein

    for t in range(PERIODEN - 1, -1, -1):
        for idx, bestand in enumerate(zustaende):
            if t == PERIODEN - 1:
                moegliche = [bestand]        # letzte Periode: Rest muss weg
            else:
                moegliche = zustaende[zustaende <= bestand]

            bester_wert, beste_aktion = np.inf, 0
            for verkauf in moegliche:
                rest = bestand - verkauf
                rest_idx = int(round(rest / SCHRITTWEITE))
                gesamt = periodenkosten(verkauf, rest) + V[t + 1, rest_idx]
                if gesamt < bester_wert:
                    bester_wert, beste_aktion = gesamt, int(verkauf)

            V[t, idx] = bester_wert
            politik[t, idx] = beste_aktion

    return zustaende, V, politik


def analytische_loesung():
    """
    Geschlossene Almgren-Chriss-Loesung fuer den kontinuierlichen Fall.
    Der optimale Pfad ist X_t = X_0 * sinh(kappa*(T-t)) / sinh(kappa*T)
    mit kappa = arccosh(tilde_kappa^2/2 + 1), tilde_kappa^2 = lambda*sigma^2*P0^2/eta.
    Dient hier als unabhaengige Kontrolle des DP-Ergebnisses.
    """
    kappa_tilde_quadrat = (RISIKOAVERSION * (VOLA_PERIODE ** 2) * (KURS ** 2)) / ETA
    kappa = np.arccosh(kappa_tilde_quadrat / 2.0 + 1.0)
    if kappa < 1e-12:                        # Grenzfall: risikoneutral -> linear
        return np.linspace(GESAMTBESTAND, 0, PERIODEN + 1)
    t = np.arange(PERIODEN + 1)
    return GESAMTBESTAND * np.sinh(kappa * (PERIODEN - t)) / np.sinh(kappa * PERIODEN)


def bewerte_pfad(bestaende):
    """Gesamtkosten eines beliebigen Bestandspfades."""
    summe = 0.0
    for t in range(len(bestaende) - 1):
        verkauf = bestaende[t] - bestaende[t + 1]
        summe += periodenkosten(verkauf, bestaende[t + 1])
    return summe


if __name__ == "__main__":
    zustaende, V, politik = loese_dp()

    # --- Vorwaertspfad der optimalen Politik -----------------------------
    bestand = GESAMTBESTAND
    verlauf = [bestand]
    verkaeufe = []
    for t in range(PERIODEN):
        idx = int(round(bestand / SCHRITTWEITE))
        verkauf = politik[t, idx]
        verkaeufe.append(verkauf)
        bestand -= verkauf
        verlauf.append(bestand)

    print("=" * 84)
    print("   OPTIMALE MEHRPERIODIGE ORDER-EXECUTION (BELLMAN DP)")
    print("=" * 84)
    print(f"Gesamtvolumen:       {GESAMTBESTAND:,} Stueck zu {KURS:.2f} EUR "
          f"= {GESAMTBESTAND*KURS:,.0f} EUR Positionswert")
    print(f"Zeithorizont:        {PERIODEN} Handelsperioden")
    print(f"Volatilitaet:        {VOLA_JAHR*100:.0f} % p.a. "
          f"= {VOLA_PERIODE*100:.3f} % je Periode")
    print(f"Slippage eta:        {ETA:.2e} EUR/Stueck^2")
    print(f"Risikoaversion:      {RISIKOAVERSION:.2e} 1/EUR")
    print(f"Erwartete Gesamtreibung: {V[0, -1]:,.2f} EUR "
          f"({V[0, -1]/(GESAMTBESTAND*KURS)*10000:.1f} Basispunkte)\n")

    plan = pd.DataFrame([{
        "Periode": f"t = {t} -> {t+1}",
        "Startbestand": f"{verlauf[t]:,}",
        "Verkauf n_t": f"{verkaeufe[t]:,}",
        "Restbestand": f"{verlauf[t+1]:,}",
        "Anteil": f"{verkaeufe[t]/GESAMTBESTAND*100:5.1f} %",
        "Kosten (EUR)": f"{periodenkosten(verkaeufe[t], verlauf[t+1]):,.0f}",
    } for t in range(PERIODEN)])
    print(plan.to_string(index=False))

    # --- Vergleich mit Alternativen und der analytischen Loesung ---------
    sofort = [GESAMTBESTAND] + [0] * PERIODEN
    gleichmaessig = [GESAMTBESTAND * (1 - t / PERIODEN) for t in range(PERIODEN + 1)]
    analytisch = analytische_loesung()

    print("\n" + "-" * 84)
    print(f"{'Strategie':<34} {'Kosten (EUR)':>15} {'Basispunkte':>13} "
          f"{'ggue. Optimum':>16}")
    print("-" * 84)
    optimum = V[0, -1]
    for name, pfad in [("DP-Optimum", verlauf),
                       ("Analytisch (Almgren-Chriss)", list(analytisch)),
                       ("Gleichmaessig (TWAP)", gleichmaessig),
                       ("Alles sofort", sofort)]:
        kosten = bewerte_pfad(pfad)
        bp = kosten / (GESAMTBESTAND * KURS) * 10000
        print(f"{name:<34} {kosten:>15,.0f} {bp:>12.1f} "
              f"{kosten - optimum:>+15,.0f}")

    print("-" * 84)
    abweichung = abs(bewerte_pfad(list(analytisch)) - optimum) / optimum
    print(f"Abweichung DP zur analytischen Loesung: {abweichung*100:.3f} % "
          f"(Diskretisierung: {SCHRITTWEITE} Stueck)")

    # --- Sensitivitaet gegenueber der Risikoaversion ---------------------
    print("\n--- Wie wirkt die Risikoaversion? ---")
    print(f"{'lambda':>10} | {'Verkauf in Periode 0':>22} | {'Charakter':<28}")
    print("-" * 70)
    for lam in [1e-7, 1e-6, 1e-5, 1e-4, 1e-3]:
        globals()["RISIKOAVERSION"] = lam
        _, V_l, pol_l = loese_dp()
        erste = pol_l[0, -1]
        anteil = erste / GESAMTBESTAND * 100
        charakter = ("nahezu gleichmaessig" if anteil < 25 else
                     "front-loaded" if anteil < 60 else "fast alles sofort")
        print(f"{lam:>10.0e} | {erste:>13,} ({anteil:5.1f} %) | {charakter:<28}")
    globals()["RISIKOAVERSION"] = 1e-5       # zuruecksetzen

    # --- Diagramm ---------------------------------------------------------
    plt.figure(figsize=(10, 5.5))
    plt.plot(range(PERIODEN + 1), verlauf, "o-", lw=2.5, label="DP-Optimum")
    plt.plot(range(PERIODEN + 1), analytisch, "s--", lw=1.8, alpha=0.8,
             label="Analytisch (Almgren-Chriss)")
    plt.plot(range(PERIODEN + 1), gleichmaessig, "^:", lw=1.8, alpha=0.8,
             label="Gleichmaessig (TWAP)")
    plt.bar(range(PERIODEN), verkaeufe, alpha=0.25, color="orange", width=0.45,
            label="Verkaufstranche $n_t$")
    plt.title("Optimaler Liquidationspfad ueber diskrete Perioden", fontsize=12)
    plt.xlabel("Handelsperiode $t$")
    plt.ylabel("Verbleibender Bestand $X_t$")
    plt.xticks(range(PERIODEN + 1))
    plt.grid(True, linestyle=":", alpha=0.6)
    plt.legend()
    plt.tight_layout()
    ziel = os.path.join(OUTPUT_DIR, "optimal_execution_dp.png")
    plt.savefig(ziel, dpi=150)
    print(f"\nDiagramm gespeichert unter '{ziel}'")
    print("=" * 84)

Erwartete Ausgabe:

====================================================================================
   OPTIMALE MEHRPERIODIGE ORDER-EXECUTION (BELLMAN DP)
====================================================================================
Gesamtvolumen:       100,000 Stueck zu 50.00 EUR = 5,000,000 EUR Positionswert
Zeithorizont:        5 Handelsperioden
Volatilitaet:        30 % p.a. = 0.741 % je Periode
Slippage eta:        2.50e-06 EUR/Stueck^2
Risikoaversion:      1.00e-05 1/EUR
Erwartete Gesamtreibung: 10,266.24 EUR (20.5 Basispunkte)

    Periode Startbestand Verkauf n_t Restbestand Anteil Kosten (EUR)
t = 0 -> 1       100,000      41,000      59,000  41.0 %        6,593
t = 1 -> 2        59,000      25,000      34,000  25.0 %        2,356
t = 2 -> 3        34,000      16,000      18,000  16.0 %          863
t = 3 -> 4        18,000      10,000       8,000  10.0 %          294
t = 4 -> 5         8,000       8,000           0   8.0 %          160

------------------------------------------------------------------------------------
Strategie                             Kosten (EUR)   Basispunkte    ggue. Optimum
------------------------------------------------------------------------------------
DP-Optimum                                  10,266          20.5               +0
Analytisch (Almgren-Chriss)                 10,860          21.7             +594
Gleichmaessig (TWAP)                        13,242          26.5           +2,976
Alles sofort                                25,000          50.0          +14,734
------------------------------------------------------------------------------------
Abweichung DP zur analytischen Loesung: 5.788 % (Diskretisierung: 1000 Stueck)

--- Wie wirkt die Risikoaversion? ---
    lambda |   Verkauf in Periode 0 | Charakter
----------------------------------------------------------------------
     1e-07 |        20,000 ( 20.0 %) | nahezu gleichmaessig
     1e-06 |        23,000 ( 23.0 %) | nahezu gleichmaessig
     1e-05 |        41,000 ( 41.0 %) | front-loaded
     1e-04 |        78,000 ( 78.0 %) | fast alles sofort
     1e-03 |        97,000 ( 97.0 %) | fast alles sofort
====================================================================================

Die Lösung ist front-loaded: 41 % im ersten Schritt, dann fallend (25 %, 16 %, 10 %, 8 %). Das ist die typische Form — man baut Risiko früh ab, aber nicht abrupt. Die Sensitivitätstabelle zeigt, wie \lambda zwischen den beiden Extremen steuert: Bei \lambda = 10^{-7} verkauft das Modell gleichmäßig (Risiko ist egal), bei \lambda = 10^{-3} praktisch alles sofort (Risiko dominiert).

Der Vergleich beziffert den Nutzen: Gegenüber der naiven TWAP-Strategie (gleiche Tranchen) spart die optimierte Ausführung 2 976 € oder 6 Basispunkte — bei einer Position von 5 Mio. €. Gegenüber „alles sofort“ sind es 14 734 €.

💻 Code-Durchgang: die analytische Gegenprobe und was ihre Abweichung bedeutet

Das Almgren-Chriss-Problem hat eine geschlossene Lösung: X_t = X_0\,\frac{\sinh(\kappa(T-t))}{\sinh(\kappa T)}, \qquad \kappa = \operatorname{arcosh}\!\Big(\tfrac{\tilde\kappa^2}{2}+1\Big),\qquad \tilde\kappa^2 = \frac{\lambda\,\sigma^2 P_0^2}{\eta}

Sie liefert hier 10 860 € gegenüber 10 266 € beim DP — eine Abweichung von 5,8 %, und zwar zugunsten des DP. Das ist kein Fehler, sondern lehrreich, und es hat zwei Ursachen:

1. Unterschiedliche Zeitkonvention. Die geschlossene Formel gilt für die zeitkontinuierliche Variante des Modells, in der das Risiko über das gesamte Intervall integriert wird. Unser diskretes Modell belastet dagegen den Bestand nach dem Verkauf. Beide Varianten sind legitim, sie lösen aber leicht verschiedene Probleme.
2. Diskretisierung. Der Zustandsraum ist in 1000er-Schritten gerastert; die analytische Lösung darf beliebige Stückzahlen wählen.

Die Lehre daraus ist wichtiger als die Zahl: Eine Vergleichsrechnung, die ungefähr passt, bestätigt die Größenordnung und die Form der Lösung — beide Pfade sind front-loaded, beide liegen bei rund 21 Basispunkten. Sie beweist aber nicht die Punktgenauigkeit, solange die Modellkonventionen nicht identisch sind. Wer zwei Zahlen vergleicht, muss zuerst prüfen, ob sie dasselbe messen.

Übernehmen Sie dennoch das Prinzip: Wo immer eine unabhängige zweite Rechnung möglich ist — Formel, Simulation, Handrechnung —, bauen Sie sie ein. Hätte das DP hier 500 000 € oder 12 € geliefert, wäre der Fehler sofort aufgefallen.

13.5 Der Fluch der Dimensionalität

DP ist mächtig, aber es hat eine harte Grenze. Der Aufwand der Rückwärtsinduktion ist

\mathcal{O}(T \cdot |\mathcal{S}| \cdot |\mathcal{A}|)

— Perioden mal Zustände mal Aktionen. Im Beispiel oben: 5 \times 101 \times 101 \approx 51\,000 Auswertungen, in Sekundenbruchteilen erledigt.

Das Problem entsteht, sobald der Zustand mehrere Dimensionen hat:

Das ist der Fluch der Dimensionalität (Bellmans eigener Begriff): Jede zusätzliche Zustandsvariable multipliziert den Aufwand.

Gegenmittel: * Zustandsraum verkleinern: gröber diskretisieren, irrelevante Variablen weglassen. * Approximate Dynamic Programming: V_t durch eine parametrische Funktion annähern statt tabellarisch zu speichern. * Reinforcement Learning: dieselbe Bellman-Gleichung, aber V wird aus Erfahrung gelernt (Q-Learning) statt vollständig berechnet. * Nach geschlossenen Lösungen suchen — wie bei Almgren-Chriss. Wo eine Formel existiert, ist sie unschlagbar.

13.6 Übungsaufgaben

Lösungen: Abschnitt A.13.

Aufgabe 13.1 ⭐ — Bausteine benennen. Ein Wanderer plant eine 5-Tages-Tour und muss täglich entscheiden, wie weit er läuft. Bestimmen Sie Stufe, Zustand, Aktion und Wertfunktion. Was gehört nicht in den Zustand?

Aufgabe 13.2 ⭐ — Optimalitätsprinzip anwenden. Warum folgt aus dem Optimalitätsprinzip, dass man rückwärts rechnen darf? Was würde schiefgehen, wenn die Kosten einer Periode auch von früheren Aktionen abhängen (und nicht nur vom aktuellen Zustand)?

Aufgabe 13.3 ⭐⭐ — Rückwärtsinduktion von Hand. 5 Einheiten in 3 Perioden, Kosten C(n) = n^2 + 2n. Erstellen Sie die vollständige Wertfunktionstabelle und bestimmen Sie den optimalen Pfad. Prüfen Sie mit Bellman_Minimalbeispiel.py (angepasst).

Aufgabe 13.4 ⭐⭐ — Rucksackproblem als DP. Lösen Sie das Rucksackproblem aus Kapitel 6 mit dynamischer Programmierung statt MILP. (Zustand: verbleibende Kapazität; Stufe: betrachteter Gegenstand.) Vergleichen Sie Laufzeit und Ergebnis mit dem MILP-Solver.

Aufgabe 13.5 ⭐⭐⭐ — Risikoaversion kalibrieren. Untersuchen Sie mit Mehrperiodige_Order_Execution.py: (a) Bei welchem \lambda verkauft das Modell in der ersten Periode mehr als 50 %? (b) Stellen Sie den Zusammenhang zwischen \lambda und den erwarteten Gesamtkosten dar. (c) Ein Händler sagt: „Ich will höchstens 20 % Marktauswirkungskosten und den Rest an Risiko.“ Welches \lambda setzen Sie?

Aufgabe 13.6 ⭐⭐⭐ — Zustandsraum erweitern. Erweitern Sie das Ausführungsmodell um einen zweiten Zustand: die aktuelle Orderbuchtiefe (3 Stufen: dünn/normal/tief), die mit gegebenen Übergangswahrscheinlichkeiten wechselt und \eta um Faktor 2 / 1 / 0,5 skaliert. Wie ändert sich die Strategie? Wie stark wächst die Rechenzeit?

13.7 Finde den Denkfehler

Bei dynamischer Programmierung entscheidet eine einzige Frage über Erfolg oder Misserfolg: Was gehört in den Zustand? Ist er zu klein, rechnet das Verfahren völlig korrekt — nur eben an einem anderen Problem.

🎯 Merksatz Der Zustand muss alles enthalten, was die Zukunft beeinflusst — und nichts darüber hinaus. Zu wenig, und das Modell löst ein anderes Problem, ohne es zu merken. Zu viel, und es wird unnötig groß (Abschnitt 13.5). Die Probe dafür ist ein einziger Satz: „Wenn ich nur den Zustand kenne und nicht den Weg dorthin — kann ich dann noch optimal weiterentscheiden?“ Lautet die Antwort nein, fehlt etwas.

13.8 Micro-Quiz

13.9 Selbsttest

Antworten: Anhang A.

1. Formulieren Sie das Optimalitätsprinzip in eigenen Worten.
2. Warum rechnet man bei DP rückwärts und nicht vorwärts?
3. Was muss ein Zustand enthalten — und woran erkennt man, dass er unvollständig ist?
4. Was besagt der Fluch der Dimensionalität, und welche drei Gegenmittel gibt es?
5. Warum ist eine analytische Vergleichslösung wertvoll, wenn man schon eine numerische hat?

13.10 Zusammenfassung

• Das Optimalitätsprinzip erlaubt es, ein mehrstufiges Problem in ineinandergreifende Einperiodenprobleme zu zerlegen.
• Rückwärtsinduktion startet am bekannten Ende und arbeitet sich nach vorn — dadurch ist V_{t+1} immer schon bekannt, wenn V_t berechnet wird.
• Die Zustandsdefinition ist die eigentliche Modellierungsleistung: vollständig, aber so knapp wie möglich. Die Probe dafür ist ein Satz: „Wenn ich nur den Zustand kenne und nicht den Weg dorthin — kann ich dann noch richtig weiterentscheiden?“ Fehlt etwas, rechnet das Verfahren korrekt an einem anderen Problem, ohne es zu melden.
• Die Wertfunktion ist eine Nachschlagetabelle, kein Plan. Ihr praktischer Ertrag ist eine Regel für jeden Zustand — die auch dann noch gilt, wenn es anders kommt als gedacht.
• Gierige Vorwärtsregeln scheitern systematisch, weil sie die Restkosten nicht kennen: Im Schnellstart kostet der billigere erste Abschnitt am Ende 50 % mehr.
• Bei überproportionalen Kosten lohnt sich Stückelung — das ist der ökonomische Kern des Ausführungsproblems.
• Magische Konstanten sind ein Warnsignal. Jeder Parameter braucht eine Einheit und eine Interpretation, sonst ist das Modell nicht kalibrierbar.
• Der Fluch der Dimensionalität begrenzt DP auf wenige Zustandsdimensionen.

Ausblick. Teil IV führt alles zusammen: Ab Kapitel 18 arbeiten wir mit echten Marktdaten — und lernen zuerst, warum diese Daten trügerisch sind.