Ein massgeschneiderter Portfolio-Optimierer, bis zu 40 % effizienter im Risiko-Rendite-Verhältnis als Standard-Heuristiken

Ein räumliches Branch-and-Bound, an der ETH IFOR mit swissQuant entwickelt, liefert zertifiziert-optimale Portfolios für ein nicht-konvexes Problem, das Standard-MIP-Solver nur heuristisch angehen können

Moderne Asset Manager wollen Portfolios, in denen jede Position einen fairen Anteil am Risiko trägt, nicht nur einen fairen Anteil am Kapital. Die Nebenbedingung, die das erzwingt, ist mathematisch sperrig, und die meisten Standardsolver geben entweder auf oder liefern Zahlen, die niemand vor einem Risikoausschuss verteidigen will.

Gemeinsam mit swissQuant und dem Institute for Operations Research der ETH Zürich haben wir einen Branch-and-Bound-Algorithmus entwickelt, der das Problem zur zertifiziert globalen Optimalität löst. Der Output ist nicht nur ein Portfolio, sondern ein Portfolio mit Beweis.

+40 %

höhere Risiko-Rendite-Effizienz als die Heuristik auf 33-Asset-MSCI-World-Portfolios

2,5×

geringere Portfolio-Varianz als die Heuristik im reinen Risiko-Minimierungsregime

Zertifiziert

globales Optimum auf einem nicht-konvexen QCQP, das Standard-MIP-Solver nicht zur Optimalität lösen können

Produktionsreif

dokumentierte Python-Implementierung für die Bewertungs-Pipeline von swissQuant

Die Herausforderung

Die institutionellen Kunden von swissQuant forderten Portfolios, in denen der Marginalbeitrag jedes Assets zur Gesamtvolatilität in einer engen Toleranz bleibt. Die Mathematik dieser Nebenbedingung ist nicht-konvex, und Standard-QP- oder Konussolver liefern entweder unzulässige Lösungen oder reissen das Zeitlimit, sobald das Asset-Universum wächst.

Heuristiken liefern einen Punkt, aber keine Schranke dafür, wie weit dieser Punkt vom Optimum entfernt liegt. Das ist unangenehm, wenn das Ergebnis auf dem Schreibtisch eines Portfoliomanagers landen und verteidigt werden muss.

Unser Vorgehen

Wir haben das Problem als Quadratically Constrained Quadratic Program reformuliert und einen räumlichen Branch-and-Bound-Algorithmus mit massgeschneiderten konvexen Relaxierungen an jedem Knoten gebaut. Enges Bound-Tightening, intelligente Verzweigungsregeln und ein Benchmark von sechs algorithmischen Varianten auf echten MSCI-World-Daten haben die Konfiguration identifiziert, die durchgängig gewinnt.

Ergänzend zur exakten Engine haben wir zwei praxisnahe Heuristiken geliefert, die die Suche warmstarten oder als schnelle Fallback-Option dienen, wenn ein zertifiziertes Optimum den Wartezeitaufwand nicht wert ist.

Das Ergebnis

Deliverable: eine dokumentierte Python-Implementierung des räumlichen Branch-and-Bound auf McCormick-Relaxierungen, die beiden Warmstart-Heuristiken und die reproduzierbaren MSCI-World-Test-Harnische, bereit zur Integration in die interne Bewertungs-Pipeline von swissQuant.

Auf echten Fünf-Jahres-Daten des MSCI World (Top-100-Instrumente, Vier-Währungs-Korb, tägliche Log-Renditen Januar 2015 – Januar 2020) schliesst der Algorithmus eine 40 % grosse Zielfunktionslücke, die die iterative Heuristik auf 33-Asset-Portfolios offen lässt. Im am stärksten nicht-konvexen Regime (n = 11, τ = 1) liefert die Heuristik einen positiven Zielwert, wo das echte Optimum negativ ist, eine relative Lücke von 160 %; unser Algorithmus findet das zertifizierte Optimum.

Technischer Deep Dive

Das Modell hinter dem Ergebnis.

Das Modell

Das Portfoliorisiko messen wir über die Volatilität R(x) = √(xᵀΣx). Für ein Long-Only-Portfolio x folgt der Marginalbeitrag von Asset i aus der Euler-Zerlegung der Volatilität:

MRC_{i} (x) = x_{i} \cdot \frac{( Σ x ) _{i}}{x ^{⊤} Σ x}, i = 1 \sum n MRC_{i} (x) = R (x) .

Die Marginal-Risikobeiträge summieren sich exakt zur Gesamtvolatilität des Portfolios.

rMRC_{i} (x) = \frac{MRC _{i} ( x )}{R ( x )} = \frac{x _{i} ( Σ x ) _{i}}{x ^{⊤} Σ x} \leq c_{i} \forall i \in [n] .

Relativer Marginalbeitrag: Asset i darf höchstens den Anteil cᵢ am Gesamtrisiko beitragen.

x \geq 0 min s.t. τ x^{⊤} Σ x - (1 - τ) μ^{⊤} x x_{i} (Σ x)_{i} \leq c_{i} (x^{⊤} Σ x) \forall i \in [n] 1^{⊤} x = 1.

Problem (P): Mean-Variance mit rMRC-Constraints. τ tariert Risiko gegen erwartete Rendite μ.

y_{i} = (Σ x)_{i}, z_{i} = x_{i} y_{i}, z_{i} \leq c_{i} j = 1 \sum n z_{j} .

Reformulierung: Hilfsvariablen y, z heben die Nicht-Konvexität in saubere bilineare Gleichungen.

z_{i} \geq z_{i} \geq z_{i} \leq z_{i} \leq x_{i}^{lb} y_{i} + x_{i} y_{i}^{lb} - x_{i}^{lb} y_{i}^{lb}, x_{i}^{ub} y_{i} + x_{i} y_{i}^{ub} - x_{i}^{ub} y_{i}^{ub}, x_{i}^{ub} y_{i} + x_{i} y_{i}^{lb} - x_{i}^{ub} y_{i}^{lb}, x_{i} y_{i}^{ub} + x_{i}^{lb} y_{i} - x_{i}^{lb} y_{i}^{ub} .

Die McCormick-Hülle: vier lineare Ungleichungen pro Asset, die den bilinearen Term z_i = x_i y_i bei vorgegebenen Boxschranken auf (x_i, y_i) einschliessen.

Jeder Branch-and-Bound-Knoten löst eine konvexe Relaxierung aus diesen McCormick-Ungleichungen. Die Verzweigung unterteilt die Box auf x, die Schranken auf y werden analytisch nachgerechnet, und die Suche endet, sobald der Abstand zwischen der besten zulässigen Lösung und der niedrigsten offenen Schranke unter die Toleranz fällt.

Benchmark

Laufzeit der besten B&B-Konfiguration auf MSCI-World-Benchmarks.

Universumsgrösse	c-Faktor	τ ≤ 0,6	τ = 0,7	τ = 0,8	τ = 0,9	τ = 1,0
n = 11	1,5/n	22,3 s	11,0 s	12,7 s	14,1 s	17,3 s
n = 22	1,5/n	198,9 s	217,0 s	107,3 s	68,2 s	64,7 s
n = 33	1,5/n	674,3 s	1658,4 s	2219,0 s	34,4 s	57,3 s
n = 44	2/n	1223,6 s	1883,5 s	1232,2 s	761,5 s	598,2 s
n = 54	2/n	-	-	-	1238,8 s	621,1 s

Zeiten in Sekunden, single-threaded Relaxierungsaufrufe, Stunden-Cap. Testumgebung: zufällige Teilmengen der MSCI-World-Top-100, tägliche Log-Renditen Januar 2015 – Januar 2020, Vier-Währungs-Korb. Gedankenstriche bedeuten, dass die Konfiguration die Optimalitätslücke innerhalb des Budgets nicht schliessen konnte.

Aus den Unterlagen

Abbildung 2.1 aus dem Bericht: Die McCormick-Hülle für den bilinearen Term z = xy. Die schwarze Kurve ist der ursprüngliche nicht-konvexe zulässige Bereich; die grünen und rosafarbenen Polytope sind die linearen Über- und Unterschätzer, über denen die Relaxierung gelöst wird.

Algorithmus 1: die räumliche Branch-and-Bound-Schleife. An jedem Knoten lösen wir das McCormick-relaxierte Programm, prunen nach bester Schranke und verzweigen auf das Asset mit der grössten bilinearen Verletzung.

Abbildung 4.3 aus dem Bericht: relative Zielfunktionslücke zwischen der iterativen Heuristik und dem zertifizierten Branch-and-Bound-Optimum als Funktion der Risikoaversion τ auf n = 33 Assets. Die Lücke überschreitet im mittleren τ-Bereich, wo das Problem am stärksten nicht-konvex ist, 40 %.

Techniken

Räumliches Branch-and-Bound
McCormick-Hüllen-Relaxierungen
Bilineare Reformulierung des QCQP
Adaptives Bound-Tightening über Relaxierungs-Duale
Risikoparitäts- und Risikobudgetierungs-Modellierung
Mean-Variance mit nicht-konvexen Risikobedingungen

Stack

Python
Gurobi
NumPy
MSCI-World-Daten-Pipeline

Ein Problem wie dieses?

Wir würden gerne davon hören.

contact@optimally.ch