Complejidad basada en la información

La complejidad basada en la información ( IBC ) estudia los algoritmos óptimos y la complejidad computacional para los problemas continuos que surgen en las ciencias físicas , la economía , la ingeniería y las finanzas matemáticas . La IBC ha estudiado problemas continuos como la integración de trayectorias , las ecuaciones diferenciales parciales , los sistemas de ecuaciones diferenciales ordinarias , las ecuaciones no lineales , las ecuaciones integrales , los puntos fijos y la integración de muy alta dimensión . Todos estos problemas involucran funciones (normalmente multivariadas) de una variable real o compleja . Como nunca se puede obtener una solución de forma cerrada para los problemas de interés, hay que conformarse con una solución numérica. Como una función de una variable real o compleja no se puede introducir en una computadora digital, la solución de problemas continuos involucra información parcial . Para dar una ilustración sencilla, en la aproximación numérica de una integral, solo se dispone de muestras del integrando en un número finito de puntos. En la solución numérica de ecuaciones diferenciales parciales, solo se pueden muestrear las funciones que especifican las condiciones de contorno y los coeficientes del operador diferencial. Además, esta información parcial puede ser costosa de obtener. Finalmente, la información suele estar contaminada por ruido.

El objetivo de la complejidad basada en la información es crear una teoría de la complejidad computacional y algoritmos óptimos para problemas con información parcial, contaminada y con precio, y aplicar los resultados para responder preguntas en varias disciplinas. Ejemplos de tales disciplinas incluyen física , economía, finanzas matemáticas, visión por computadora , teoría de control , geofísica , imágenes médicas , pronóstico del tiempo y predicción del clima , y ​​estadística . La teoría se desarrolla sobre espacios abstractos, típicamente espacios de Hilbert o Banach , mientras que las aplicaciones son generalmente para problemas multivariados.

Como la información es parcial y está contaminada, solo se pueden obtener soluciones aproximadas. El IBC estudia la complejidad computacional y los algoritmos óptimos para soluciones aproximadas en diversos entornos. Dado que el peor de los casos suele conducir a resultados negativos, como la imposibilidad de solución y la intratabilidad, también se estudian entornos con garantías más débiles, como el promedio, el probabilístico y el aleatorio. Un área bastante nueva de investigación del IBC es la computación cuántica continua .

Ilustramos algunos conceptos importantes con un ejemplo muy simple, el cálculo de

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

Para la mayoría de los integrandos no podemos utilizar el teorema fundamental del cálculo para calcular la integral analíticamente; tenemos que aproximarla numéricamente. Calculamos los valores de en n puntos ${\estilo de visualización f}$

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

Los n números son la información parcial sobre el integrando verdadero. Combinamos estos n números mediante un algoritmo combinatorio para calcular una aproximación a la integral. Consulte la monografía Complejidad e información para obtener más detalles. ${\estilo de visualización f(x).}$

Como sólo disponemos de información parcial, podemos utilizar un argumento adversario que nos diga qué tan grande debe ser n para calcular una aproximación. Gracias a estos argumentos basados ​​en la información, a menudo podemos obtener límites estrictos sobre la complejidad de los problemas continuos. En el caso de problemas discretos, como la factorización de números enteros o el problema del viajante, tenemos que conformarnos con conjeturas sobre la jerarquía de complejidad. La razón es que la entrada es un número o un vector de números y, por lo tanto, se puede introducir en la computadora. Por lo tanto, normalmente no hay argumento adversario a nivel de información y rara vez se conoce la complejidad de un problema discreto. ${\displaystyle \épsilon}$

El problema de integración univariante se presentó sólo a modo de ejemplo. La integración multivariante es significativa para muchas aplicaciones. El número de variables se encuentra en cientos o miles. El número de variables puede incluso ser infinito; en ese caso, hablamos de integración de trayectorias. La razón por la que las integrales son importantes en muchas disciplinas es que se dan cuando queremos conocer el comportamiento esperado de un proceso continuo. Véase, por ejemplo, la aplicación a las finanzas matemáticas que se muestra a continuación.

Supongamos que queremos calcular una integral en d dimensiones (las dimensiones y las variables se usan indistintamente) y que queremos garantizar un error como máximo para cualquier integrando en alguna clase. Se sabe que la complejidad computacional del problema es del orden de (aquí contamos el número de evaluaciones de funciones y el número de operaciones aritméticas, por lo que esta es la complejidad temporal). Esto llevaría muchos años incluso para valores modestos de La dependencia exponencial de d se llama la maldición de la dimensionalidad . Decimos que el problema es intratable. ${\displaystyle \épsilon}$${\displaystyle \epsilon ^{-d}.}$${\estilo de visualización d.}$

Hemos planteado la maldición de la dimensionalidad para la integración, pero la dependencia exponencial de d se da en casi todos los problemas continuos que se han investigado. ¿Cómo podemos intentar vencer la maldición? Hay dos posibilidades:

• Podemos debilitar la garantía de que el error debe ser menor que (establecimiento del peor caso) y conformarnos con una garantía estocástica. Por ejemplo, podríamos exigir únicamente que el error esperado sea menor que (establecimiento del caso promedio). Otra posibilidad es el entorno aleatorio. Para algunos problemas podemos romper la maldición de la dimensionalidad debilitando la garantía; para otros, no podemos. Existe una gran cantidad de literatura de IBC sobre resultados en varios entornos; consulte Dónde obtener más información a continuación.${\displaystyle \épsilon}$${\displaystyle \épsilon}$
• Podemos incorporar conocimientos del área . Vea un ejemplo: Finanzas matemáticas a continuación.

Las integrales de dimensiones muy altas son comunes en finanzas. Por ejemplo, calcular los flujos de efectivo esperados para una obligación hipotecaria garantizada (CMO) requiere el cálculo de una serie de integrales dimensionales, siendo la cantidad de meses en años. Recordemos que si se requiere una garantía del peor caso, el tiempo es del orden de unidades de tiempo. Incluso si el error no es pequeño, digamos que es de unidades de tiempo. Las personas en finanzas han estado usando durante mucho tiempo el método de Monte Carlo (MC), un ejemplo de un algoritmo aleatorio. Luego, en 1994, un grupo de investigación de la Universidad de Columbia (Papageorgiou, Paskov, Traub, Woźniakowski) descubrió que el método cuasi-Monte Carlo (QMC) que usa secuencias de baja discrepancia superaba al MC en uno a tres órdenes de magnitud. Los resultados se informaron a una serie de finanzas de Wall Street con un escepticismo inicial considerable. Los resultados fueron publicados por primera vez por Paskov y Traub , Faster Valuation of Financial Derivatives , Journal of Portfolio Management 22, 113-120. Hoy en día, el QMC se utiliza ampliamente en el sector financiero para valorar derivados financieros. ${\estilo de visualización 360}$${\estilo de visualización 360}$${\estilo de visualización 30}$${\displaystyle \epsilon ^{-d}}$${\displaystyle \epsilon =10^{-2},}$$Estilo de visualización 10^{720}}$

Estos resultados son empíricos; ¿dónde entra en juego la complejidad computacional? QMC no es una panacea para todas las integrales de alta dimensión. ¿Qué tienen de especial los derivados financieros? He aquí una posible explicación. Las dimensiones en el CMO representan tiempos futuros mensuales. Debido al valor descontado del dinero, las variables que representan tiempos para el futuro son menos importantes que las variables que representan tiempos cercanos. Por lo tanto, las integrales no son isotrópicas. Sloan y Woźniakowski introdujeron la idea muy poderosa de los espacios ponderados, que es una formalización de la observación anterior. Pudieron demostrar que con este conocimiento adicional del dominio, las integrales de alta dimensión que satisfacen ciertas condiciones eran manejables incluso en el peor de los casos. En contraste, el método de Monte Carlo solo brinda una garantía estocástica. Consulte Sloan y Woźniakowski When are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integration? J. Complexity 14, 1-33, 1998. ¿Para qué clases de integrales es QMC superior a MC? Este sigue siendo un importante problema de investigación. ${\estilo de visualización 360}$

Los precursores del IBC se pueden encontrar en la década de 1950 por Kiefer, Sard y Nikolskij. En 1959, Traub tuvo la idea clave de que el algoritmo óptimo y la complejidad computacional de la solución de un problema continuo dependían de la información disponible. Aplicó esta idea a la solución de ecuaciones no lineales , lo que dio inicio al área de la teoría de iteración óptima. Esta investigación se publicó en la monografía de 1964 Métodos iterativos para la solución de ecuaciones.

La configuración general de la complejidad basada en la información fue formulada por Traub y Woźniakowski en 1980 en Una teoría general de algoritmos óptimos. Para obtener una lista de monografías más recientes y referencias a la extensa literatura, consulte Más información a continuación.

Hay una serie de premios para la investigación del IBC.

• Premio por logros en complejidad basada en la información Este premio anual, creado en 1999, consta de 3000 dólares y una placa. Se otorga por logros destacados en complejidad basada en la información. Los ganadores se enumeran a continuación. La afiliación es la vigente en el momento del premio.
  • 1999 Erich Novak, Universidad de Jena, Alemania
  • 2000 Sergei Pereverzev, Academia de Ciencias de Ucrania, Ucrania
  • 2001 GW Wasilkowski, Universidad de Kentucky, Estados Unidos
  • 2002 Stefan Heinrich, Universidad de Kaiserslautern, Alemania
  • 2003 Arthur G. Werschulz, Universidad de Fordham, EE.UU.
  • 2004 Peter Mathe, Instituto Weierstrass de Análisis Aplicado y Estocástica, Alemania
  • 2005 Ian Sloan, profesor de Scientia, Universidad de Nueva Gales del Sur, Sídney, Australia
  • 2006 Leszek Plaskota, Departamento de Matemáticas, Informática y Mecánica, Universidad de Varsovia, Polonia
  • 2007 Klaus Ritter, Departamento de Matemáticas, TU Darmstadt, Alemania
  • 2008 Anargyros Papageorgiou, Universidad de Columbia, EE.UU.
  • 2009 Thomas Mueller-Gronbach, Fakultaet fuer Informatik und Mathematik, Universitaet Passau, Alemania
  • 2010 Boleslaw Z. Kacewicz, Departamento de Matemáticas, Universidad de Ciencia y Tecnología AGH, Cracovia, Polonia
  • 2011 Aicke Hinrichs, Fakultät für Mathematik und Informatik, FSU Jena, Alemania
  • 2012 Michael Gnewuch, Departamento de Ciencias de la Computación, Christian-Albrechts-Universitaet zu Kiel, Alemania y Facultad de Matemáticas y Estadística, Universidad de Nueva Gales del Sur, Sídney, Australia
  • 2012 (Premio especial) Krzysztof Sikorski, Departamento de Ciencias de la Computación, Universidad de Utah
  • Co-ganadores 2013
    • Josef Dick, Universidad de Nueva Gales del Sur, Sídney, Australia
    • Friedrich Pillichshammer, Universidad Johannes Kepler, Linz, Austria
  • 2014 Frances Kuo, Facultad de Matemáticas, Universidad de Nueva Gales del Sur, Sídney, Australia
  • 2015 Peter Kritzer, Departamento de Matemáticas Financieras, Universidad de Linz, Austria
  • 2016 Fred J. Hickernell, Departamento de Matemáticas Aplicadas, Instituto Tecnológico de Illinois, Chicago, EE. UU.
  • Co-ganadores 2017
    • Thomas Kühn, Universidad de Leipzig, Alemania
    • Winfried Sickel, Universidad de Jena, Alemania.
  • 2018 Paweł Przybyłowicz, Universidad de Ciencia y Tecnología AGH en Cracovia, Polonia
  • 2019 Jan Vybíral, Universidad Técnica Checa, Praga, República Checa
• Premio a jóvenes investigadores en complejidad basada en la información Este premio anual, creado en 2003, consta de 1000 dólares y una placa. Los ganadores han sido
  • 2003 Frances Kuo, Facultad de Matemáticas, Universidad de Nueva Gales del Sur, Sídney, Australia
  • 2004 Christiane Lemieux, Universidad de Calgary, Calgary, Alberta, Canadá, y Josef Dick, Universidad de Nueva Gales del Sur, Sydney, Australia
  • 2005 Friedrich Pillichshammer, Instituto de Matemáticas Financieras, Universidad de Linz, Austria
  • 2006 Jakob Creutzig, TU Darmstadt, Alemania y Dirk Nuyens, Katholieke Universiteit, Lovaina, Bélgica
  • 2007 Andreas Neuenkirch, Universidad de Frankfurt, Alemania
  • 2008 Jan Vybíral, Universidad de Jena, Alemania
  • 2009 Steffen Dereich, TU Berlín, Alemania
  • 2010 Daniel Rudolf, Universidad de Jena, Alemania
  • 2011 Peter Kritzer, Universidad de Linz, Austria
  • 2012 Pawel Przybylowicz, Universidad de Ciencia y Tecnología AGH, Cracovia, Polonia
  • 2013 Christoph Aistleitner, Departamento de Análisis y Teoría Computacional de Números, Technische Universitat Graz, Austria
  • 2014 Tino Ullrich, Instituto de Simulación Numérica, Universidad de Bonn, Alemania
  • 2015 Mario Ullrich, Instituto de Análisis, Universidad Johannes Kepler de Linz, Austria
  • 2016 Mario Hefter, TU Kaiserslautern, Alemania
  • Co-ganadores 2017
    • Takashi Goda, Universidad de Tokio
    • Larisa Yaroslavtseva, Universidad de Passau
  • 2018 Arnulf Jentzen, Eidgenössische Technische Hochschule (ETH) Zúrich, Suiza
• Premio al mejor artículo, Journal of Complexity Este premio anual, creado en 1996, consta de 3000 dólares (4000 dólares desde 2015) y una placa. Muchos de los premios, aunque no todos, han sido para investigaciones en IBC. Los ganadores han sido
  • 1996 Pascal Koiran
  • Co-ganadores de 1997
    • B. Bank, M. Giusti, J. Heintz y GM Mbakop
    • R. DeVore y V. Temlyakov
  • Co-ganadores de 1998
    • Stefan Heinrich
    • P. Kirrinis
  • 1999 Arthur G. Werschulz
  • Co-ganadores del año 2000
    • Bernard Mourrain y Victor Y. Pan
    • J. Maurice Rojas
  • 2001 Erich Novak
  • 2002 Peter Hertling
  • Co-ganadores 2003
    • Markus Blaeser
    • Boleslaw Kacewicz
  • 2004 Stefan Heinrich
  • Co-ganadores 2005
    • Yosef Yomdin
    • Josef Dick y Friedrich Pillichshammer
  • 2006 Knut Petras y Klaus Ritter
  • Co-ganadores 2007
    • Martín Avendaño, Teresa Krick y Martín Sombra
    • Istvan Berkes, Robert F. Tichy y el difunto Walter Philipp
  • 2008 Stefan Heinrich y Bernhard Milla
  • 2009 Frank Aurzada, Steffen Dereich, Michael Scheutzow y Christian Vormoor
  • Co-ganadores 2010
    • Aicke Hinrichs
    • Simón Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich
  • Co-ganadores 2011
    • Thomas Daun
    • Leszek Plaskota, Greg W. Wasilkowski
  • Co-ganadores 2012
    • Dmitriy Bilyk, VN Temlyakov, Rui Yu
    • Lutz Kämmerer, Stefan Kunis, Daniel Potts
  • Co-ganadores 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-ganadores 2016
    • David Harvey, Joris van der Hoeven y Grégoire Lecerf
    • Carlos Beltrán, Jordi Marzo y Joaquim Ortega-Cerdà
  • 2017 Martijn Baartse y Klaus Meer
  • Co-ganadores 2018
    • Stefan Heinrich
    • Julian Grote y Christoph Thäle
  • Ganadores 2019
    • Aicke Hinrichs, Joscha Prochno  [de] , Mario Ullrich

• Traub, JF, Métodos iterativos para la solución de ecuaciones, Prentice Hall, 1964. Reeditado por Chelsea Publishing Company, 1982; traducción al ruso por MIR, 1985; reeditado por American Mathematical Society, 1998
• Traub, JF, y Woźniakowski, H., Una teoría general de algoritmos óptimos, Academic Press, Nueva York, 1980
• Traub, JF, Woźniakowski, H. y Wasilkowski, GW, Información, incertidumbre, complejidad, Addison-Wesley, Nueva York, 1983
• Novak, E., Límites de error deterministas y estocásticos en el análisis numérico, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Nueva York, 1988
• Traub, JF, Woźniakowski, H. y Wasilkowski, GW (1988). Complejidad basada en la información . Nueva York: Academic Press. ISBN 978-0126975451.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
• Werschulz, AG, La complejidad computacional de ecuaciones diferenciales e integrales: un enfoque basado en la información, Oxford University Press, Nueva York, 1991
• Kowalski, M., Sikorski, K. y Stenger, F., Temas seleccionados en aproximación y computación, Oxford University Press, Oxford, Reino Unido, 1995
• Plaskota, L., Información ruidosa y complejidad computacional, Cambridge University Press, Cambridge, Reino Unido, 1996
• Traub, JF, y Werschulz, AG, Complejidad e información, Oxford University Press, Oxford, Reino Unido, 1998
• Ritter, K., Análisis de casos promedio de problemas numéricos, Springer-Verlag, Nueva York, 2000
• Sikorski, K., Solución óptima de ecuaciones no lineales, Oxford University Press, Oxford, Reino Unido, 2001

Se pueden encontrar bibliografías extensas en las monografías N (1988), TW (1980), TWW (1988) y TW (1998). El sitio web del IBC tiene una base de datos con capacidad de búsqueda de unos 730 artículos.

• Revista de complejidad
• Complejidad e información
• José Traub
• JF Traub, 1985. Introducción a la complejidad basada en la información