Un optimiseur de portefeuille sur mesure, jusqu'à 40 % plus efficace en risque-rendement que les heuristiques standard

Un Branch-and-Bound spatial construit à l'ETH IFOR avec swissQuant, livrant des portefeuilles à l'optimum certifié sur un problème non convexe que les solveurs MIP standard ne peuvent qu'approcher heuristiquement

Les gérants d'actifs modernes veulent des portefeuilles où chaque position porte une part équitable du risque, pas seulement une part équitable du capital. La contrainte qui impose cela est mathématiquement désagréable, et la plupart des solveurs sur étagère renvoient soit des chiffres infaisables, soit des chiffres que personne ne peut défendre devant un comité de risque.

Nous avons travaillé avec swissQuant et l'Institute for Operations Research de l'ETH Zurich pour construire un algorithme de Branch-and-Bound qui résout le problème jusqu'à l'optimalité globale certifiée. La sortie n'est pas seulement un portefeuille, c'est un portefeuille avec preuve.

+40 %

plus efficace en risque-rendement que la heuristique sur des portefeuilles MSCI World à 33 actifs

2,5×

variance de portefeuille inférieure à la heuristique dans le régime de pure minimisation du risque

Certifié

optimum global sur un QCQP non convexe que les solveurs MIP standard ne savent pas résoudre à l'optimum

Production-ready

implémentation Python documentée pour le pipeline de valorisation de swissQuant

Le défi

Les clients institutionnels de swissQuant exigeaient des portefeuilles où la contribution marginale de chaque actif à la volatilité totale reste dans une tolérance étroite. Les mathématiques derrière cette contrainte sont non convexes, et les solveurs quadratiques et coniques sur étagère renvoient soit des solutions infaisables, soit ils atteignent leur limite de temps dès que l'univers d'actifs grandit.

Les heuristiques produisent un point mais aucune borne sur sa distance à l'optimum. C'est gênant quand le résultat doit atterrir sur le bureau d'un gérant et être défendu.

Notre démarche

Nous avons reformulé le problème en Quadratically Constrained Quadratic Program et construit un algorithme de Branch-and-Bound spatial avec relaxations convexes sur mesure à chaque nœud. Un bound-tightening serré, des règles de branchement intelligentes et un benchmark de six variantes algorithmiques sur des données MSCI World réelles ont identifié la configuration qui gagne systématiquement.

À côté du moteur exact, nous avons livré deux heuristiques adaptées à l'industrie qui réchauffent le démarrage de la recherche ou servent de repli rapide quand un optimum certifié ne vaut pas l'attente.

Le résultat

Livrable : une implémentation Python documentée du Branch-and-Bound spatial sur relaxations de McCormick, les deux heuristiques de warm-start, et les harnais de test MSCI World reproductibles, prêts à se brancher sur le pipeline de valorisation interne de swissQuant.

Sur des données MSCI World réelles sur cinq ans (top 100 instruments, panier de quatre devises, log-rendements quotidiens janvier 2015 – janvier 2020), l'algorithme comble un écart d'objectif de 40 % laissé ouvert par l'heuristique itérative sur des portefeuilles de 33 actifs. Dans le régime le plus non convexe (n = 11, τ = 1), l'heuristique renvoie un objectif positif là où le véritable optimum est négatif, un écart relatif de 160 % ; notre algorithme trouve l'optimum certifié.

Plongée technique

Le modèle derrière le résultat.

Le modèle

Nous mesurons le risque du portefeuille par la volatilité R(x) = √(xᵀΣx). Pour un portefeuille long-only x, la contribution marginale au risque de l'actif i découle de la décomposition d'Euler de la volatilité :

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

Les contributions marginales au risque s'additionnent exactement à la volatilité totale du portefeuille.

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

Contribution marginale relative : l'actif i peut contribuer au plus à une fraction cᵢ du risque total.

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.

Problème (P) : mean-variance sous contraintes rMRC. τ arbitre entre le risque et le rendement attendu μ.

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

Reformulation : les variables auxiliaires y, z déplacent toute la non-convexité dans des égalités bilinéaires propres.

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} .

L'enveloppe de McCormick : quatre inégalités linéaires par actif qui encadrent le terme bilinéaire z_i = x_i y_i étant donné les bornes en boîte sur (x_i, y_i).

Chaque nœud de Branch-and-Bound résout une relaxation convexe construite à partir de ces inégalités de McCormick. Le branchement subdivise la boîte sur x, les bornes sur y sont recalculées analytiquement, et la recherche se termine quand l'écart entre la meilleure solution faisable et la plus basse borne ouverte tombe en dessous de la tolérance.

Benchmark

Temps d'exécution de la meilleure configuration B&B sur des benchmarks MSCI World.

Taille de l'univers	Facteur c	τ ≤ 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

Temps en secondes, appels de relaxation en mono-thread, limite d'une heure. Banc d'essai : sous-ensembles aléatoires du top 100 MSCI World, log-rendements quotidiens janvier 2015 – janvier 2020, panier de quatre devises. Les tirets indiquent que la configuration n'a pas comblé l'écart d'optimalité dans le budget imparti.

Tiré du dossier

Figure 2.1 du rapport : l'enveloppe de McCormick pour le terme bilinéaire z = xy. La courbe noire est la région faisable non convexe d'origine ; les polytopes verts et roses sont les sur- et sous-estimateurs linéaires sur lesquels la relaxation est résolue.

Algorithme 1 : la boucle de Branch-and-Bound spatial. À chaque nœud nous résolvons le programme relaxé par McCormick, prunons selon la meilleure borne et branchons sur l'actif présentant la plus grande violation bilinéaire.

Figure 4.3 du rapport : écart relatif en fonction objectif entre l'heuristique itérative et l'optimum certifié de Branch-and-Bound, en fonction de l'aversion au risque τ sur n = 33 actifs. L'écart culmine au-dessus de 40 % dans le régime médian où le problème est le plus non convexe.

Techniques

Branch-and-Bound spatial
Relaxations par enveloppe de McCormick
Reformulation bilinéaire du QCQP
Bound-tightening adaptatif via duaux de relaxation
Modélisation par parité de risque et budget de risque
Mean-variance avec contraintes de risque non convexes

Stack

Python
Gurobi
NumPy
Pipeline de données MSCI World

Un problème de ce type ?

Nous serions ravis d'en entendre parler.

contact@optimally.ch