A Portfolio Optimization Model

Ce mémoire étudie le problème d'optimisation de portefeuille moyenne-variance (MV) de Markowitz avec contrainte de cardinalité et bornes sur les variables. C'est un problème NP-Difficile modélisé à l'aide d'un programme MIQP. La performance du portefeuille MV optimal généré est évaluée à l'aide de la méthode exacte Branch-and-Bound (BB) qui fournit une solution optimale globale en comparaison avec les méthodes les plus performantes de la littérature, comme l'écart absolu moyen, la différence moyenne de Gini et la valeur conditionnelle à risque. Ces méthodes alternatives utilisent différentes mesures de risque. De plus, nous avons appliqué pour la première fois une approximation externe (Outer Approximation - OA) au problème MV et nous avons proposé une nouvelle heuristique de branchement afin de faire face à la difficulté de résolution des grandes instances du problème. Ces dernières approches utilisent des techniques de décomposition. La classification des résultats numériques montre que la méthode exacte (BB) est efficace pour les problèmes de petite taille, que la méthode OA surpasse les autres méthodes pour les instances de taille moyenne et que l'heuristique proposée de branchement est efficace pour les instances de taille importante où les méthodes BB et OA ne sont pas applicables. À cause de la complexité de la structure du problème, les méthodes exactes sont incapables de résoudre les problèmes de taille importante dans un temps raisonnable. C'est pourquoi les méthodes heuristiques sont développées pour faire un compromis entre la précision de la solution et le temps de résolution.

Abstract

This thesis investigates the Markowitz' Mean-Variance (MV) portfolio optimization model with cardinality constraint and bounds on variables which is MIQP model and known as an NP-Hard problem. We evaluate the performance of the optimal MV-portfolio generated by Branch-and-Bound (BB) algorithm as an exact method which provides a global optimal solution in comparison with the most effective alternative methods in literature such as Mean Absolute Deviation, Gini Mean Difference and Conditional Value at Risk. These alternative methods make use of different risk measures. In addition, we applied an Outer Approximation (OA) algorithm for the MV problem for the first time as well as proposing a new Heuristic Branching algorithm to deal with the difficulty of the problem for large instances. The later approaches utilize some sort of problem decomposition. With the classification of the numerical results, we showed that the exact method (BB) is efficient for small size problem while for medium size problem the OA outperforms the other methods and the proposed Heuristic Branching algorithm is efficient for large size problems since BB and OA are not applicable in this category. Due to the complexity of the problem structure, exact methods are not capable of solving large size problem in a reasonable time budget. Thus, heuristic methods are developed to trade-off between the precision of the solution and computational time.