Rozwiązywanie trudnego układu równań numerycznie

Mam układ równań nieliniowych, które chcę rozwiązać numerycznie: $n$

f (x) = a

$\mathbf{f}(\mathbf{x})=\mathbf{a}$

f = (f_{1}, \dots, f_{n}) x = (x_{1}, \dots, x_{n})

$\mathbf{f}=(f_1,\dots,f_n)\quad\mathbf{x}=(x_1,\dots,x_n)$

Ten system ma wiele cech, które sprawiają, że jest szczególnie trudny w obsłudze. Szukam pomysłów, jak efektywniej radzić sobie z systemem.

Dlaczego system jest trudny?

Funkcje są podobne do tej (ale oczywiście w wielu wymiarach):

Mają płaskie płaskowyże oddzielone regionem płynnych zmian. W 2D możesz sobie wyobrazić coś takiego dla jednego : $f_i$

Ogólnie rzecz biorąc, każdy ma dwa plateau oddzielone płynną zmianę wokół hiperpłaszczyznę wymiarowej. $f_i$ $n-1$

$f_i$ $n=1$
Funkcje są bardzo powolne do obliczenia. Szukam metody, która może uzyskać rozsądne przybliżenie katalogu głównego w jak najmniejszej liczbie iteracji.
Funkcje są obliczane metodą Monte Carlo. Oznacza to, że za każdym razem, gdy są obliczane, otrzymuję nieco inną losową wartość. Pochodne są trudne do oszacowania. Kiedy będziemy już wystarczająco blisko korzenia, hałas zacznie dominować i konieczne jest zastosowanie uśrednienia w celu zwiększenia precyzji. Idealnie powinno być możliwe uogólnienie metody na równoważną stochastyczną wersję aproksymacyjną (np. Newton → Robbins-Monro).
$n$ $n=2$ $f_1(x_1,x_2) = 0$ $f_2(x_1,x_2)=0$

Co jeszcze wiem o systemie?

Jest dokładnie jeden pierwiastek (z wyników teoretycznych).
$f_i$ $i$
$f_i$ $x_i$ $f_i(\dots, x_i, \dots)$ $x_i$ $-\infty$ $\infty$ $x_{j\ne i}$

numerical-analysis nonlinear-equations

— Szabolcs
źródło

Czy znasz dolne i górne granice wszystkich zmiennych, w których musi leżeć rozwiązanie? Im ściślejsze te granice, tym lepiej. Czy możesz podać deterministyczny przykład, w tak wysokim wymiarze, jak chcesz, który ilustruje twoje płaskowyże i trudności, ale nie wymaga symulacji Monte Carlo i nie ma losowych błędów w funkcjach (punkty bonusowe, jeśli można obliczyć pochodne)? Celem takiego deterministycznego przykładu jest zrozumienie trudności problemu, nie mówiąc, że ocena Monte Carlo nie zostanie wykorzystana w ostatecznym rozwiązaniu twojego rzeczywistego problemu.

— Mark L. Stone,

f

$f$

Nie mogę się doczekać, aby go zobaczyć

— Mark L. Stone,

Ponieważ istnieje jeden pierwiastek i nie ma żadnych ograniczeń, możesz mieć szczęście, przedstawiając go jako problem optymalizacji: zminimalizuj sumę (wzdłuż każdego wymiaru) kwadratów oryginalnej funkcji.

Metody optymalizacji klasycznej prawdopodobnie zawiodą, ale metody heurystyczne, takie jak algorytmy genetyczne lub CME-ES (kowariant itp. Adaptacja macierzy - strategia ewolucyjna) mogą działać.

— MattKelly
źródło

Takie jest podejście. Chciałbym szczególnie przyjrzeć się algorytmowi SPSA, który został opracowany specjalnie do twoich celów i jest dość niezawodny.

— Wolfgang Bangerth,

OP wspomina, że ocena funkcji jest bardzo droga (zastosowanie symulacji Monte Carlo do oceny funkcji). Czy nie stanowi to dużego problemu dla algorytmów genetycznych i innych algorytmów ewolucyjnych? Są „trywialnie równoległe” (i zwykle MC też), więc masywne obliczenia równoległe mogą być możliwe, ale czy to najlepszy sposób, aby się tu wybrać?

— GertVdE

@WolfgangBangerth Dziękuję, jak mówisz, brzmi jak właściwe rozwiązanie. Spojrzę na SPSA.

— Szabolcs

W odniesieniu do kosztownych ocen funkcji: Prawdą jest, że algorytmy genetyczne i powiązane metody heurystyczne zwykle wymagają większej liczby ocen funkcji niż metody tradycyjne. Korzyścią jest to, że metody heurystyczne często mogą rozwiązać problemy, które 1) w innym przypadku wymagałyby metody specyficznej dla problemu lub 2) zawiodłyby z powodu problemów numerycznych. W tym przykładzie prawdopodobne jest, że tradycyjne metody miałyby kłopoty ze względu na stochastyczny charakter funkcji celu i małe gradienty wzdłuż niektórych wymiarów. SPSA wygląda na świetną kandydującą metodę tego problemu.

— MattKelly,