Resolvendo numericamente um sistema difícil de equações

10

Eu tenho um sistema de equações não lineares que quero resolver numericamente:n

f = ( f 1 , , f n )

f(x)=uma
f=(f1 1,,fn)x=(x1 1,,xn)

Este sistema possui várias características que dificultam o manuseio. Estou procurando idéias sobre como lidar com o sistema de forma mais eficaz.

Por que o sistema é difícil?

  • As funções são semelhantes a esta (mas é claro em várias dimensões):

    Gráficos do Mathematica

    Eles têm planaltos planos separados por uma região de mudança suave. Em 2D, você pode imaginar algo assim para um :fEu

    Gráficos do Mathematica

    Geralmente, cada possui dois platôs separados por mudança suave em torno de um hiperplano dimensional. n - 1fEun-1 1

    Funções como essa são difíceis de lidar com métodos do tipo Newton, porque a derivada é efetivamente zero nos platôs. Em várias dimensões, não consigo encontrar facilmente uma região onde nenhum dosfEu n=1 tenha um platô - se pudesse, isso resolveria o problema. O método de bissecção funciona bem para , mas não generaliza bem para várias dimensões.n=1 1

  • As funções são muito lentas para calcular. Estou procurando um método que possa obter uma aproximação razoável da raiz no menor número possível de iterações.

  • As funções são calculadas com o método Monte Carlo. Isso significa que, cada vez que são calculados, recebo um valor aleatório ligeiramente diferente. Derivativos são difíceis de estimar. Quando estivermos perto o suficiente da raiz, o ruído começará a dominar, e é necessário usar a média para aumentar a precisão. Idealmente, deve ser possível generalizar o método para uma versão equivalente de aproximação estocástica (por exemplo, Newton → Robbins-Monro).

  • O sistema é de alta dimensão. pode ser tão grande quanto 10-20. Quando , um método eficaz seria, provavelmente, ser o seguinte: tentar seguir os contornos definidos por e e ver onde eles se intersectam. Não está claro como isso se generalizaria em altas dimensões.n = 2 f 1 ( x 1 , x 2 ) = 0 f 2 ( x 1 , x 2 ) = 0nn=2f1 1(x1 1,x2)=0 0f2(x1 1,x2)=0 0

O que mais eu sei sobre o sistema?

  • Existe precisamente uma raiz (dos resultados teóricos).

  • Eu sei o valor de nos platôs (digamos que seja 0 e 1 para qualquer ). ifEuEu

  • fEu tem um relacionamento especial com :  muda monotonicamente de 1 para 0, conforme passa de para . Isso vale para qualquer valor fixo do outro .xEufEu(,xEu,)xEu-xjEu

Szabolcs
fonte
Você conhece os limites inferior e superior de todas as variáveis, dentro das quais a solução deve estar? Quanto mais apertados esses limites, melhor. Você pode dar um exemplo determinístico, na dimensão que você desejar, que ilustra seus platôs e dificuldades, mas não requer simulação de Monte Carlo e não possui erros aleatórios nas funções (pontos de bônus se derivadas puderem ser computadas)? O objetivo de um exemplo determinístico é entender as dificuldades do problema, sem dizer que a avaliação de Monte Carlo não será usada na solução final do seu problema real.
Mark L. Stone
@ Limites MarkL.Stone: Eu não os conheço. Mas eu posso adivinhar. As suposições teriam que ser bem amplas para ter certeza de que estão corretas. Exemplo: vou apresentar um exemplo e editarei a pergunta amanhã. Não tenho uma imagem muito mais clara sobre a verdadeira forma de do que a que descrevi aqui; portanto, meu primeiro exemplo pode não ser verdadeiramente representativo do problema real. Mas reunirei algo feito das funções Fermi (sigmóides) e tentarei fazer com que ele tenha tantas dificuldades do problema real quanto possível. f
Szabolcs
Estou ansioso para vê-lo,
Mark L. Stone

Respostas:

1

Como existe uma única raiz e não há restrições, você pode ter sorte em colocá-la como um problema de otimização: minimize a soma (ao longo de cada dimensão) dos quadrados da sua função original.

Os métodos de otimização clássica provavelmente falharão, mas métodos heurísticos, como algoritmos genéticos ou CME-ES (adaptação covariável da matriz etc - estratégia evolutiva), podem funcionar.

MattKelly
fonte
Essa é realmente a abordagem a seguir. Eu examinaria particularmente o algoritmo SPSA, desenvolvido especificamente para o seu propósito e bastante robusto.
Wolfgang Bangerth
2
O OP menciona que a função é muito cara de avaliar (aplicando a simulação de Monte Carlo para uma avaliação de função). Isso não representa um problema muito grande para algoritmos genéticos e outros algoritmos evolutivos? Eles são "trivialmente paralelos" (e geralmente o MC também), de modo que uma computação paralela maciça poderia ser possível, mas eles são o melhor caminho a percorrer aqui?
GertVdE
@WolfgangBangerth Obrigado, como você diz, parece a solução certa. Vou olhar para a SPSA.
Szabolcs
11
Em relação às avaliações de funções caras: É verdade que algoritmos genéticos e métodos heurísticos relacionados tendem a exigir um número maior de avaliações de funções do que os métodos tradicionais. O benefício é que os métodos heurísticos geralmente podem resolver problemas que 1) exigiriam um método específico do problema ou 2) falhariam devido a problemas numéricos. Para este exemplo, é provável que os métodos tradicionais tenham problemas devido à natureza estocástica da função objetivo e aos pequenos gradientes ao longo de algumas dimensões. O SPSA parece um ótimo método candidato para esse problema.
precisa saber é o seguinte