Ein schwieriges Gleichungssystem numerisch lösen

Ich habe ein System von nichtlinearen Gleichungen, die ich numerisch lösen möchte: $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)$

Dieses System weist eine Reihe von Eigenschaften auf, die die Handhabung besonders schwierig machen. Ich suche nach Ideen, wie ich effektiver mit dem System umgehen kann.

Warum ist das System schwierig?

Die Funktionen sind ähnlich (aber natürlich in mehreren Dimensionen):

Sie haben flache Plateaus, die durch einen Bereich sanften Wandels getrennt sind. In 2D können Sie sich so etwas für ein vorstellen : $f_i$

Im Allgemeinen jeweils hat zwei Plateaus durch glatte Änderung um einen abgetrennten dimensionale Hyperebene. $f_i$ $n-1$

$f_i$ $n=1$
Die Funktionen sind sehr langsam zu berechnen. Ich suche nach einer Methode, mit der sich die Wurzel in möglichst wenigen Iterationen vernünftig annähern lässt.
Die Funktionen werden mit einer Monte-Carlo-Methode berechnet. Dies bedeutet, dass ich jedes Mal, wenn sie berechnet werden, einen etwas anderen Zufallswert erhalte. Derivate sind schwer abzuschätzen. Sobald wir nahe genug an der Wurzel sind, beginnt das Rauschen zu dominieren, und es ist notwendig, die Mittelung zu verwenden, um die Genauigkeit zu erhöhen. Idealerweise sollte es möglich sein, die Methode auf eine äquivalente stochastische Approximationsversion (z. B. Newton → Robbins-Monro) zu verallgemeinern .
$n$ $n=2$ $f_1(x_1,x_2) = 0$ $f_2(x_1,x_2)=0$

Was weiß ich noch über das System?

Es gibt genau eine Wurzel (aus theoretischen Ergebnissen).
$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
quelle

Kennen Sie die unteren und oberen Grenzen aller Variablen, innerhalb derer die Lösung liegen muss? Je enger diese Grenzen, desto besser. Können Sie ein deterministisches Beispiel in einer so hohen Dimension geben, wie Sie möchten, das Ihre Plateaus und Schwierigkeiten veranschaulicht, jedoch keine Monte-Carlo-Simulation erfordert und keine zufälligen Fehler in den Funktionen aufweist (Bonuspunkte, wenn Ableitungen berechnet werden können)? Der Zweck eines solchen deterministischen Beispiels besteht darin, die Schwierigkeiten des Problems zu verstehen und nicht zu sagen, dass die Monte-Carlo-Bewertung nicht zur endgültigen Lösung Ihres tatsächlichen Problems verwendet wird.

Mark L. Stone

f

$f$

Ich freue mich darauf, es zu sehen,

Mark L. Stone

Antworten:

Da es eine einzelne Wurzel gibt und es keine Einschränkungen gibt, haben Sie möglicherweise Glück, wenn Sie dies als Optimierungsproblem darstellen: Minimieren Sie die Summe (entlang jeder Dimension) der Quadrate Ihrer ursprünglichen Funktion.

Klassische Optimierungsmethoden werden wahrscheinlich fehlschlagen, aber heuristische Methoden wie genetische Algorithmen oder CME-ES (kovariante usw. Matrixanpassung - Evolutionsstrategie) könnten funktionieren.

MattKelly
quelle

Das ist in der Tat der richtige Ansatz. Ich würde insbesondere den SPSA-Algorithmus betrachten, der speziell für Ihren Zweck entwickelt wurde und ziemlich robust ist.

Wolfgang Bangerth

Das OP erwähnt, dass die Bewertung der Funktion sehr teuer ist (Anwendung der Monte-Carlo-Simulation für eine Funktionsbewertung). Ist das nicht ein sehr großes Problem für genetische Algorithmen und andere evolutionäre Algorithmen? Sie sind "trivial parallel" (und MC normalerweise auch), so dass massives paralleles Rechnen möglich sein könnte, aber sind sie der beste Weg, um hierher zu gelangen?

GertVdE

@ WolfgangBangerth Danke, wie du sagst, es klingt nach der richtigen Lösung. Ich werde mir SPSA ansehen.

Szabolcs

In Bezug auf teure Funktionsbewertungen: Es ist richtig, dass genetische Algorithmen und verwandte heuristische Methoden tendenziell eine größere Anzahl von Funktionsbewertungen erfordern als herkömmliche Methoden. Der Vorteil ist, dass heuristische Methoden häufig Probleme lösen können, die 1) ansonsten eine problemspezifische Methode erfordern würden oder 2) aufgrund numerischer Probleme fehlschlagen würden. In diesem Beispiel ist es wahrscheinlich, dass herkömmliche Methoden aufgrund der stochastischen Natur der Zielfunktion und der kleinen Gradienten entlang einiger Dimensionen Probleme haben würden. SPSA scheint eine großartige Kandidatenmethode für dieses Problem zu sein.

MattKelly