Sur l’optimisation de la méthode de Monte-Carlo
En mathématiques financières, la méthode de Monte-Carlo est régulièrement utilisée, en particulier sur des problématiques de valorisation (ou « pricing ») de produits dérivés. Si cette méthode a bien d’autres applications, la série d’articles que nous allons présenter ici vise à accélérer la convergence de la méthode de Monte-Carlo (méthode dont la variance de l’estimation et la complexité de l’algorithme sont élevées ; cf. l’encadré ci-contre). Il existe plusieurs méthodes pour optimiser la vitesse de convergence de l’algorithme de Monte-Carlo, citons par exemple les méthodes de réduction de variance. Mais il existe d’autres méthodes, plus originales, reposant sur la Théorie du Transport et de l’Echantillonnage ou sur la méthode statistique de Romberg.
Nos collaborateurs chercheurs ont notamment travaillé sur ces méthodes, que nous vous introduirons dans cet article, après avoir rappelé le principe de base de la méthode.
Complexité d’un algorithme
La théorie de la complexité est un domaine des mathématiques qui s’intéresse à la quantité de ressources et de temps nécessaire pour résoudre un problème. Dans le cas d’un algorithme, il va s’agir du nombre d’opérations à effectuer pour que l’algorithme aboutisse à une solution.
Il n’est cependant pas possible de déterminer a priori et de façon générique le nombre exact d’opérations nécessaires. C’est pourquoi la complexité s’exprime souvent en O, notation de Landau. Cette notation renvoie à la domination d’un élément par un autre. Par exemple, un algorithme avec une complexité en O(n) aura besoin de moins de kn opérations (avec k entier) pour converger, ce qui est plus rapide que O(n²) mais plus lent que O(n1/2).
Méthode de Monte-Carlo
La méthode de Monte-Carlo, inventée mais non théorisée par Buffon au XVIIIè siècle pour estimer π, est surtout utilisée pour déterminer numériquement une intégrale. En mathématique financière, cette méthode utilisée pour la valorisation des options, trouve un cadre naturel d’application. En effet, le principe de la méthode est d’assimiler l’intégrale de valorisation au calcul de l’espérance d’une variable aléatoire ; puis, en effectuant un grand nombre de tirages de cette variable, en moyennant les résultats, la moyenne converge vers l’espérance de la variable aléatoire, avec une vitesse de convergence et une marge d’erreur connue, via la Loi des Grandes Nombres.
L’un des exemples le plus courant, pour illustrer la méthode de Monte-Carlo est la mesure de la surface d’un lac. Imaginons qu’une armée napoléonienne se retrouve en face d’un lac contenu dans un pré. Le général, qui a du temps à perdre, souhaite déterminer la surface du lac, mais ne dispose pas d’unité du Génie pour prendre des mesures. Il ordonne alors à ses canons de faire feu aléatoirement dans le pré (notre général a également de la poudre et des boulets à perdre). L’inventaire, après feu, des boulets tombés à côté du lac et le total de boulets tirés permettent d’obtenir une estimation de la taille du lac. En effet, le rapport :
constitue une estimation de la surface qu’occupe le lac par rapport à la surface du pré. Ainsi, la formule suivante est un estimateur de la surface du lac :
La qualité de l’estimation dépend alors de deux paramètres : le nombre de boulets tirés (et, de façon plus générale, le nombre de tirages effectués) et la qualité du tirage aléatoire. Dans notre exemple, la qualité du tirage aléatoire renvoie à la capacité des artilleurs a bien couvrir l’intégralité de la surface du pré.
Cette problématique du tirage aléatoire est loin d’être anodine. En effet, la notion de tirage parfaitement aléatoire est une notion purement théorique. Il est possible d’effectuer des tirages quasi-aléatoires mais aucune machine n’est capable de simuler un tirage aléatoire. Le recours à la méthode de Monte-Carlo est donc toujours légèrement biaisé.
Par exemple, on utilise cette méthode pour valoriser un call de la façon suivante : une simulation du prix du sous-jacent du call va être effectuée, en tirant aléatoirement des rendements qui seront cumulés pour obtenir la trajectoire de prix. À partir de cette trajectoire de prix, il est possible d’observer la valeur prise par le payoff pour chaque simulation. La moyenne de chaque valeur de payoff donne alors une estimation du prix du call. Si la méthode de Monte-Carlo permet d’aboutir sur des simulations relativement robustes, elle requiert des ressources machines relativement importantes, et souvent, beaucoup de temps.
On comprend alors qu’en Finance plus qu’ailleurs, la question de l’optimisation de la méthode de Monte-Carlo est essentielle.
Monte-Carlo et le pricing d’options
Pour fixer les idées, concentrons-nous sur cette question centrale de valorisation d’une option.
Le sous-jacent, qui peut être un indice, le cours du pétrole, du gaz, d’une action, ou un taux de change, est en général solution d’une équation de type :
dXt=b(Xt)dt +(Xt)dWt , X0=xR,
où b et sont suffisamment régulières.
Le prix d’une option de maturité T sur le sous-jacent X est tout simplement l’espérance de f(XT) où f est la fonction donnant le payoff de l’option. Mathématiquement, cette espérance est notée E[f(XT)] (cf. [1]).
Cette espérance, à part dans des cas très rares, ne se calcule pas avec des formules fermées, mais nécessite l’utilisation de la Méthode de Monte-Carlo.
Optimisation de la méthode de Monte-Carlo par échantillonnage
En effet, au lieu de calculer E[f(XT)], on calcule E[f(Xn,T)], où Xn,T est une solution qui approche notre processus Xt, via ce que l’on appelle le schéma discrétisé, qui consiste à découper l’intervalle de temps [0,T] en n intervalles, et d’approcher la solution point par point.
La méthode de Monte-Carlo permet donc de calculer E[f(Xn,T)], avec n tirages indépendants de la variable aléatoire Xn,T, puis, grâce au théorème de la Limite Centrale, on obtient l’espérance E[f(XT)], et donc le prix de l’option, dans un intervalle de confiance aussi petit que l’on veut, avec une probabilité de 95%.
Pour le schéma d’Euler, qui est le schéma de discrétisation le plus classique et le plus connu, la complexité optimale de cette méthode est de l’ordre de n3.
Une récente méthode de réduction de complexité a été développée en 2012 par Ahmed Kebaier et Mohamed Ben Alaya (Cermics, LAGA), qui collaborent avec MPG Research, le pôle Recherche de MPG Partners (*). Cette méthode consiste en une extrapolation de la méthode statistique de Romberg [2] et utilise deux schémas d’Euler imbriqués, c’est-à-dire, un premier schéma d’Euler découpant l’intervalle en n intervalles de taille 1/n et m intervalles de tailles 1/m avec la condition m<<n.
La méthode permet de choisir n et m de façon optimale permettant de trouvze une solution Xn,m,T qui donne le prix de l’option avec une complexité de l’ordre de n5/2 !
Ceci implique naturellement un gain de temps et d’efficacité.
La figure ci-contre, dans une échelle logarithmique, illustre ce gain en performance par rapport au Monte-Carlo classique, pour la valorisation d’options asiatiques. Ce graphique compare le temps nécessaire au calcul (ordonnée) relativement à une longueur d’intervalle de confiance (abscisses). On voit clairement que pour un intervalle de confiance de 6.10-2, la méthode de A. Kebaier et de M. Ben Alaya permet de gagner 3,33 plus de temps et pour un intervalle de confiance de 2.10-2 on gagne 10 fois plus de temps !
L’avantage de cette méthode est qu’elle s’applique de manière identique en grande dimension, ce qui permet d’effectuer du Monte-Carlo optimisé pour des multi-sous-jacents ou pour des sous-jacents solutions de modèles à volatilités stochastiques.
En effet, en comparant les deux méthodes pour un sous-jacent suivant le modèle de Heston, on obtient les résultats résumés dans le tableau ci-contre, où les colonnes représentent respectivement le nombre de discrétisation (n), le prix (on remarque que les prix sont quasi-identiques avec les deux méthodes, ce qui est normal), l’intervalle de confiance choisi, et le temps nécessaire aux calculs.
Il est clair que la méthode de statistiques de Romberg extrapolée est bien plus efficace et offre un gain en temps substantiel. Cette méthode s’implémente aisément [3], ce qui la rend très attractive.
Théorie du Transport Optimal
La théorie du transport est une branche de l’économie mathématique qui s’intéresse à l’étude du transfert optimal de biens et à l’allocation optimale de ressources. C’est une problématique qui a été introduite par Monge à la fin du XVIIIè via son mémoire sur la Théorie des Déblais & des Remblais. Dans cet ouvrage, Monge étudiait comment trouver le déplacement optimal pour un tas de sable. Cette première ébauche a été reprise par Kantorovitch, mathématicien et économiste, à propos de l’allocation optimale des ressources. De nos jours, la problématique sur laquelle se pose la théorie du transport s’exprime de la façon suivante :
Soit usines et mines de fer et la fonction de coût pour un déplacement d’un point à un point . Quels sont les déplacements à effectuer pour que chaque usine soit alimentée pour un coût minimal, sachant qu’une usine ne peut être alimentée que par une seule mine.
Graphiquement, la théorie du transport se représente de la façon suivante :
Solution incorrecte
Solution optimale
Solution possible mais non optimale
La recherche de l’optimum est relativement simple lorsque le nombre de points (ici mines et usines) est faible, comme dans le cas de l’exemple graphique proposé. En effet, il n’y a dans ce cas que 24 possibilités correctes différentes et une résolution où le coût du transport est calculé pour chaque possibilité est envisageable. Cependant, une telle résolution devient délicate à envisager avec un plus grand nombre de points. De plus, le problème peut être complexifié à souhait (possibilité pour une mine d’alimenter plusieurs usines, possibilité d’introduire des heures d’ouverture, …) et la résolution par calcul de toutes les possibilités devient impossible.
Théorie du Transport Optimal, Echantillonnage et Méthode de Monte-Carlo
Le lien entre les théories présentées précédemment et la méthode de Monte-Carlo n’est pas tout à fait immédiat, les méthodes étant issues de domaines variés (électronique, économique, probabilité). En particulier, l’échantillonnage et la recherche du transport optimal ne paraissent pas être des accélérateurs de la méthode de Monte-Carlo. Le principe de la méthode de Monte-Carlo reste le même, c’est-à-dire qu’il s’agira toujours d’effectuer des simulations, par exemple de rendements afin de déterminer une valorisation dans le cas des mathématiques financières. Ce principe revient donc à parcourir aléatoirement l’espace des rendements afin d’aboutir à la moyenne après un grand nombre de tirages. Dans l’implémentation informatique de la méthode de Monte-Carlo, la méthode revient à parcourir quasi-aléatoirement l’espace des rendements afin d’aboutir à la moyenne après un grand nombre de tirages, puisqu’il n’est pas possible de construire une fonction parfaitement aléatoire en informatique. Le recours à l’échantillonnage à la théorie du transport optimal permet d’accélérer la façon de paver l’espace des rendements et donc de le parcourir plus rapidement, ce qui optimise la convergence de l’algorithme de Monte-Carlo. Puisque dans la méthode brute, la façon de paver l’espace est quasi-aléatoire, mais non optimisée, l’idée ici est, en recherchant le bon échantillonnage et en l’optimisant, de paver l’espace de façon quasi-aléatoire toujours, mais optimale. Ainsi, si en termes de temps de calcul, l’algorithme est un peu plus long au début (cas d’un Monte-Carlo avec peu de tirages, par exemple), plus le nombre de tirages va augmenter et plus l’algorithme va converger rapidement si l’échantillonnage a été bien effectué. Le recours à l’échantillonnage et à la théorie du transport optimal permet de réduire le nombre de tirages à effectuer pour permettre une bonne convergence (en espérance) de l’algorithme de Monte-Carlo. Le nombre de tirages étant plus faible la convergence (en complexité) de l’algorithme se retrouve donc meilleure.
Pour plus d’informations à ce sujet, contacter research@mpg-partners.com
*MPG Research : soucieux de créer une marque forte, de contribuer au débat de place et de développer un service d’expertise métier de haut niveau, MPG Partners développe son programme de Recherche en synergie avec de prestigieux laboratoires et départements de Recherche Quantitative en Banque et en Assurance.
Nos partenaires aujourd’hui sont l’Institut Louis Bachelier, le LAGA (Paris 13) ainsi que plusieurs laboratoires d’écoles d’ingénieurs françaises.
Références
[1] D. Lamberton, B. Lapeyre, Introduction au Calcul Stochastique Appliqué à la Finance, 3e édition, (2012)
[2] A.Kebaier, Statistical Romberg Extrapolation: A New Variance Reduction Method and Applications to Option Pricing,Ann. Appl. Probab. 15 (2005)
[3] M. Ben Alaya, K,Hajji & A.Kebaier , Importance Sampling and the Statistical Romberg method. Preprint (2013)