Méthodes de quasi-Monte Carlo et applications

Présentation du problème

Introduction

Peu après les méthodes de Monte Carlo, se sont développées dans les années 50 celles dites de quasi-Monte Carlo, leurs analogues déterministes. La nature stochastique et la non garantie de la borne de l'erreur sont les principaux désavantages de Monte Carlo. Comme le souligne Zaremba :``La justification de la pratique de Monte Carlo n'est pas basée sur la nature aléatoire de la procédure [...], mais sur l'équi-distribution [...]. Il doit exister des suites de points telles que l'erreur soit plus faible''. Le nom quasi-Monte Carlo fut employé pour la première fois dans un rapport de recherche en 1951 de Richtmyer. Roth, médaillé Fields en 1958, a déterminé en 1954 une vitesse de convergence optimale pour l'approximation des intégrales, ainsi qu'une suite, utilisant l'idée de Van der Corput, permettant une convergence rapide. Se sont alors développées au cours des années toutes sortes de suites, dites à discrépance faible, et de théorèmes de bornes. Contrairement à celles de Monte Carlo, les méthodes de quasi-Monte Carlo ont connu très peu d'applications, celles-ci se situant principalement en physique et plus récemment en finance.

Mes travaux passés

Le problème essentiel est l'absence d'un équivalent utilisable en pratique des intervalles de confiance de l'approche stochastique. En effet les bornes connues n'ont qu'un intérêt asymptotique et ne peuvent en général pas être utilisées en pratique.

Dans ces conditions, la majeure partie de notre travail s'est concentrée sur une combinaison des méthodes de Monte Carlo et quasi-Monte Carlo. Cette méthode peut être vue de deux manières : une utilisation des suites à discrépance faible comme technique de réduction de la variance dans les méthodes de Monte Carlo ou une perturbation aléatoire des méthodes de quasi-Monte Carlo. L'avantage est donc d'utiliser la vitesse de convergence des suites à discrépance faible tout en ayant un intervalle de confiance grâce à l'introduction de l'aléatoire. Nous avons pu obtenir plusieurs résultats théoriques sur la vitesse de convergence de cette méthode et étudier empiriquement les suites les plus efficaces parmi toutes les suites à discrépance faible connues.

Nous avons illustré la puissance de cette méthode sur plusieurs modèles : les réseaux de files d'attente multi-classes à forme produit et les réseau à pertes incluants notamment les systèmes cellulaires.

Les sujets sur lesquels je compte continuer à travailler

Mes publications dans ce domaine (pour une liste complète et à jour, voir la Liste des publications)

  1. B. Tuffin, Simulation accélérée par les méthodes de Monte Carlo et Quasi-Monte Carlo : théorie et applications. Thèse de Doctorat, Université de Rennes 1. Octobre 1997.
  2. B. Tuffin, On the Use of Low Discrepancy Sequences in Monte Carlo Methods. Monte Carlo Methods and Applications, Vol.2, Num.4, pages 295-320, 1996.

    3. Voir aussi la note "Comments on ``On the use of low discrepancy sequences in Monte Carlo methods''. Monte Carlo Methods and Applications. Vol.4, 1998.
  3. B. Tuffin, Variance Reduction Technique for a Cellular System with Dynamic Resource Sharing. In Proceedings of the 10th European Simulation Multiconference, p 467-471, Budapest, Hongrie, Juin 1996.
  4. B. Tuffin, Variance Reductions applied to Product-Form Multi-Class Queuing Networks. ACM Transactions on Modeling and Computer Simulation, Vol.7, Num.4, pages 478-500, 1997.
  5. B. Tuffin, A new Permutation Choice in Halton Sequences. Dans Monte Carlo and Quasi-Monte Carlo 1996, volume 127, Lecture Notes in Statistics, Springer Verlag, New-York, 1997.
  6. B. Tuffin, Variance Reduction Order Using Good Lattice Points in Monte Carlo Methods. Computing, Vol. 61, Num. 4, pages 371-378, 1998.
  7. B. Tuffin et L.M. Le Ny. Parallélisation d'une combinaison des méthodes de Monte Carlo et quasi-Monte Carlo et application aux réseaux de files d'attente. RAIRO: Recherche opérationnelle, Vol. 34, pages 8 5-98, 2000.
  8. B. Tuffin. A randomized Quasi-Monte carlo method for the simulation of product-form loss networks. Proceedings of the 9th International Conference on Telecommunication Systems, pages 468-478, Dallas, TX, USA, Mars 2001.
  9. C. Lécot and B. Tuffin. Quasi-Monte Carlo Methods for Estimating Transient Measures of Discrete Time Markov Chains. In the fifth International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Singapore, 2002.

Quelques Références bibliographiques

  1. Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods, 7, 86-112,1967. CBMS-SIAM 63, Philadelphia, 1992.
  2. Sobol', I.M., On the distribution of points in a cube and the approximate evaluation of integrals, USSR Computational Math. and Math. Phys., 1967.
  3. Sloan, I. H. and Kachoyan, P. J., Lattice Methods for Multiple Integration: Theory, Error Analysis and Examples. SIAM Journal of Numerical Analysis , 24(1):116-128,1987.

Quelques liens intéressants

Retour à la page principale
btuffin@irisa.fr