Complexidade baseada na informação - Information-based complexity

A complexidade baseada em informações ( IBC ) estuda algoritmos ideais e complexidade computacional para os problemas contínuos que surgem em ciências físicas , economia , engenharia e finanças matemáticas . IBC estudou problemas contínuos como integração de caminhos , equações diferenciais parciais , sistemas de equações diferenciais ordinárias , equações não lineares , equações integrais , pontos fixos e integração dimensional muito alta . Todos esses problemas envolvem funções (normalmente multivariadas) de uma variável real ou complexa . Uma vez que nunca se pode obter uma solução de forma fechada para os problemas de interesse, é preciso se contentar com uma solução numérica. Visto que uma função de uma variável real ou complexa não pode ser inserida em um computador digital, a solução de problemas contínuos envolve informações parciais . Para dar uma ilustração simples, na aproximação numérica de uma integral, apenas amostras do integrando em um número finito de pontos estão disponíveis. Na solução numérica de equações diferenciais parciais, as funções que especificam as condições de contorno e os coeficientes do operador diferencial só podem ser amostradas. Além disso, essa informação parcial pode ser cara de se obter. Finalmente, a informação é frequentemente contaminada por ruído.

O objetivo da complexidade baseada em informações é criar uma teoria da complexidade computacional e algoritmos ideais para problemas com informações parciais, contaminadas e com preços, e aplicar os resultados para responder a perguntas em várias disciplinas. Exemplos de tais disciplinas incluem física , economia, finanças matemáticas, visão computacional , teoria de controle , geofísica , imagens médicas , previsão do tempo e previsão do clima e estatística . A teoria é desenvolvida sobre espaços abstratos, normalmente espaços de Hilbert ou Banach , enquanto as aplicações são geralmente para problemas multivariados.

Como as informações são parciais e contaminadas, apenas soluções aproximadas podem ser obtidas. IBC estuda complexidade computacional e algoritmos ideais para soluções aproximadas em vários ambientes. Visto que a configuração do pior caso freqüentemente leva a resultados negativos, como insolvência e intratabilidade, as configurações com garantias mais fracas, como média, probabilística e aleatória também são estudadas. Uma área relativamente nova de pesquisa IBC é a computação quântica contínua .

Visão geral

Ilustramos alguns conceitos importantes com um exemplo muito simples, o cálculo de

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

Para a maioria dos integrandos, não podemos usar o teorema fundamental do cálculo para calcular a integral analiticamente; temos que aproximar numericamente. Calculamos os valores de em n pontos ${\ displaystyle f}$

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

Os n números são as informações parciais sobre o integrando verdadeiro . Combinamos esses n números por um algoritmo combinatório para calcular uma aproximação da integral. Veja a monografia Complexidade e Informações para detalhes. ${\ displaystyle f (x).}$

Como temos apenas informações parciais, podemos usar um argumento do adversário para nos dizer o quão grande n deve ser para calcular uma -aproximação. Por causa desses argumentos baseados em informações, muitas vezes podemos obter limites rígidos sobre a complexidade dos problemas contínuos. Para problemas discretos, como fatoração de inteiros ou o problema do caixeiro-viajante , temos de nos contentar com conjecturas sobre a hierarquia de complexidade. O motivo é que a entrada é um número ou vetor de números e pode, portanto, ser inserida no computador. Portanto, normalmente não há argumento adversário no nível da informação e a complexidade de um problema discreto raramente é conhecida. ${\ displaystyle \ epsilon}$

O problema de integração univariada era apenas ilustrativo. Significativo para muitas aplicações é a integração multivariada. O número de variáveis está na casa das centenas ou milhares. O número de variáveis pode até ser infinito; então falamos de integração de caminhos. A razão pela qual as integrais são importantes em muitas disciplinas é que elas ocorrem quando queremos saber o comportamento esperado de um processo contínuo. Veja, por exemplo, o aplicativo para finanças matemáticas abaixo.

Suponha que queremos calcular uma integral em d dimensões (dimensões e variáveis são usadas de forma intercambiável) e que queremos garantir um erro no máximo para qualquer integrando em alguma classe. A complexidade computacional do problema é conhecido por ser de ordem (Aqui estamos contando o número de avaliações da função e do número de operações aritméticas por isso esta é a complexidade de tempo.) Isso levaria muitos anos para valores ainda modestos da dependência exponencial sobre d é chamada de maldição da dimensionalidade . Dizemos que o problema é intratável. ${\ displaystyle \ epsilon}$ ${\ displaystyle \ epsilon ^ {- d}.}$ ${\ displaystyle d.}$

Declaramos a maldição da dimensionalidade para a integração. Mas a dependência exponencial de d ocorre para quase todos os problemas contínuos que foram investigados. Como podemos tentar vencer a maldição? Existem duas possibilidades:

Podemos enfraquecer a garantia de que o erro deve ser menor que (configuração do pior caso) e nos contentar com uma garantia estocástica. Por exemplo, podemos apenas exigir que o erro esperado seja menor que (configuração de caso médio). Outra possibilidade é a configuração aleatória. Para alguns problemas, podemos quebrar a maldição da dimensionalidade enfraquecendo a segurança; para outros, não podemos. Existe uma vasta literatura de IBC sobre resultados em vários cenários; veja Onde Aprender Mais abaixo. ${\ displaystyle \ epsilon}$ ${\ displaystyle \ epsilon}$
Podemos incorporar conhecimento de domínio . Veja um exemplo: finanças matemáticas abaixo.

Um exemplo: finanças matemáticas

Integrais dimensionais muito altas são comuns em finanças. Por exemplo, o cálculo dos fluxos de caixa esperados para uma obrigação hipotecária colateralizada (CMO) requer o cálculo de um número de integrais dimensionais, sendo o número de meses em anos. Lembre-se de que, se a garantia do pior caso for necessária, o tempo é de unidades de tempo do pedido . Mesmo que o erro não seja pequeno, digamos que sejam unidades de tempo. O pessoal de finanças há muito usa o método Monte Carlo (MC), uma instância de um algoritmo aleatório. Então, em 1994, um grupo de pesquisa da Universidade de Columbia ( Papageorgiou , Paskov, Traub , Woźniakowski) descobriu que o método quase-Monte Carlo (QMC) usando sequências de baixa discrepância superava o MC em uma a três ordens de magnitude. Os resultados foram relatados a uma série de finanças de Wall Street com considerável ceticismo inicial. Os resultados foram publicados pela primeira vez por Paskov e Traub , Faster Valuation of Financial Derivatives , Journal of Portfolio Management 22, 113-120. Hoje, o QMC é amplamente utilizado no setor financeiro para avaliar derivados financeiros. ${\ displaystyle 360}$ ${\ displaystyle 360}$ ${\ displaystyle 30}$ ${\ displaystyle \ epsilon ^ {- d}}$ ${\ displaystyle \ epsilon = 10 ^ {- 2},}$ ${\ displaystyle 10 ^ {720}}$

Esses resultados são empíricos; onde entra a complexidade computacional? QMC não é uma panacéia para todas as integrais de alta dimensão. O que há de especial nos derivativos financeiros? Aqui está uma explicação possível. As dimensões no CMO representam tempos futuros mensais. Devido ao valor descontado do dinheiro, as variáveis que representam os tempos futuros são menos importantes do que as variáveis que representam os tempos próximos. Assim, as integrais são não isotrópicas. Sloan e Woźniakowski introduziram a ideia muito poderosa de espaços ponderados, que é uma formalização da observação acima. Eles foram capazes de mostrar que, com este conhecimento de domínio adicional, integrais de alta dimensionalidade satisfazendo certas condições eram tratáveis mesmo no pior caso! Em contraste, o método de Monte Carlo oferece apenas uma garantia estocástica. Consulte Sloan e Woźniakowski Quando os algoritmos quase Monte Carlo são eficientes para integração dimensional elevada? J. Complexity 14, 1-33, 1998. Para quais classes de integrais o QMC é superior ao MC? Este continua a ser um grande problema de pesquisa. ${\ displaystyle 360}$

Breve história

Os precursores do IBC podem ser encontrados na década de 1950 por Kiefer, Sard e Nikolskij. Em 1959, Traub teve o insight fundamental de que o algoritmo ideal e a complexidade computacional para resolver um problema contínuo dependiam das informações disponíveis. Ele aplicou esse insight à solução de equações não lineares , que deu início à área da teoria da iteração ótima. Esta pesquisa foi publicada na monografia de 1964 Métodos Iterativos para a Solução de Equações.

O cenário geral para a complexidade baseada na informação foi formulado por Traub e Woźniakowski em 1980 em A General Theory of Optimal Algorithms. Para obter uma lista das monografias mais recentes e indicações para a extensa literatura, consulte Para aprender mais abaixo.

Prêmios

Existem vários prêmios para pesquisas IBC.

Prêmio por Realização em Complexidade Baseada na Informação Este prêmio anual, que foi criado em 1999, consiste em $ 3.000 e uma placa. É concedido para realizações excepcionais em complexidade baseada em informações. Os destinatários estão listados abaixo. A afiliação é a partir do momento da premiação.
- 1999 Erich Novak, Universidade de Jena, Alemanha
- 2000 Sergei Pereverzev, Academia Ucraniana de Ciências, Ucrânia
- 2001 GW Wasilkowski, Universidade de Kentucky, EUA
- 2002 Stefan Heinrich, Universidade de Kaiserslautern, Alemanha
- 2003 Arthur G. Werschulz, Fordham University, EUA
- 2004 Peter Mathe, Instituto Weierstrass de Análise Aplicada e Estocástica, Alemanha
- 2005 Ian Sloan, Professor Scientia, University of New South Wales, Sydney, Austrália
- 2006 Leszek Plaskota, Departamento de Matemática, Informática e Mecânica, Universidade de Varsóvia, Polônia
- 2007 Klaus Ritter, Departamento de Matemática, TU Darmstadt, Alemanha
- 2008 Anargyros Papageorgiou, Columbia University, EUA
- 2009 Thomas Mueller-Gronbach, Fakultaet fuer Informatik und Mathematik, Universitaet Passau, Alemanha
- 2010 Boleslaw Z. Kacewicz, Departamento de Matemática, AGH University of Science and Technology, Cracóvia, Polônia
- 2011 Aicke Hinrichs, Fakultät für Mathematik und Informatik, FSU Jena, Alemanha
- 2012 Michael Gnewuch, Departamento de Ciência da Computação, Christian-Albrechts-Universitaet zu Kiel, Alemanha e Escola de Matemática e Estatística, Universidade de New South Wales, Sydney, Austrália
- 2012 (Prêmio especial) Krzysztof Sikorski, Departamento de Ciência da Computação, Universidade de Utah
- Co-vencedores de 2013
  - Josef Dick, University of New South Wales, Sydney, Austrália
  - Friedrich Pillichshammer, Universidade Johannes Kepler, Linz, Áustria
- 2014 Frances Kuo, Escola de Matemática, Universidade de New South Wales, Sydney, Austrália
- 2015 Peter Kritzer, Departamento de Matemática Financeira, Universidade de Linz, Áustria
- 2016 Fred J. Hickernell, Departamento de Matemática Aplicada, Instituto de Tecnologia de Illinois, Chicago, EUA
- Co-vencedores de 2017
  - Thomas Kühn, Universidade de Leipzig, Alemanha
  - Winfried Sickel, Universidade de Jena, Alemanha.
- 2018 Paweł Przybyłowicz, AGH University of Science and Technology em Cracóvia, Polônia
- 2019 Jan Vybíral, Universidade Técnica Tcheca, Praga, República Tcheca
Prêmio Jovem Pesquisador da Complexidade Baseada em Informações Este prêmio anual, criado em 2003, consiste em US $ 1.000 e uma placa. Os destinatários foram
- 2003 Frances Kuo, Escola de Matemática, Universidade de New South Wales, Sydney, Austrália
- 2004 Christiane Lemieux, University of Calgary, Calgary, Alberta, Canadá, e Josef Dick, University of New South Wales, Sydney, Austrália
- 2005 Friedrich Pillichshammer, Instituto de Matemática Financeira, Universidade de Linz, Áustria
- 2006 Jakob Creutzig, TU Darmstadt, Alemanha e Dirk Nuyens, Katholieke Universiteit, Leuven, Bélgica
- 2007 Andreas Neuenkirch, Universität Frankfurt, Alemanha
- 2008 Jan Vybíral, Universidade de Jena, Alemanha
- 2009 Steffen Dereich, TU Berlin, Alemanha
- 2010 Daniel Rudolf, Universidade de Jena, Alemanha
- 2011 Peter Kritzer, Universidade de Linz, Áustria
- 2012 Pawel Przybylowicz, AGH University of Science and Technology, Cracóvia, Polônia
- 2013 Christoph Aistleitner, Departamento de Análise e Teoria dos Números Computacionais, Technische Universitat Graz, Áustria
- 2014 Tino Ullrich, Instituto de Simulação Numérica, Universidade de Bonn, Alemanha
- 2015 Mario Ullrich, Instituto de Análise, Johannes Kepler University Linz, Áustria
- 2016 Mario Hefter, TU Kaiserslautern, Alemanha
- Co-vencedores de 2017
  - Takashi Goda, Universidade de Tóquio
  - Larisa Yaroslavtseva, Universidade de Passau
- 2018 Arnulf Jentzen, Eidgenössische Technische Hochschule (ETH) Zurique, Suíça
Prêmio de Melhor Artigo, Journal of Complexity Este prêmio anual, que foi criado em 1996, consiste em $ 3.000 ($ 4.000 desde 2015) e uma placa. Muitos, mas de forma alguma todos os prêmios foram para pesquisas no IBC. Os destinatários foram
- Pascal Koiran 1996
- Co-vencedores de 1997
  - B. Bank, M. Giusti, J. Heintz e GM Mbakop
  - R. DeVore e V. Temlyakov
- Co-vencedores de 1998
  - Stefan Heinrich
  - P. Kirrinis
- 1999 Arthur G. Werschulz
- 2.000 co-vencedores
  - Bernard Mourrain e Victor Y. Pan
  - J. Maurice Rojas
- Erich Novak de 2001
- 2002 Peter Hertling
- Co-vencedores de 2003
  - Markus Blaeser
  - Boleslaw Kacewicz
- Stefan Heinrich 2004
- Co-vencedores de 2005
  - Yosef Yomdin
  - Josef Dick e Friedrich Pillichshammer
- 2006 Knut Petras e Klaus Ritter
- Co-vencedores de 2007
  - Martin Avendano, Teresa Krick e Martin Sombra
  - Istvan Berkes, Robert F. Tichy e o falecido Walter Philipp
- Stefan Heinrich e Bernhard Milla 2008
- 2009 Frank Aurzada, Steffen Dereich, Michael Scheutzow e Christian Vormoor
- Co-vencedores de 2010
  - Aicke Hinrichs
  - Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich
- Co-vencedores de 2011
  - Thomas Daun
  - Leszek Plaskota, Greg W. Wasilkowski
- Co-vencedores de 2012
  - Dmitriy Bilyk, VN Temlyakov, Rui Yu
  - Lutz Kämmerer, Stefan Kunis, Daniel Potts
- Co-vencedores 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
- Co-vencedores de 2016
  - David Harvey, Joris van der Hoeven e Grégoire Lecerf
  - Carlos Beltrán, Jordi Marzo e Joaquim Ortega-Cerdà
- 2017 Martijn Baartse e Klaus Meer
- Co-vencedores de 2018
  - Stefan Heinrich
  - Julian Grote e Christoph Thäle

Referências

Traub, JF, Métodos Iterativos para a Solução de Equações, Prentice Hall, 1964. Reeditado Chelsea Publishing Company, 1982; Tradução russa MIR, 1985; Reeditada American Mathematical Society, 1998
Traub, JF e Woźniakowski, H., A General Theory of Optimal Algorithms, Academic Press, New York, 1980
Traub, JF, Woźniakowski, H., e Wasilkowski, GW, Information, Uncertainty, Complexity, Addison-Wesley, New York, 1983
Novak, E., Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Nots in Mathematics, vol. 1349, Springer-Verlag, Nova York, 1988
Traub, JF, Woźniakowski, H. e Wasilkowski, GW (1988). Complexidade baseada em informações . Nova York: Academic Press. ISBN 978-0126975451 . CS1 maint: vários nomes: lista de autores ( link )
Werschulz, AG, The Computational Complexity of Differential and Integral Equations: An Information-Based Approach, Oxford University Press, New York, 1991
Kowalski, M., Sikorski, K., e Stenger, F., Tópicos Selecionados em Aproximação e Computação, Oxford University Press, Oxford, Reino Unido, 1995
Plaskota, L., Noisy Information and Computational Complexity, Cambridge University Press, Cambridge, UK, 1996
Traub, JF e Werschulz, AG, Complexity and Information, Oxford University Press, Oxford, Reino Unido, 1998
Ritter, K., Average-Case Analysis of Numerical Problems, Springer-Verlag, Nova York, 2000
Sikorski, K., Optimal Solution of Nonlinear Equations, Oxford University Press, Oxford, UK, 2001

Bibliografias extensas podem ser encontradas nas monografias N (1988), TW (1980), TWW (1988) e TW (1998). O site do IBC possui um banco de dados pesquisável de cerca de 730 itens.

Languages

In other projects