💰 quantitative finance

Large-Scale Portfolio Optimization Problem Under Cardinality Constraint With Enhanced Multi-Objective Evolutionary Algorithms

Cet article propose des algorithmes évolutionnaires multiobjectifs améliorés, présentant de nouvelles représentations de solutions, des opérateurs et des mécanismes de réparation pour résoudre efficacement les problèmes d'optimisation de portefeuille à grande échelle sous contraintes de cardinalité, démontrant une convergence plus rapide et des performances supérieures par rapport aux méthodes traditionnelles à mesure que la complexité du marché augmente.

Auteurs originaux : Danial Ramezani, Mostafa Abouei Ardakan

Publié 2026-07-13

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Danial Ramezani, Mostafa Abouei Ardakan

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un chercheur de trésors essayant de construire le sac à dos ultime pour un long voyage. Vous voulez deux choses : les pièces d'or les plus précieuses (rendement élevé) et une charge la plus légère et la plus sûre possible (faible risque). Mais il y a un piège. Votre sac à dos a une règle stricte : vous ne pouvez transporter qu'un nombre spécifique d'articles différents, disons entre 3 et 10, peu importe le nombre de trésors éparpillés sur la carte. C'est le problème de l'« Optimisation de Portefeuille à Contrainte de Cardinalité ».

Pendant des décennies, les investisseurs ont tenté de résoudre cela en utilisant des méthodes mathématiques « exactes », comme essayer de compter chaque grain de sable sur une plage pour trouver la poignée parfaite. L'article explique que cette approche est comparable à essayer de boire d'un incendie de lance à incendie ; c'est trop lent et cela se bloque lorsque le nombre d'actifs (les grains de sable) devient énorme. En fait, les auteurs notent que l'ajout de ces règles du monde réel transforme le problème en un cauchemar pour les ordinateurs, connu sous le nom de « NP-difficile », où les outils mathématiques traditionnels abandonnent ou mettent un temps infini.

La Grande Idée : Un Nouveau Design de Sac à Dos
Au lieu de compter chaque grain, les auteurs ont construit un nouveau type de sac à dos et un nouvel ensemble de règles pour le remplir. Ils ont pris un outil populaire appelé NSGA-II (pensez à un robot intelligent et évolutif qui essaie différentes combinaisons de sacs à dos) et lui ont donné une mise à jour majeure.

Voici comment leur nouveau système fonctionne, en utilisant leurs propres analogies et mécaniques :

1. Le Sac à Dos à « Taille Fixe » (Nouveau Codage)
Les anciennes méthodes essayaient de transporter une liste de tous les trésors possibles et marquaient simplement lesquels prendre. Si vous aviez 225 trésors, votre liste faisait toujours 225 articles de long, même si vous n'en transportiez que 10. Cela faisait perdre du temps au robot qui vérifiait des emplacements vides.
Les auteurs ont changé le sac à dos lui-même. Désormais, le sac possède exactement Kmax emplacements (le nombre maximum d'articles que vous êtes autorisé à transporter). Si vous pouvez transporter jusqu'à 5 articles, votre sac possède exactement 5 emplacements.

L'Astuce : Si vous mettez le même trésor dans deux emplacements, cela compte pour un seul article, mais le poids (l'argent) s'additionne. Cela permet au robot de voir beaucoup plus facilement s'il enfreint les règles. Si le sac contient moins de Kmin articles uniques (par exemple, seulement 2 articles uniques alors qu'il en faut au moins 3), le robot sait qu'il doit échanger un nouveau trésor.

2. La Chasse en « Deux Phases » (Stratégies de Reproduction)
Le robot ne devine pas au hasard. Il chasse en deux phases distinctes, comme un détective résolvant une affaire :

Phase 1 (Le Large Filet) : Au début, le robot est sauvage. Il utilise une stratégie basée sur le « genou » (Knee-based) pour trouver les meilleures combinaisons de trésors. Il cherche le « genou » de la courbe — le point idéal où l'on obtient le plus d'or pour le moins de poids supplémentaire. Il fait se reproduire les solutions qui sont proches de ce point idéal pour trouver le bon mélange d'actifs rapidement.
Phase 2 (L'Affinage) : Une fois qu'il a une bonne liste de trésors, il arrête de chercher de nouveaux trésors et commence à ajuster la quantité de chaque trésor. Il utilise une stratégie basée sur la « similitude » (Similarity-based), faisant se reproduire des sacs à dos qui possèdent déjà les mêmes trésors mais des poids différents, afin d'affiner l'équilibre exact.

3. L'Outil « Explorateur »
Parfois, le robot répare un sac à dos cassé (qui contient trop peu ou trop d'articles) en y échangeant simplement un article au hasard. Mais les auteurs ont réalisé que cela est maladroit. Ils ont inventé un nouvel outil appelé l'« Explorateur ».
Imaginez que vous avez un sac à dos auquel il manque un article. Au lieu de simplement saisir la première pierre que vous voyez, l'Explorateur examine plusieurs façons de combler ce vide. Il essaie cinq méthodes « heuristiques » différentes (comme répartir l'argent également, ou donner plus d'argent aux articles les plus sûrs) pour voir laquelle rend le sac à dos meilleur. Il choisit ensuite la meilleure version et marche même un peu dans l'espace « inconnu » entre l'ancien et le nouveau sac à dos pour voir s'il peut trouver quelque chose d'encore meilleur. Cela garantit que la réparation n'est pas seulement « correcte », mais qu'il s'agit d'une amélioration réelle.

4. L'Équipe de Réparation (Gestion des Contraintes)
Lorsque le robot enfreint accidentellement les règles (comme choisir trop d'articles ou mettre trop d'argent dans un article), il ne jette pas simplement le sac à dos. Il dispose d'une équipe de réparation spécialisée :

L'Équipe d'Association : Regarde ce que d'autres sacs à dos réussis dans le groupe actuel contiennent et copie ces modèles.
L'Équipe de Score : Groupe les trésors selon la manière dont ils performent ensemble et choisit le meilleur groupe.
L'Équipe de Seuil : Regarde spécifiquement les trésors qui ne bougent pas en synchronisation avec les autres (faible corrélation) pour ajouter de la diversité.

Ce Qu'Ils Ont Trouvé (Les Résultats)
Les auteurs ont testé ce nouveau système contre l'ancien robot standard sur quatre marchés réels : le DAX 100 (Allemagne), le S&P 100 (USA), le Nikkei 225 (Japon) et la Bourse de Téhéran (TSE).

La Taille du Test : Ils ont utilisé des ensembles de données comprenant respectivement 85, 98, 225 et 418 actifs.
Les Règles : Ils ont fixé le sac pour qu'il contienne entre Kmin et Kmax articles (par exemple, entre 2 et 10, ou exactement 10).
Le Résultat : Dans des simulations tournant sur 100 itérations avec une population de 100 solutions, leur robot amélioré a systématiquement trouvé de meilleurs sacs à dos.
- Il a trouvé des solutions plus proches de la limite théorique « parfaite » (mesurée par une métrique appelée IGD).
- Il a couvert une gamme plus large d'options de qualité (mesurée par l'Hypervolume).
- Il l'a fait plus rapidement et plus de manière plus fiable, surtout lorsque le nombre d'actifs devenait important.

Ce Qu'Ils Excluent Explicitement
L'article est très clair sur ce qui ne fonctionne pas bien pour ce problème spécifique :

Méthodes Exactes : Ils soutiennent que les méthodes mathématiques exactes traditionnelles sont inefficaces pour ce problème car il est NP-difficile. Ils suggèrent que ces méthodes sont trop lentes pour les grands marchés.
Fonctions de Pénalité : Bien que certains chercheurs utilisent des « fonctions de pénalité » (donner un mauvais score aux sacs à dos défectueux), cet article stipule explicitement que la vaste majorité des études réussies utilisent des mécanismes de réparation (réparer le sac à dos) au lieu de cela. Ils ont choisi de réparer les solutions plutôt que de simplement les pénaliser.
Le Hasard : Ils montrent que faire se reproduire simplement des solutions aléatoires tôt dans le processus gaspille du temps. Leur sélection basée sur le « genou » est nécessaire pour guider la recherche.

À Quel Point Sont-ils Sûrs ?
Les auteurs sont confiants dans leurs résultats, mais ils sont prudents dans leur langage. Ils déclarent que leur approche « indique » et « démontre » la supériorité basée sur 100 passages de la simulation. Ils ont utilisé des tests statistiques (le Test de Signe et le Test de Wilcoxon) pour prouver que leurs résultats ne sont pas dus à la chance.

Par exemple, sur le marché TSE, leur méthode a gagné 10 fois sur 10 contre la méthode standard pour la métrique Hypervolume.
Cependant, ils notent que pour le marché DAX 100, l'amélioration d'une métrique spécifique (MGD) n'était pas statistiquement significative au niveau le plus strict, bien qu'elle soit meilleure en moyenne.

L'Essentiel
L'article suggère qu'en changeant la façon dont nous représentons le problème (le sac à dos à taille fixe), la façon dont nous cherchons les solutions (la chasse en deux phases) et la façon dont nous réparons les erreurs (l'outil Explorateur), nous pouvons trouver de meilleurs portefeuilles d'investissement beaucoup plus rapidement. Cela est particulièrement vrai lorsque le marché se densifie avec des centaines d'actifs. Les auteurs concluent que, bien que leur méthode soit une amélioration notable, elle n'est pas une baguette magique ; elle doit encore être adaptée si les investisseurs souhaitent ajouter des règles encore plus complexes comme les coûts de transaction plus tard. Mais pour l'instant, c'est une façon bien plus intelligente de préparer son sac à dos.

Résumé Technique : Optimisation de Portefeuille à Grande Échelle sous Contrainte de Cardinalité avec des Algorithmes Évolutifs Multi-Objectifs Améliorés

Définition du Problème
L'article traite du Problème d'Optimisation de Portefeuille sous Contrainte de Cardinalité (CCPOP), une variante du modèle classique Moyenne-Variance (MV) introduit par Markowitz. Bien que le modèle MV cherche à maximiser le rendement et à minimiser le risque, il échoue souvent à prendre en compte les contraintes réelles, rendant le problème NP-difficile. Plus précisément, cette étude se concentre sur la Contrainte de Cardinalité (CC), qui limite le nombre d'actifs ( $K$ ) dans un portefeuille à une plage $[K_{min}, K_{max}]$ , et la Contrainte de Limite (BC), qui restreint le poids de chaque actif individuel à $[\epsilon_i, \delta_i]$ . L'inclusion de ces contraintes, parallèlement aux objectifs conflictuels de risque et de rendement, rend les méthodes exactes inefficaces pour les marchés à grande échelle, nécessitant ainsi l'utilisation d'algorithmes d'approximation.

Méthodologie
Les auteurs proposent une version personnalisée de l'Algorithme Génétique de Tri Non-Dominé II (NSGA-II) conçue pour gérer les complexités spécifiques du CCPOP. La méthodologie introduit quatre innovations primaires :

Encodage de Solution Novateur :
Au lieu du vecteur standard de valeurs réelles de taille $N$ (total des actifs), les auteurs proposent un chromosome de taille fixe $K_{max}$ composé de deux lignes :
- Ligne 1 : Identifiants des actifs sélectionnés pour le portefeuille.
- Ligne 2 : Poids correspondants.
  Cette représentation limite intrinsèquement le nombre d'actifs à $K_{max}$ , éliminant ainsi le besoin de mécanismes de réparation pour supprimer les actifs excédentaires lorsque la limite supérieure est violée. Les actifs en double dans la première ligne sont autorisés ; leurs poids dans la seconde ligne sont additionnés pour déterminer l'allocation totale de cet actif.
Stratégies de Reproduction Dynamiques :
Le processus de sélection est divisé en deux phases pour équilibrer l'exploration et l'exploitation :
- Itérations Précoces (Exploration) : Une Sélection par Tournoi basée sur le Genou (Knee-based) est utilisée. Elle sélectionne des individus basés sur la distance euclidienne vers le "Point d'Utopie" (rendement maximal/risque minimal idéal), privilégiant les solutions proches du genou du Front de Pareto (PF) pour trouver rapidement des combinaisons d'actifs de haute qualité.
- Itérations Tardives (Exploitation) : Une Sélection par Tournoi par Matrice de Similitude est activée. Elle identifie les portefeuilles ayant des combinaisons d'actifs identiques ou similaires et les fait se reproduire pour affiner les allocations de capital (poids) plutôt que de chercher de nouveaux mélanges d'actifs.
Mutation Spécialisée et l'Opérateur "Explorer" :
- Mutations : Trois types de mutations sont combinés dynamiquement. Les itérations précoces utilisent des mutations qui échangent des actifs (recherche globale), tandis que les itérations tardives se concentrent sur l'ajustement des poids (recherche locale).
- Opérateur Explorer : Un nouvel opérateur de réparation et d'optimisation conçu pour les individus qui violent les contraintes. Il génère des solutions candidates en utilisant cinq méthodes heuristiques de distribution de capital (ex: distribution égale, basée sur la volatilité, ratio rendement/risque). Il explore ensuite l'espace entre la solution cible et la meilleure candidate en utilisant une formule d'interpolation spécifique (Équation 10) pour trouver des allocations de poids supérieures sans modifier l'ensemble des actifs.
Mécanismes de Gestion des Contraintes :
- Réparation de la Cardinalité : Trois techniques sont proposées pour ajouter des actifs aux portefeuilles violant la contrainte $K_{min}$ $K_{min}$ :
  - Basée sur l'association : Utilise le regroupement (clustering) du Front de Pareto actuel pour identifier les actifs qui apparaissent fréquemment avec les actifs du portefeuille violé.
  - Basée sur le score : Regroupe l'ensemble de l'univers des actifs et sélectionne des actifs issus des clusters ayant les scores les plus élevés basés sur la corrélation et les mesures de performance.
  - Basée sur le seuil : Sélectionne des actifs ayant une faible corrélation avec les actifs du portefeuille existant, contrôlée par un coefficient de rigueur.
- Réparation des Limites : Une version modifiée de Chang et al. (2000) est utilisée pour ajuster les poids afin de satisfaire $[\epsilon_i, \delta_i]$ , traitant spécifiquement les cas où les doublons d'actifs causent des violations de poids totaux.

Principales Contributions

Efficacité de l'Encodage : La représentation du chromosome de taille fixe simplifie la gestion de la limite supérieure de cardinalité et réduit la charge de calcul des mécanismes de réparation.
Recherche Adaptative : La stratégie de reproduction en deux phases (Genou vs Similitude) équilibre efficacement la découverte de diverses combinaisons d'actifs et l'optimisation de l'allocation de capital.
Réparation Améliorée : L'opérateur "Explorer" fournit un moyen structuré de ré-optimiser les poids pour les solutions réparées, garantissant que la faisabilité ne se fait pas au détriment de la performance.
Scalabilité : L'approche est spécifiquement conçue pour maintenir ses performances à mesure que le nombre d'actifs disponibles ( $N$ ) augmente, répondant à une faiblesse connue des algorithmes évolutifs standards pour les problèmes à grande échelle.

Résultats Expérimentaux
L'algorithme proposé a été testé contre le NSGA-II standard et une version utilisant le nouvel encodage mais les stratégies de reproduction standard. Les expériences ont été menées sur quatre jeux de données : DAX 100, S&P 100, Nikkei 225 et la Bourse de Téhéran (TSE) (418 actifs).

Métriques de Performance : L'étude a utilisé l'Hypervolume (HV), la Distance Générationnelle (GD), l'Inverted Generational Distance (IGD) et la Métrique de Diversité ( $\Delta$ ). Une "Distance Générationnelle Modifiée" (MGD) a également été introduite pour normaliser les comparaisons.
Constats :
- L'approche proposée a systématiquement surpassé le NSGA-II standard sur toutes les métriques et tous les marchés.
- L'écart de performance s'est creusé à mesure que le nombre d'actifs augmentait, démontrant une scalabilité supérieure.
- L'algorithme a atteint des taux de convergence plus rapides, particulièrement visibles dans les graphiques IGD au fil des générations.
- La validation statistique via des Tests de Signe et des Tests de Rang des Sommes de Wilcoxon a confirmé la signification des améliorations (p < 0,05) pour la plupart des métriques, à l'exception de la MGD pour le marché DAX 100.
- L'analyse du temps de calcul a indiqué que bien que Python soit plus lent que C++, l'encodage et la logique proposés ont abouti à des temps d'exécution comparables ou meilleurs que les approches standards, même pour le grand jeu de données TSE.

Signification et Revendications
L'article affirme que la stratégie proposée offre une solution robuste pour l'optimisation de portefeuille à grande échelle sous contraintes de cardinalité. Les auteurs soutiennent que leur approche :

Fournit une convergence plus rapide et une capacité de recherche étendue par rapport aux méthodes traditionnelles.
Maintient une stabilité de performance à mesure que la taille du marché (nombre d'actifs) croît, là où les algorithmes standards ont tendance à se dégrader.
Gère efficacement l'arbitrage entre la découverte de l'ensemble optimal d'actifs et l'optimisation de l'allocation des poids grâce à sa reproduction phasée et son opérateur "Explorer".

L'étude conclut que si la formulation actuelle traite la CC et la BC, les travaux futurs pourraient incorporer d'autres contraintes réelles telles que les coûts de transaction et la liquidité, ce qui nécessiterait des modifications de ses mécanismes de réparation proposés.

Articles similaires