Complexité basée sur l'information - Information-based complexity

La complexité basée sur l'information ( IBC ) étudie les algorithmes optimaux et la complexité de calcul pour les problèmes continus qui se posent en sciences physiques , en économie , en ingénierie et en finance mathématique . IBC a étudié des problèmes continus tels que l' intégration de chemin , les équations aux dérivées partielles , les systèmes d' équations différentielles ordinaires , les équations non linéaires , les équations intégrales , les points fixes et l' intégration à très haute dimension . Tous ces problèmes impliquent des fonctions (typiquement multivariées) d'une variable réelle ou complexe . Puisqu'on ne peut jamais obtenir une solution de forme fermée aux problèmes d'intérêt, il faut se contenter d'une solution numérique. Puisqu'une fonction d'une variable réelle ou complexe ne peut pas être entrée dans un ordinateur numérique, la solution de problèmes continus implique une information partielle . Pour donner une illustration simple, dans l'approximation numérique d'une intégrale, seuls des échantillons de l'intégrale en un nombre fini de points sont disponibles. Dans la solution numérique d'équations aux dérivées partielles, les fonctions spécifiant les conditions aux limites et les coefficients de l'opérateur différentiel ne peuvent être échantillonnées. De plus, ces informations partielles peuvent être coûteuses à obtenir. Enfin, les informations sont souvent contaminées par le bruit.

L'objectif de la complexité basée sur l'information est de créer une théorie de la complexité informatique et des algorithmes optimaux pour les problèmes avec des informations partielles, contaminées et tarifées, et d'appliquer les résultats pour répondre à des questions dans diverses disciplines. Des exemples de ces disciplines comprennent la physique , l'économie, la finance mathématique, la vision par ordinateur , la théorie du contrôle , la géophysique , l'imagerie médicale , les prévisions météorologiques et les prévisions climatiques , et les statistiques . La théorie est développée sur des espaces abstraits, généralement des espaces de Hilbert ou de Banach , alors que les applications sont généralement destinées à des problèmes à plusieurs variables.

Les informations étant partielles et contaminées, seules des solutions approximatives peuvent être obtenues. IBC étudie la complexité des calculs et les algorithmes optimaux pour des solutions approximatives dans divers contextes. Étant donné que le paramètre le plus défavorable conduit souvent à des résultats négatifs tels que l'insolvabilité et l'insurmontabilité, les paramètres avec des assurances plus faibles telles que la moyenne, le probabiliste et la randomisation sont également étudiés. L' informatique quantique continue est un domaine relativement nouveau de la recherche IBC .

Aperçu

Nous illustrons quelques concepts importants avec un exemple très simple, le calcul de

${\ displaystyle \ int _ {0} ^ {1} f (x) \, dx.}$

Pour la plupart des intégrands, nous ne pouvons pas utiliser le théorème fondamental du calcul pour calculer l'intégrale analytiquement; nous devons l'approcher numériquement. Nous calculons les valeurs de en n points ${\ displaystyle f}$

${\ displaystyle [f (t_ {1}), \ dots, f (t_ {n})].}$

Les n nombres sont les informations partielles sur l'intégrale vraie. Nous combinons ces n nombres par un algorithme combinatoire pour calculer une approximation de l'intégrale. Voir la monographie Complexité et information pour plus de détails. ${\ Displaystyle f (x).}$

Parce que nous n'avons que des informations partielles, nous pouvons utiliser un argument d'adversaire pour nous dire quelle doit être la taille de n pour calculer une -approximation. En raison de ces arguments basés sur l'information, nous pouvons souvent obtenir des limites strictes sur la complexité des problèmes continus. Pour des problèmes discrets tels que la factorisation d'entiers ou le problème du voyageur de commerce, nous devons nous contenter de conjectures sur la hiérarchie de la complexité. La raison en est que l'entrée est un nombre ou un vecteur de nombres et peut donc être entrée dans l'ordinateur. Ainsi, il n'y a généralement pas d'argument adversaire au niveau de l'information et la complexité d'un problème discret est rarement connue. ${\ displaystyle \ epsilon}$

Le problème de l'intégration univariée était uniquement à titre d'illustration. L'intégration multivariée est importante pour de nombreuses applications. Le nombre de variables se chiffre en centaines ou en milliers. Le nombre de variables peut même être infini; on parle alors d'intégration de chemin. La raison pour laquelle les intégrales sont importantes dans de nombreuses disciplines est qu'elles se produisent lorsque nous voulons connaître le comportement attendu d'un processus continu. Voir par exemple, l'application à la finance mathématique ci-dessous.

Supposons que nous voulons calculer une intégrale en d dimensions (les dimensions et les variables sont utilisées de manière interchangeable) et que nous voulons garantir une erreur au plus pour n'importe quel intégrande dans une classe. La complexité de calcul du problème est connue pour être d'ordre (Ici, nous comptons le nombre d'évaluations de fonctions et le nombre d'opérations arithmétiques, c'est donc la complexité temporelle.) Cela prendrait de nombreuses années pour des valeurs même modestes de La dépendance exponentielle sur d est appelé la malédiction de la dimensionnalité . Nous disons que le problème est insoluble. ${\ displaystyle \ epsilon}$${\ displaystyle \ epsilon ^ {- d}.}$${\ displaystyle d.}$

Nous avons énoncé la malédiction de la dimensionnalité pour l'intégration. Mais une dépendance exponentielle à d se produit pour presque tous les problèmes continus qui ont été étudiés. Comment pouvons-nous essayer de vaincre la malédiction? Il y a deux possibilités:

• Nous pouvons affaiblir la garantie que l'erreur doit être inférieure à (paramètre du pire des cas) et nous contenter d'une assurance stochastique. Par exemple, nous pourrions uniquement exiger que l'erreur attendue soit inférieure à (paramètre de cas moyen). Une autre possibilité est le paramètre aléatoire. Pour certains problèmes, nous pouvons briser la malédiction de la dimensionnalité en affaiblissant l'assurance; pour d'autres, nous ne pouvons pas. Il existe une importante littérature du CIB sur les résultats dans divers contextes; voir Où en savoir plus ci-dessous. ${\ displaystyle \ epsilon}$${\ displaystyle \ epsilon}$
• Nous pouvons intégrer la connaissance du domaine . Voir un exemple: Finance mathématique ci-dessous.

Un exemple: la finance mathématique

Les intégrales dimensionnelles très élevées sont courantes en finance. Par exemple, le calcul des flux de trésorerie attendus pour une obligation hypothécaire garantie (CMO) nécessite le calcul d'un certain nombre d' intégrales dimensionnelles, à savoir le nombre de mois en années. Rappelez-vous que si l'assurance du pire des cas est requise, le temps est de l'ordre des unités de temps. Même si l'erreur n'est pas petite, disons qu'il s'agit d' unités de temps. Les gens de la finance utilisent depuis longtemps la méthode de Monte Carlo (MC), une instance d'algorithme aléatoire. Puis, en 1994, un groupe de recherche de l'Université de Columbia ( Papageorgiou , Paskov, Traub , Woźniakowski) a découvert que la méthode quasi-Monte Carlo (QMC) utilisant des séquences à faible divergence battait MC d'un à trois ordres de grandeur. Les résultats ont été rapportés à un certain nombre de finances de Wall Street à un scepticisme initial considérable. Les résultats ont été publiés pour la première fois par Paskov et Traub , Faster Valuation of Financial Derivatives , Journal of Portfolio Management 22, 113-120. Aujourd'hui, le QMC est largement utilisé dans le secteur financier pour valoriser les dérivés financiers. ${\ displaystyle 360}$${\ displaystyle 360}$${\ displaystyle 30}$${\ displaystyle \ epsilon ^ {- d}}$${\ displaystyle \ epsilon = 10 ^ {- 2},}$${\ displaystyle 10 ^ {720}}$

Ces résultats sont empiriques; d'où vient la complexité de calcul? QMC n'est pas une panacée pour toutes les intégrales de haute dimension. Quelle est la particularité des dérivés financiers? Voici une explication possible. Les dimensions du CMO représentent les temps futurs mensuels. En raison de la valeur actualisée de la monnaie, les variables représentant les temps futurs sont moins importantes que les variables représentant les heures proches. Ainsi, les intégrales sont non isotropes. Sloan et Woźniakowski ont introduit l'idée très puissante d'espaces pondérés, qui est une formalisation de l'observation ci-dessus. Ils ont pu montrer qu'avec cette connaissance de domaine supplémentaire, les intégrales de haute dimension satisfaisant certaines conditions étaient traitables même dans le pire des cas! En revanche, la méthode de Monte Carlo ne donne qu'une assurance stochastique. Voir Sloan et Woźniakowski Quand les algorithmes quasi-Monte Carlo sont-ils efficaces pour une intégration haute dimension? J. Complexity 14, 1-33, 1998. Pour quelles classes d'intégrales QMC est-il supérieur à MC? Cela continue d'être un problème majeur de recherche. ${\ displaystyle 360}$

Bref historique

Des précurseurs de l'IBC peuvent être trouvés dans les années 1950 par Kiefer, Sard et Nikolskij. En 1959, Traub avait l'intuition principale que l'algorithme optimal et la complexité de calcul pour résoudre un problème continu dépendaient des informations disponibles. Il a appliqué cette idée à la solution d' équations non linéaires , qui a commencé le domaine de la théorie de l'itération optimale. Cette recherche a été publiée dans la monographie 1964 Iterative Methods for the Solution of Equations.

Le cadre général de la complexité basée sur l'information a été formulé par Traub et Woźniakowski en 1980 dans A General Theory of Optimal Algorithms. Pour une liste des monographies les plus récentes et des pointeurs vers la littérature abondante, voir Pour en savoir plus ci-dessous.

Prix

Il existe un certain nombre de prix pour la recherche IBC.

• Prix ​​de la complexité de l'information Ce prix annuel, créé en 1999, se compose de 3 000 $ et d'une plaque. Il est décerné pour des réalisations exceptionnelles dans le domaine de la complexité basée sur l'information. Les destinataires sont listés ci-dessous. L'affiliation est au moment de l'attribution.
  • 1999 Erich Novak, Université de Jena, Allemagne
  • 2000 Sergei Pereverzev, Académie ukrainienne des sciences, Ukraine
  • 2001 GW Wasilkowski, Université du Kentucky, États-Unis
  • 2002 Stefan Heinrich, Université de Kaiserslautern, Allemagne
  • 2003 Arthur G. Werschulz, Fordham University, États-Unis
  • 2004 Peter Mathe, Institut Weierstrass pour l'analyse appliquée et la stochastique, Allemagne
  • 2005 Ian Sloan, professeur de Scientia, Université de New South Wales, Sydney, Australie
  • 2006 Leszek Plaskota, Département de mathématiques, informatique et mécanique, Université de Varsovie, Pologne
  • 2007 Klaus Ritter, Département de mathématiques, TU Darmstadt, Allemagne
  • 2008 Anargyros Papageorgiou, Columbia University, États-Unis
  • 2009 Thomas Mueller-Gronbach, Fakultaet fuer Informatik und Mathematik, Universitaet Passau, Allemagne
  • 2010 Boleslaw Z. Kacewicz, Département de mathématiques, Université des sciences et technologies AGH, Cracovie, Pologne
  • 2011 Aicke Hinrichs, Fakultät für Mathematik und Informatik, FSU Jena, Allemagne
  • 2012 Michael Gnewuch, Département d'informatique, Christian-Albrechts-Universitaet zu Kiel, Allemagne et École de mathématiques et de statistique, Université de New South Wales, Sydney, Australie
  • 2012 (Prix spécial) Krzysztof Sikorski, Département d'informatique, Université de l'Utah
  • Co-lauréats 2013
    • Josef Dick, Université de la Nouvelle-Galles du Sud, Sydney, Australie
    • Friedrich Pillichshammer, Université Johannes Kepler, Linz, Autriche
  • 2014 Frances Kuo, École de mathématiques, Université de New South Wales, Sydney, Australie
  • 2015 Peter Kritzer, Département de mathématiques financières, Université de Linz, Autriche
  • 2016 Fred J.Hickernell, Department of Applied Mathematics, Illinois Institute of Technology, Chicago, États-Unis
  • Co-lauréats 2017
    • Thomas Kühn, Université de Leipzig, Allemagne
    • Winfried Sickel, Université de Jena, Allemagne.
  • 2018 Paweł Przybyłowicz, Université des sciences et technologies AGH de Cracovie, Pologne
  • 2019 Jan Vybíral, Université technique tchèque, Prague, République tchèque
• Prix ​​du jeune chercheur pour la complexité de l'information Ce prix annuel, créé en 2003, se compose de 1 000 $ et d'une plaque. Les destinataires ont été
  • 2003 Frances Kuo, École de mathématiques, Université de New South Wales, Sydney, Australie
  • 2004 Christiane Lemieux, Université de Calgary, Calgary, Alberta, Canada, et Josef Dick, Université de New South Wales, Sydney, Australie
  • 2005 Friedrich Pillichshammer, Institut de mathématiques financières, Université de Linz, Autriche
  • 2006 Jakob Creutzig, TU Darmstadt, Allemagne et Dirk Nuyens, Katholieke Universiteit, Louvain, Belgique
  • 2007 Andreas Neuenkirch, Universität Frankfurt, Allemagne
  • 2008 Jan Vybíral, Université de Jena, Allemagne
  • 2009 Steffen Dereich, TU Berlin, Allemagne
  • 2010 Daniel Rudolf, Université de Jena, Allemagne
  • 2011 Peter Kritzer, Université de Linz, Autriche
  • 2012 Pawel Przybylowicz, AGH University of Science and Technology, Cracovie, Pologne
  • 2013 Christoph Aistleitner, Département d'analyse et de théorie des nombres, Technische Universitat Graz, Autriche
  • 2014 Tino Ullrich, Institut de simulation numérique, Université de Bonn, Allemagne
  • 2015 Mario Ullrich, Institut d'analyse, Université Johannes Kepler Linz, Autriche
  • 2016 Mario Hefter, TU Kaiserslautern, Allemagne
  • Co-lauréats 2017
    • Takashi Goda, Université de Tokyo
    • Larisa Yaroslavtseva, Université de Passau
  • 2018 Arnulf Jentzen, Eidgenössische Technische Hochschule (ETH) Zürich, Suisse
• Prix ​​du meilleur article, Journal of Complexity Ce prix annuel, créé en 1996, se compose de 3 000 $ (4 000 $ depuis 2015) et d'une plaque. Beaucoup de prix, mais pas tous, ont été attribués à des recherches sur le CIB. Les destinataires ont été
  • 1996 Pascal Koiran
  • Co-lauréats 1997
    • B. Bank, M. Giusti, J. Heintz et GM Mbakop
    • R. DeVore et V. Temlyakov
  • Co-lauréats 1998
    • Stefan Heinrich
    • P. Kirrinis
  • 1999 Arthur G. Werschulz
  • 2000 co-lauréats
    • Bernard Mourrain et Victor Y. Pan
    • J. Maurice Rojas
  • 2001 Erich Novak
  • 2002 Peter Hertling
  • Co-lauréats 2003
    • Markus Blaeser
    • Boleslaw Kacewicz
  • 2004 Stefan Heinrich
  • Co-lauréats 2005
    • Yosef Yomdin
    • Josef Dick et Friedrich Pillichshammer
  • 2006 Knut Petras et Klaus Ritter
  • 2007 Co-lauréats
    • Martin Avendano, Teresa Krick et Martin Sombra
    • Istvan Berkes, Robert F. Tichy et feu Walter Philipp
  • 2008 Stefan Heinrich et Bernhard Milla
  • 2009 Frank Aurzada, Steffen Dereich, Michael Scheutzow et Christian Vormoor
  • Co-lauréats 2010
    • Aicke Hinrichs
    • Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich
  • Co-lauréats 2011
    • Thomas Daun
    • Leszek Plaskota, Greg W. Wasilkowski
  • Co-lauréats 2012
    • Dmitriy Bilyk, VN Temlyakov, Rui Yu
    • Lutz Kämmerer, Stefan Kunis, Daniel Potts
  • Co-lauréats 2013
    • Shu Tezuka
    • Joos Heintz, Bart Kuijpers, Andrés Rojas Paredes
  • 2014 Bernd Carl, Aicke Hinrichs, Philipp Rudolph
  • 2015 Thomas Müller-Gronbach, Klaus Ritter, Larisa Yaroslavtseva
  • Co-lauréats 2016
    • David Harvey, Joris van der Hoeven et Grégoire Lecerf
    • Carlos Beltrán, Jordi Marzo et Joaquim Ortega-Cerdà
  • 2017 Martijn Baartse et Klaus Meer
  • Co-lauréats 2018
    • Stefan Heinrich
    • Julian Grote et Christoph Thäle

Les références

• Traub, JF, Méthodes itératives pour la solution des équations, Prentice Hall, 1964. Reédité Chelsea Publishing Company, 1982; Traduction russe MIR, 1985; Réédition American Mathematical Society, 1998
• Traub, JF et Woźniakowski, H., A General Theory of Optimal Algorithms, Academic Press, New York, 1980
• Traub, JF, Woźniakowski, H., et Wasilkowski, GW, Information, Incertainty, Complexity, Addison-Wesley, New York, 1983
• Novak, E., Limites d'erreur déterministes et stochastiques en analyse numérique, Lecture Nots in Mathematics, vol. 1349, Springer-Verlag, New York, 1988
• Traub, JF, Woźniakowski, H., et Wasilkowski, GW (1988). Complexité basée sur l'information . New York: Presse académique. ISBN   978-0126975451 . CS1 maint: noms multiples: liste des auteurs ( lien )
• Werschulz, AG, The Computational Complexity of Differential and Integral Equations: An Information-Based Approach, Oxford University Press, New York, 1991
• Kowalski, M., Sikorski, K., et Stenger, F., Selected Topics in Approximation and Computation, Oxford University Press, Oxford, Royaume-Uni, 1995
• Plaskota, L., Noisy Information and Computational Complexity, Cambridge University Press, Cambridge, Royaume-Uni, 1996
• Traub, JF et Werschulz, AG, Complexity and Information, Oxford University Press, Oxford, Royaume-Uni, 1998
• Ritter, K., Analyse de cas moyen des problèmes numériques, Springer-Verlag, New York, 2000
• Sikorski, K., Solution optimale d'équations non linéaires, Oxford University Press, Oxford, Royaume-Uni, 2001

Des bibliographies détaillées peuvent être trouvées dans les monographies N (1988), TW (1980), TWW (1988) et TW (1998). Le site Web du CIB contient une base de données consultable de quelque 730 articles.

Liens externes

• Journal de complexité
• Complexité et information
• Joseph Traub
• JF Traub, 1985. Une introduction à la complexité basée sur l'information