Нахождение минимума функционала за адекватное время

[Евгеша]

Здравствуйте! Посоветуйте что-нибудь для решения следующей задачи.

Задача такая:

1. Есть два больших массива входных данных (размерность порядка нескольких тысяч)
2. Есть функция/алгоритм, вычисляющая по этим данным, некоторый результат - число. Время одного прогона - 1-2 минуты, т. е. чтобы прогнать оба массива один раз, потребуется минуты 3-4.
3. У этой этого алгоритма есть 6 параметров.

Задача - подобрать эти параметры так, чтобы результаты обработки обоих массивов были достаточно близки (с заданной точностью).

Входные данные и сам алгоритм очень сложны, и, по факту, можно считать черным ящиком, в котором можно менять параметры, и смотреть на результат.

Математически, я бы сформулировал задачу так:

Пусть $X_1, X_2$ - заданные входные данные, $F(X_i, c) = k_i\in\mathbb{R}$ - наш алгоритм, где $c\in\mathbb{R}^6$ - набор параметров, вектор 6-мерного пространства.
Для краткости введем обозначение $F_i(c) = F(X_i, c)$.
Тогда вопрос будет звучать следующим образом:

Найти $c$ из заданного промежутка, при котором значение функционала $||F_1(c)| - |F_2(c)||$ минимально, либо:

Найти такое $c$, при котором $||F_1(c)| - |F_2(c)|| < \varepsilon$, где $\varepsilon$ - заданная точность.

Единственная возникшая идея у меня - варьировать параметры в некотором диапазоне и сравнивать результаты. Но простым перебором получится очень долго (уйдут часы, а то и дни). То есть, если учесть, что на один просчет уходит 3-4 минуты, а хотелось бы уложиться хотя бы в полчаса, то нужно не более 10 итераций.

Сразу в голову пришел метод половинного деления, но как его обобщить на случай 6-мерного аргумента? Или может есть другие методы?

Заранее благодарю.

[Pavia]

Евгеша
Метод покоординатного спуска. С начало по одной координате потом по другой после 6 делаете ещё один заход.
Можно более оптимально метод градиентного спуска.
Или ещё можно нанять кластер запустить параллельно.

[Dmitriy40]

По моему тут необходимы данные о степени гладкости функционала от параметров. Если там могут быть резкие скачки, то придётся выбирать сетки не реже интервала между скачками, чтобы не пропустить "долины" (или "горы"). И это будет ограничением снизу на время вычислений.
Заявленное время в полчаса совершенно нереалистично: его хватит лишь чтобы получить оценки на краях диапазона по каждому параметру, на поиск решения времени уже не остаётся.
Без априорных знаний о поведении функционала от параметров за несколько часов можно лишь примерно оценить требуемое время поиска решения: методом деления пополам идти по параметрам и строить график уменьшения ошибки, сделав 4-5 итераций по каждому параметру ($(2+4..5)\cdot6\cdot3..4=108..168$ минут или до трёх часов) можно примерно прикинуть скорость уменьшения ошибки и оценить общее требуемое время.

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

-- 20.06.2019, 14:18 --

Да, насчёт метода половинного деления для более одного параметра. Ничего тут сложного, в цикле делим пополам каждый параметр, выбираем нужную точку, и лишь после перебора всех параметров переходим к следующей итерации метода деления пополам. Тут тоже требуется гладкость функционала от всех и каждого в отдельности параметров.
Плюс требуется монотонность функционала в интервале между точками по каждому параметру отдельно. Т.е. может потребоваться сначала посчитать достаточно частую сетку чтобы найти интервалы монотонности по каждому параметру (если этих сведений нет априорно) и лишь потом в каждом найденном интервале (и по каждому параметру!) запускать отдельный цикл поиска решений.

[B@R5uk]

Dmitriy40 в сообщении #1400338 писал(а):

Да, насчёт метода половинного деления для более одного параметра. Ничего тут сложного, в цикле делим пополам каждый параметр, выбираем нужную точку, и лишь после перебора всех параметров переходим к следующей итерации метода деления пополам.

Зачем такие сложности? Причём это далеко не оптимальный алгоритм. Я всё не устану рекламировать метод Нелдера-Мида, как по мне для этой задачи это самый что ни на есть алгоритм в тему.

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