Многомерная оптимизация "пупырчатой" функции: Как

[jkff]

Итак, друзья:
Скажите пожалуйста, каким методом лучше минимизировать (чем глобальнее, тем лучше) функцию большого количества переменных, причем противную - овражную и пупырчатую, со множеством локальных минимумов? Речь идет о функции энергии системы множества тел, взаимодействующих нехитрыми способами - пружинками и электростатическим отталкиванием; мне надо найти установившееся состояние.
Специфика задачи такова, что у меня изначально дано хорошее начальное приближение.

Мне представляется два принципиально разных пути:
1) Минимизировать функционал энергии с помощью методов типа Флетчера-Ривса.
2) Метод тяжелого шарика: просто решать дифур движения системы

Переменных очень много: сотни-тысячи-десятки тысяч.

Проблемы:
1) Из-за дурной формы функции Флетчер-Ривс работает очень плохо и улетает куда-то в заоблачные дали, причем иногда даже из стабильной конфигурации (близкой к оптимуму, градиент близок к нулю).

2) Просто неприемлемо медленно сходится. Может, правда, если использовать не топорный метод Эйлера, а Рунге-Кутта например, то будет сходиться лучше, но я в этом не уверен. Наверняка ведь есть методы, которые находят именно _асимптотическое_ (на бесконечности) решение такого дифура, не заморачиваясь промежуточными шагами?

[Yuri Gendelman]

Насколько мне известно, численных методов поиска глобального экстремума для "противных овражно-пупырчатых" функций не существует даже для 2х переменных, а уж тем более для тысяч и десятков тысяч. Практически все существующие методы реализуют поиск локального экстремума. Для поиска именно глобального экстремума многократно ищут локальные, начиная с разных начальных точек. Альтернатива - методы случайного поиска.

jkff писал(а):

Специфика задачи такова, что у меня изначально дано хорошее начальное приближение.

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

jkff писал(а):

Наверняка ведь есть методы, которые находят именно _асимптотическое_ (на бесконечности) решение такого дифура, не заморачиваясь промежуточными шагами?

Есть методы асимптотического анализа, но аналитические, не численные.

[Горьковчанин]

Насколько я знаю, задачи многомерной глобальной оптимизации - хлеб одной из кафедр кафедр Нижегородского госуниверситета, тематика Р.Г. Стронгина. Вот список книжек с его странички:
1) Численные методы в многоэкстремальных задачах. Информационно- статистический подход. М.: Наука, 1978, 240 стр.
2) Поиск глобального оптимума. М.: Знание, 1990.
3) Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms (в соавторстве с Я.Д.Сергеевым). Kluwer Academic Publishers. Dordrecht. The Netherlands, 2000, 728 pp.

[KogdaToBylNaSborah]

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

Да, известное начальное приближение можно просто добавить в первое поколение, это сильно поможет.