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 . IBC ha estudiado problemas continuos como integración de trayectorias , ecuaciones diferenciales parciales , sistemas de ecuaciones diferenciales ordinarias , ecuaciones no lineales , ecuaciones integrales , puntos fijos e integración de muy alta dimensión.. Todos estos problemas involucran funciones (típicamente multivariadas) de una variable real o compleja . Dado que nunca se puede obtener una solución de forma cerrada a los problemas de interés, uno tiene que conformarse con una solución numérica. Dado que una función de una variable real o compleja no se puede ingresar en una computadora digital, la solución de problemas continuos implica información parcial . Para dar una ilustración simple, en la aproximación numérica de una integral, solo están disponibles muestras del integrando en un número finito de puntos. En la solución numérica de ecuaciones diferenciales parciales, las funciones que especifican las condiciones de contorno y los coeficientes del operador diferencial solo se pueden muestrear. Además, esta información parcial puede resultar costosa de obtener. Por último, 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 diversas 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 suelen ser para problemas multivariados.
Dado que la información es parcial y está contaminada, solo se pueden obtener soluciones aproximadas. IBC estudia la complejidad computacional y los algoritmos óptimos para soluciones aproximadas en varios entornos. Dado que el escenario del peor de los casos a menudo conduce a resultados negativos, como la insolubilidad y la intratabilidad, también se estudian los entornos con garantías más débiles, como promedio, probabilístico y aleatorizado. Un área bastante nueva de la investigación de IBC es la computación cuántica continua .
Descripción general
Ilustramos algunos conceptos importantes con un ejemplo muy simple, el cálculo de
Para la mayoría de los integrandos, no podemos usar el teorema fundamental del cálculo para calcular la integral analíticamente; tenemos que aproximarlo numéricamente. Calculamos los valores deen n puntos
Los n números son la información parcial sobre el verdadero integrandoCombinamos 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.
Debido a que solo tenemos información parcial, podemos usar un argumento adversario para decirnos qué tan grande debe ser n para calcular una-aproximación. Debido a estos argumentos basados en la información, a menudo podemos obtener límites estrictos sobre la complejidad de los problemas continuos. Para 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 ingresar en la computadora. Por lo tanto, no suele haber un argumento contradictorio a nivel de información y rara vez se conoce la complejidad de un problema discreto.
El problema de la integración univariante fue solo para ilustración. Para muchas aplicaciones, es importante la integración multivariante. El número de variables es de cientos o miles. El número de variables puede incluso ser infinito; luego hablamos de integración de caminos. La razón por la que las integrales son importantes en muchas disciplinas es que ocurren cuando queremos conocer el comportamiento esperado de un proceso continuo. Consulte, por ejemplo, la aplicación a las finanzas matemáticas 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áximopara cualquier integrando en alguna clase. Se sabe que la complejidad computacional del problema es de orden (Aquí estamos contando 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 insoluble.
Dijimos la maldición de la dimensionalidad para la integración. Pero la dependencia exponencial de d ocurre para 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 (configuración del peor de los casos) y conformarse con una garantía estocástica. Por ejemplo, es posible que solo solicitemos que el error esperado sea menor que(configuración de caso promedio). Otra posibilidad es la configuración aleatoria. Para algunos problemas, podemos romper la maldición de la dimensionalidad debilitando la seguridad; para otros, no podemos. Existe una amplia bibliografía sobre IBC sobre los resultados en varios entornos; consulte Dónde aprender más a continuación.
- Podemos incorporar conocimientos de dominio . Vea un ejemplo: Finanzas matemáticas a continuación.
Un ejemplo: finanzas matemáticas
Las integrales de muy alta dimensión 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, la siendo el número de meses en años. Recuerde que si se requiere una garantía en el peor de los casos, el tiempo es el indicado.unidades de tiempo. Incluso si el error no es pequeño, digamos esto es unidades de tiempo. Las personas en finanzas han estado usando durante mucho tiempo el método de Monte Carlo (MC), una instancia 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 utiliza secuencias de baja discrepancia vence a 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. En la actualidad, QMC se utiliza ampliamente en el sector financiero para valorar derivados financieros.
Estos resultados son empíricos; ¿Dónde entra la complejidad computacional? QMC no es una panacea para todas las integrales de alta dimensión. ¿Qué tienen de especial los derivados financieros? Aquí hay una posible explicación. Lalas dimensiones en el CMO representan tiempos futuros mensuales. Debido al valor descontado del dinero, las variables que representan tiempos para en el futuro son menos importantes que las variables que representan tiempos cercanos. Por tanto, las integrales no son isotrópicas. Sloan y Woźniakowski introdujeron la idea muy poderosa de espacios ponderados, que es una formalización de la observación anterior. Pudieron demostrar que con este conocimiento de dominio adicional, las integrales de alta dimensión que satisfacían ciertas condiciones eran tratables incluso en el peor de los casos. Por el contrario, el método de Monte Carlo ofrece sólo una garantía estocástica. Consulte Sloan y Woźniakowski. ¿ Cuándo son eficientes los algoritmos cuasi-Monte Carlo para la integración de alta dimensión? J. Complexity 14, 1-33, 1998. ¿Para qué clases de integrales es QMC superior a MC? Este sigue siendo un problema de investigación importante.
Breve historia
Los precursores de 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 resolver un problema continuo dependían de la información disponible. Aplicó esta idea a la solución de ecuaciones no lineales , lo que inició el área de la teoría de la iteración óptima. Esta investigación fue publicada en la monografía de 1964 Métodos iterativos para la solución de ecuaciones.
El escenario general para la complejidad basada en la información fue formulado por Traub y Woźniakowski en 1980 en A General Theory of Optimal Algorithms. Para obtener una lista de monografías más recientes y sugerencias para la extensa literatura, consulte Para aprender más a continuación.
Premios
Hay una serie de premios para la investigación de IBC.
- Premio por logros en complejidad basada en la información Este premio anual, creado en 1999, consta de $ 3000 y una placa. Se otorga por logros sobresalientes en complejidad basada en información. Los destinatarios se enumeran a continuación. La afiliación es a partir del momento de la adjudicación.
- 1999 Erich Novak, Universidad de Jena, Alemania
- 2000 Sergei Pereverzev, Academia de Ciencias de Ucrania, Ucrania
- 2001 GW Wasilkowski, Universidad de Kentucky, EE. UU.
- 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, Sydney, 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 Escuela de Matemáticas y Estadística, Universidad de Nueva Gales del Sur, Sydney, Australia
- 2012 (premio especial) Krzysztof Sikorski, Departamento de Ciencias de la Computación, Universidad de Utah
- Coganadores de 2013
- Josef Dick, Universidad de Nueva Gales del Sur, Sydney, Australia
- Friedrich Pillichshammer, Universidad Johannes Kepler, Linz, Austria
- 2014 Frances Kuo, Escuela de Matemáticas, Universidad de Nueva Gales del Sur, Sydney, Australia
- 2015 Peter Kritzer, Departamento de Matemáticas Financieras, Universidad de Linz, Austria
- 2016 Fred J. Hickernell, Departamento de Matemáticas Aplicadas, Instituto de Tecnología de Illinois, Chicago, EE. UU.
- Coganadores de 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 Joven Investigador de Complejidad Basada en la Información Este premio anual, creado en 2003, consiste en $ 1000 y una placa. Los destinatarios han sido
- 2003 Frances Kuo, Escuela de Matemáticas, Universidad de Nueva Gales del Sur, Sydney, 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, Universität 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 de Números Computacionales, 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
- Coganadores de 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 ($ 4000 desde 2015) y una placa. Muchos, pero de ninguna manera todos los premios han sido para la investigación en IBC. Los destinatarios han sido
- 1996 Pascal Koiran
- 1997 Coganadores
- B. Bank, M. Giusti, J. Heintz y GM Mbakop
- R. DeVore y V. Temlyakov
- 1998 Co-ganadores
- Stefan Heinrich
- P. Kirrinis
- 1999 Arthur G. Werschulz
- 2000 Co-ganadores
- Bernard Mourrain y Victor Y. Pan
- J. Maurice Rojas
- 2001 Erich Novak
- 2002 Peter Hertling
- 2003 Co-ganadores
- Markus Blaeser
- Boleslaw Kacewicz
- 2004 Stefan Heinrich
- 2005 Co-ganadores
- Yosef Yomdin
- Josef Dick y Friedrich Pillichshammer
- 2006 Knut Petras y Klaus Ritter
- 2007 Coganadores
- Martin Avendano, Teresa Krick y Martin 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
- Coganadores de 2010
- Aicke Hinrichs
- Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich
- Co-ganadores 2011
- Thomas Daun
- Leszek Plaskota, Greg W. Wasilkowski
- Coganadores de 2012
- Dmitriy Bilyk, VN Temlyakov, Rui Yu
- Lutz Kämmerer, Stefan Kunis y Daniel Potts
- Coganadores de 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
- Coganadores de 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
Referencias
- Traub, JF, Métodos iterativos para la solución de ecuaciones, Prentice Hall, 1964. Publicado nuevamente en Chelsea Publishing Company, 1982; Traducción rusa MIR, 1985; Sociedad matemática estadounidense reeditada, 1998
- Traub, JF y Woźniakowski, H., A General Theory of Optimal Algorithms, Academic Press, Nueva York, 1980
- Traub, JF, Woźniakowski, H. y Wasilkowski, GW, Information, Uncertainty, Complexity, Addison-Wesley, Nueva York, 1983
- Novak, E., Límites de error deterministas y estocásticos en el análisis numérico, Lecture Nots 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.CS1 maint: varios nombres: lista de autores ( enlace )
- Werschulz, AG, La complejidad computacional de las 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, Complexity and Information, 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 amplias bibliografías en las monografías N (1988), TW (1980), TWW (1988) y TW (1998). El sitio web de IBC tiene una base de datos de búsqueda de unos 730 elementos.