LAIL-JDD-DM
Programmation quadratique non convexe
Lorsque nous avons démarré notre étude, nous nous sommes familiarisés avec la notion de convexité, et aux conséquences de son absence, à partir de la Programmation Quadratique en Variables Entières (PQVE). En effet, en dimension un, la parabole fournit une représentation graphique simple et directe de la notion de convexité. La première idée naturelle est de transformer ce problème en un problème équivalent plus simple. Pour le cas quadratique, sous contraintes linéaires, en variable binaires, les travaux de Billionnet et al. [27], en 2009, présentent une réformulation quadratique convexe (la méthode QCR), à l’aide de matrices semi-définies positives. Ce problème convexe équivalent peut alors être résolu par un Branch & Bound classique dont la fonction d’évaluation correspond à la relaxation continue (convexe) du problème équivalent. L’approche a été étendue aux variables entières dans Billionnet et al. [25] en 2012, puis aux variables entières sous contraintes quadratiques dans Billionnet et al. [26] et Elloumi et Lambert [44]. Les travaux d’habilitation d’Amélie Lambert [69] montrent comment construire une suite de problèmes, paramétrés par des matrices semi-définies positives, équivalents au problème initial et dont la relaxation (convexe) est de plus en plus fine. Elle montre la convergence de ces problème relâchés convexes vers l’optimum global, à près du problème quadratique (non convexe) initial. Un autre intérêt pratique de ce type d’approche est que la résolution de ces sous-problèmes plus simples, peut être sous-traitée à un algorithme ou à un solver dédiés, afin d’améliorer la performance. Une autre reformulation du problème quadratique non convexe sous contraintes linéaires est proposée par Quadri et Soutil [92], ainsi que Soutil et al. [107]. Ils transforment tout d’abord le problème en un problème séparable équivalent en variables mixtes.
Programmation polynomiale
Un programme mathématique est polynomial si les fonctions du problèmes (objectifs et contraintes) sont des polynômes de degré fini dans les variables de décision. Bien que nous n’ayons pas utilisé directement ces résultats dans notre étude, nous observons que certaines idées décrites dans le cas quadratiques s’appliquent au cas polynomial. Par exemple, comme dans le cas cas quadratique, nous cherchons à reformuler et à linéariser le problème. Dans le cas en variables binaires, les travaux de Glover et Woolsey [58] et la RLT de Sherali et Adams [103] fournissent des relaxations linéaires fines. Ce cadre est étendu à la programmation polynomiale par Sherali et Adams [102]. Plus récemment, les travaux de Lazare [71] proposent plusieurs techniques de reformulation et/ou de linéarisation de programmes polynomiaux en variables binaires. Il étend notamment la méthode de relaxation convexe quadratique (QCR) au cas polynomial (méthode PQCR). Cafieri et al. [35] cherchent à réduire le nombre de contraintes RLT. Ils montrent comment générer un nombre réduit de contraintes, permettant ainsi d’améliorer les performances de l’algorithme de Branch & Bound. Ils nomment la procédure Reduced RLT (ou rRLT). Nous nous intéressons également aux relaxations convexes des monômes. La meilleure relaxation possible correspond, par définition, à l’enveloppe convexe de la fonction considérée, qui est cependant difficile à expliciter dans le cas général.
Etat de l’art financier ELBA
Ma carrière dans l’industrie financière m’a, de longue date, sensibilisé aux problèmes d’optimisation dans ce secteur. De manière informelle, la question de l’allocation d’une ressource (fonds, quantité d’actif), soumise à des contraintes (de temps, coût, risque etc.) afin d’optimiser une fonction objectif (profit, rendement, utilité, risques) est au cœur des problématiques financières, scientifiques et réglementaires. Un autre aspect qui est structurellement ancré dans la finance, et même dans la plupart des sciences humaines, est l’incertain. Le prix d’une action est modélisé par une distribution probabiliste, reflétant l’univers des possibles, mais nul ne sait ce que sera le prix exact au temps t, vu d’aujourd’hui. Par conséquent pour modéliser aujourd’hui, le prix des contrats à terme (instrument financier dont la valeur est fonction du prix futur d’un actif ou plusieurs actifs), l’opérateur de marché a deux grandes avenues devant lui : la première est de répliquer le contrat, via une stratégie équivalente, ou bien simplement en le décomposant en d’autres actifs sousjacent dont le prix est connu (ou répliqué) avec certitude. Il suppose alors que le prix est exactement (ou très proche en pratique) de celui de la stratégie de réplication équivalente, sinon un autre opérateur de marché, ne manquerait pas d’exploiter la différence à son profit, sans prendre aucun risque, et cet argument est fondamental, réduisant ainsi l’écart de prix. Cet argument est connu sous le nom d’absence d’arbitrage. Il est le pilier qui soutient de nombreux prix et comportements relatifs à des produits dérivés (futures, forward, taux de change, réplication d’indice, basis-trades etc.) sur différentes classes d’actif. La deuxième direction est de modéliser les actifs fondamentaux (actions, taux, devises) qui composent le contrat, par des variables aléatoires stochastiques, ce qui impose des hypothèses sur leur distribution de probabilité et, par calcul différentiel stochastique ou par simulation de Monte-Carlo, d’obtenir, le barycentre des prix possibles pondérés par leur probabilité qui n’est autre que l’espérance mathématique du prix du contrat à terme. En pratique, la force d’un modèle réside bien évidemment dans sa rigueur mathématique et dans la validité de ses hypothèses, mais aussi et surtout dans le consensus qu’il fait, c’est à dire le nombre d’opérateurs de marché qui l’utilisent. Un exemple prégnant de ces cinquante dernières années est celui de la Formule Black et Scholes [28] et Merton [81]. Elle est la formule de calcul du prix d’une option européenne la plus utilisée à Wall Street. Pour rappel, une option est le droit (et non l’obligation) d’acheter (ou de vendre) un actif à un prix et à une date donnés, fixés aujourd’hui. Le prix de cette option d’achat (ou de vente) est l’objet de la formule. Bien qu’elle fasse des hypothèses fausses en pratique sur la constance des variables qui la composent, notamment la volatilité, qui ont fait l’objet d’une littérature abondante (cf. travaux de Dupire et al. [43] sur la volatilité locale), elle a régné quasiment sans partage sur les marchés depuis son introduction. Et nous avons vécu dans le monde (ou au moins le paradigme de marché) de Black & Scholes & Merton. Ce qui suppose que les prix d’actif ont une distribution lognormale (leur logarithme est normal) et donc qu’ils ne peuvent en aucun cas, devenir négatifs. Lorsque les taux d’intérêts sont entrés durablement dans le territoire négatif, entre 2014 et 2021, après certains ajustements temporaires, les opérateurs de marché ont été forcés de l’abandonner (temporairement ?) et se sont tournés en masse, vers les travaux fondateurs et vers la formule de Bachelier [11] datant de 1900. Une légitimation posthume pour le mathématicien dont les travaux fondateurs ont été redécouverts après la seconde guerre mondiale, et qui a connu une carrière académique difficile, racontée par Mandelbrot et Hudson [75]. En conclusion, l’incertain et sa modélisation sont au cœur des préoccupations des institutions financières. Par conséquent, nous nous sommes intéressés, avec ma directrice de thèse, spécialisée en optimisation combinatoire et déterministe, aux applications financières possibles de mon sujet. Nous avons cherché parmi les problèmes que j’avais rencontrés et qui pouvaient être modélisés via la programmation mathématique, dans un cadre déterministe. Ce dernier point est beaucoup plus discriminant. Historiquement, l’optimisation quadratique est liée à l’allocation d’actifs suite aux travaux fondateurs de Markowitz [76]. Ils indiquent comment choisir la pondération des actifs et comment composer son portefeuille, afin de maximiser le rendement, pour un niveau donné de risques, mesuré par une fonction quadratique (la variance). Nous nous sommes cependant intéressés, à un autre problème auquel j’ai été confronté personnellement, qui est celui de l’Ecoulements de Larges Blocs d’Actifs (ELBA), également appelé, Liquidation Optimale de Portefeuille (LOP). Il consiste à vendre ou à acheter, une très grande quantité d’actif (le bloc) dans un temps donné, discret (il y a nombre fini d’occasions de vente) ou continu. Dans la littérature financière, ELBA a déjà été largement étudié, sous différents angles. Le premier sujet d’étude est l’impact des larges blocs sur le marché. Quel est la performance de l’actif durant et après la vente de blocs, à différents horizons de temps ? Quel est le temps de retour à l’équilibre d’un marché suite à l’écoulement d’un large bloc ? Guthmann et Bakay [59], Dann et al. [40], Gemmill [56] fournissent des études empiriques à ces questions. Par analogie avec un lac calme, ces approches étudient les remous provoqués par le lâché d’un ou plusieurs pavés ainsi que leurs évolutions temporelles. Dans ce contexte, notre objectif est donc poser le plus délicatement possible ce pavé dans l’eau, pour en minimiser les remous. Une deuxième voie s’attache à l’étude de marchés spécifiques dédiés à ce type de transactions, connus sous le nom d’upstairs market , ainsi que leur récents alter ego électroniques, les dark pools . Le lecteur peut se référer à Madhavan et Cheng [74] et plus récemment Mishra [86] ont abordé le problème ELBA sur ces marchés. Une troisième approche s’appuie sur la modélisation du comportement des différents participants (opérateur de marché, broker, spécialiste etc.) pour déterminer l’état d’équilibre et en étudier les conditions d’existence et d’unicité. Le lecteur peut se référer à Seppi [100] et Keim et Madhavan [66]. Une quatrième voie, s’attachant à la modélisation du carnet d’ordre (Limit Order Book), qui trie les meilleurs offres d’achat ou de vente avec leur volume respectif, a été introduit par Obizhaeva et Wang [89]. Des approfondissements dans cette direction sont proposés dans Alfonsi et al. [5, 6] et Obizhaeva et Wang [90]. Enfin, de nombreux articles abordent ELBA en temps continu, qui devient un problème de contrôle stochastique : Barles [12], Vath et al. [113], Seydel [101], Kharroubi et Pham [67], Gatheral [52], Gatheral et Schied [53], pour ne citer que quelques références. Nous nous sommes placés dans cette étude, en temps discret et en variables entières. Dans ce cadre, la question de la décomposition optimale du blocs en plus petits ordres afin de maximiser le produit de la vente, ou de manière équivalente, de minimiser son impact sur les prix, a été traité dans des articles fondateurs de Bertsimas et Lo [23] et Almgren et Chriss [7], Almgren [8]. Ils introduisent un prix d’actif stochastique dont la dynamique dépend de la taille de l’ordre précédent sur le marché. La majorité des modèles qui font échos à ces deux articles, font la distinction entre l’impact temporaire sur le prix de l’actif, du aux déséquilibres temporaires entre l’offre et la demande, et l’impact permanent qui reflète l’effet sur le prix des informations transmises aux participants de marché par nos actions d’écoulement. Leur résolution est parfois fondée sur la programmation dynamique. Cependant, dans la plupart des travaux, les fonctions de pénalisation (impact sur les prix) sont linéaires ou suivent une loi de puissance. La question de la «mémoire du marché», via la modélisation de l’information qui lui est transmise occupe également une place centrale. On rencontre principalement dans la littérature, soit des fonctions de pénalisations à mémoire courte, dans le sens où la pénalité au temps tk est en g(xk) et ne dépend que des xk unités d’actifs écoulées en tk, ou bien avec une mémoire longue séparée (ex : Almgren et Chriss [7]) pour lesquelles la pénalité en tk est de la forme Pk j=1 g(xj ). Comme indiqué précédemment, nous nous sommes placés, pour cette application, dans un cadre déterministe. Nous ne cherchons donc pas à prédire l’évolution du prix de l’actif, que l’on suppose connue (ou correctement estimée) avant toute optimisation. Ce cadre a été utilisé récemment par Boyd et al. [32] pour le problème d’allocation optimale de portefeuille. Du point de vue du praticien financier, cette hypothèse n’est réaliste que pour des marchés très calmes (faible volatilité), pour lesquels aucune nouvelle économique ou autre, n’est susceptible d’influencer les cours de l’actif considéré. Bien qu’elle puisse paraître assez restrictive en première approche, elle fournit, dans notre expérience, un environnement très favorable à l’écoulement de larges blocs. En fait, la vente de blocs se pratique principalement, dans l’environnement de marché le plus calme possible, afin justement, de ne pas éveiller l’attention des autres opérateurs de marché. A contrario, dans un marché volatil ou pour l’écoulement d’un bloc d’un actif peu liquide (qui n’est pas très fréquent), le résultat du produit de la vente du bloc dépend principalement de la dynamique des prix, quelque soit la stratégie d’exécution. Une autre situation, bien plus rare mais plus confortable, est celle où nous sommes à contre-sens du marché (vente d’un bloc d’actions qui est très recherché). Dans cette situation, la pénalité à écouler un bloc est faible donc la stratégie de vente importe peu et le prix final est dominé par l’évolution des prix de l’actif. Ce cas, très rare en pratique, ne présente pas d’intérêt pour la programmation mathématique. Enfin, cette hypothèse permet de découpler la réponse des participants de marché à la liquidation, qui constitue notre objet principal d’étude, de l’évolution des prix de l’actif. Par conséquent les méthodes de résolutions, les algorithmes et les techniques d’optimisation présentées dans cette thèse sont valables pour tout vecteur de prix. Par conséquent, l’application financière de notre sujet est simplement de montrer comment optimiser la liquidation d’un portefeuille mono sous-jacent, sachant que les évolutions de prix sont correctement estimées, sans se soucier de comment ces estimations sont faites. Nous avons également inclus le cas des prix de l’actif constant durant la liquidation, à titre de benchmark dans les expérimentations numériques, afin de mesurer la dissémination de l’information dans le marché. Hors de la finance, le vecteur de prix p peut être interprété comme le comportement standard de l’environnement, sans aucune influence de notre fait. Dans ce contexte, on suppose que le comportement standard est connu et on cherche à étudier, comment nos actions qui fournissent des informations à l’environnement à mémoire parfaite, influencent sa réponse. Notre objectif est alors de minimiser l’impact négatif de nos actions sur la métrique de sortie, ou de manière équivalente de maximiser cette métrique.
|
Table des matières
Introduction
1 Formulation du problème
1.1 Formulation et complexité
1.2 Intérêt du problème
2 Etat de l’art
2.1 Programmation quadratique non convexe
2.2 Programmation polynomiale
2.3 Cas général
2.4 Etat de l’art financier ELBA
3 Programmation dynamique
3.1 Rappels de Programmation Dynamique
3.2 Résolution exacte
3.3 Résolutions approchées du problème discret
3.3.1 Heuristiques naïves
3.3.2 Méthode DP en deux étapes (TSDP)
3.3.3 Algorithme de recherche locale (ILS)
3.3.4 LocalSolver
3.3.5 Taille du grain et complexité
3.4 Résolutions approchées du problème continu
3.4.1 Gradient projeté
3.4.2 Solver libre NLopt
3.5 Borne supérieure naïve
3.5.1 Résolution du problème séparé
3.5.2 Autres résultats théoriques
3.6 Conclusion
4 Convexification du problème
4.1 Rappels de factorisation
4.2 Factorisation du problème
4.2.1 Factorisation pour le cas convexe à deux variables
4.2.2 Factorisation du produit bilinéaire pour le cas à trois variables
4.2.3 Factorisation dans le cas général du problème P NSN,M
4.3 Relaxation convexe
4.3.1 Rappels de convexité
4.3.2 Convexification des problèmes factorisables : cas général
4.3.3 Application au problème traité P NSN,M
4.4 Linéarisation du minimum
4.5 Algorithmes de Branch & Bound .
4.5.1 Algorithme Principal
4.5.2 Exploration en largeur d’abord
4.6 Conclusion .
5 Comparaison numériques des méthodes
5.1 Cadre des expérimentations numériques
5.1.1 Outils informatiques et choix des solvers
5.1.2 Taille et nomenclature d’instances
5.1.3 Paramétrages statiques et origine des données
5.1.4 Fonctions de pénalité et calibration
5.1.5 Justification du choix des paramètres L et H
5.2 Petites et moyennes instances
5.2.1 Résolution exacte des petites et moyennes instances
5.2.2 DP à gros grain et recherche dans un bandeau
5.2.3 TSDP en utilisant la relaxation continue
5.2.3.1 Comparaison du gradient projeté et de NLopt
5.2.3.2 Taille du bandeau pour la méthode hybride
5.2.4 Résultats agrégés des méthodes de DP
5.2.5 Résolution par convexification
5.2.5.1 Très petites instances
5.2.5.2 Résultats agrégés de convexification
5.3 Grandes et très grandes instances
5.3.1 Limitations en espace (mémoire)
5.3.2 Résultats agrégés des méthodes de DP
5.3.3 Résultats de convexification
6 Conclusions et perspectives
6.1 Conclusion générale
6.2 Perspective
Télécharger le rapport complet
