Глобальная оптимизация - методы, библиотеки

[YuraM]

Здравствуйте, в своей научной работе (если ее так можно назвать) у меня следующая задача. Есть переменные, $x_1$ — $x_n$. Для каждой переменной есть свой интервал значений. Далее, на основании значений всех переменных у меня рассчитываются значения некоторых точек данных $y_1^{theor}$ - $y_m^{theor}$. Для этих же точек данных у меня есть значения из эксперимента, $y_1^{exp} - y_m^{exp}$. У меня $m>n$. В идеале я хочу получить значения переменных $x_1 - x_n$ которые дают наибольшее согласие $y^{ theor}$ and $y^{exp}$. Думаю это стандартная задача. Задача у меня не линейная, производных нет и не предвидется. На данный момент я решаю задачу в лоб, то есть составляю ф-цию $F = \frac 1 m \sum(y_j^{theor} - y_j^{exp})^2$ и пытаюсь оптимизировать ее глобально. Я пробовал практически все безградиентные алгоритмы в библиотеке NLOPT и несколько алгоритмов (BASINHOPPING and DIFFERENTIAL_EVOLUTION) from python optimize. BASINHOPPING, NLOPT_ GN_CRS2_LM дают пока наилучшее решения. Но - эти алгоритмы медленные.

Интересно, есть ли более быстрые безградиентные алгоритмы для таких проблем? Есть ли смысл поискать еще какие-то библиотеки? Вы знаете какие-либо библиотеки? Желательно чтобы легко было привязать к коду на питоне. Количество переменных от 23 до 100.

Интересно, если я постараюсь увеличить количество точек данных, у меня уменьшится количество локальных минимумов?

Спасибо!

[dmd]

Если правильно понимаю о чём речь, то самые быстрые безградиентные - это методы local search. Но естественно они не гарантируют глобальный оптимум. Самые быстрые из опробованных мною - это LocalSolver и java-библиотека oscar для MiniZinc. 100 переменных для LocalSolver-а вообще пустяк, он легко оперирует десятками тысяч переменных, лишь бы памяти хватило (ну и времени ждать улучшения локального оптимума, если найденный неудовлетворителен, ибо повторюсь - глобал не гарантирован).

[YuraM]

спасибо за ответ, да - Вы все правильно поняли. Я почитал, что люди делают в таких случаях. Обычно пытаются сначала уменьшить количество переменных оценивая какие из них вносят наибольший вклад, а потом запускают методы глобальной оптимизации - типа эволюционных алгоритмов и Монте-Карло. Потом, когда более или меннее "глобальное" решение для этих переменных найдено, то добавляются другие переменные, которые вначале были "заморожены" и типа все оптимизируется локально. Тут вообще вариантов не много. Либо надо аппроксимировать как-то функцию F чтобы ее вычисление было бы как можно быстрее, но, в таком случае вводится дополнительные приближения - и не факт, что найденный минимум для приближенной функции будет идентичен минимуму настояще функции. Плохо то, что по-видимому в моем случае локальных минимумов дающий похожий результат довольно много, я уже нашел три.