Численное решение сложной системы уравнений

У меня есть система из нелинейных уравнений, которые я хочу решить численно: $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)$

Эта система имеет ряд характеристик, которые делают ее особенно сложной в обращении. Я ищу идеи о том, как работать с системой более эффективно.

Почему система сложна?

Функции похожи на эту (но, конечно, в нескольких измерениях):

У них плоские плато, разделенные областью плавного изменения. В 2D вы можете представить что-то вроде этого для одного : $f_i$

Как правило, у каждого есть два плато, разделенных плавным изменением вокруг мерной гиперплоскости. $f_i$ $n-1$

$f_i$ $n=1$
Функции очень медленно вычисляются. Я ищу метод, который может получить разумное приближение корня за как можно меньшее количество итераций.
Функции рассчитываются методом Монте-Карло. Это означает, что каждый раз, когда они вычисляются, я получаю немного другое случайное значение. Производные сложно оценить. Как только мы подойдем достаточно близко к корню, шум начнет доминировать, и для повышения точности необходимо использовать усреднение. В идеале должна быть возможность обобщения метода на эквивалентную версию стохастической аппроксимации (например, Ньютон → Роббинс-Монро).
$n$ $n=2$ $f_1(x_1,x_2) = 0$ $f_2(x_1,x_2)=0$

Что еще я знаю о системе?

Существует ровно один корень (из теоретических результатов).
$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 Сабольч
источник

Знаете ли вы нижнюю и верхнюю границы для всех переменных, в пределах которых должно лежать решение? Чем теснее эти границы, тем лучше. Можете ли вы привести детерминистский пример в таком высоком измерении, который вам нужен, который иллюстрирует ваши плато и трудности, но не требует симуляции Монте-Карло и не имеет случайных ошибок в функциях (бонусные баллы, если можно вычислить производные)? Цель такого детерминированного примера - понять трудности проблемы, а не сказать, что оценка по методу Монте-Карло не будет использована для окончательного решения вашей актуальной проблемы.

Марк Л. Стоун

f

$f$

Я с нетерпением жду этого,

Марк Л. Стоун

Ответы:

Поскольку существует один корень и нет ограничений, вам может повезти, представив это как задачу оптимизации: минимизируйте сумму (по каждому измерению) квадратов вашей исходной функции.

Классические методы оптимизации, скорее всего, потерпят неудачу, но эвристические методы, такие как генетические алгоритмы или CME-ES (ковариантная и т. Д. Адаптация матрицы - эволюционная стратегия), могут работать.

MattKelly
источник

Это действительно подход. Я бы особенно посмотрел на алгоритм SPSA, который был разработан специально для ваших целей и является достаточно надежным.

Вольфганг Бангерт

В OP упоминается, что функция очень дорогая для оценки (применение моделирования Монте-Карло для оценки функции). Разве это не представляет собой очень большую проблему для генетических алгоритмов и других эволюционных алгоритмов? Они «тривиально параллельны» (и обычно ли это тоже MC), поэтому массивные параллельные вычисления могут быть возможны, но являются ли они лучшим путем?

GertVdE

@WolfgangBangerth Спасибо, как вы говорите, это звучит как правильное решение. Я посмотрю на SPSA.

Сабольч

Относительно дорогостоящих оценок функций. Это правда, что генетические алгоритмы и связанные с ними эвристические методы, как правило, требуют большего количества оценок функций, чем традиционные методы. Преимущество состоит в том, что эвристические методы часто могут решать проблемы, которые 1) в противном случае требовали бы специфичного для задачи метода или 2) потерпели бы неудачу из-за численных проблем. В этом примере вполне вероятно, что традиционные методы будут иметь проблемы из-за стохастической природы целевой функции и небольших градиентов по некоторым измерениям. SPSA выглядит как отличный метод для решения этой проблемы.

MattKelly