Многоэкстремальная оптимизация

[Katyunya]

Всем добрый день!
У такой вопрос: решаю оптимизационную задачу (поиск минимума). Аналитическое выражение для целевой функции отсутствует (очень сложно получить), просто получаю значения целевой функции при конкретном значении начальных данных. Поэтому градиентные методы применить нельзя. Пробовала применить симплексный метод (его вариантами являются методы Хука-Дживса, Нелдера-Мида). Но при разных начальных данных разный результат. Значит, функция многоэкстремальная.
Не подскажите ли Вы, каким методом можно пользоваться для оптимизации многоэкстремальной функции, к тому же не имеющей аналитического выражения (заданной таблично)?
Нет ли каких-то модификаций симплексного метода, позволяющих искать не локальный, а глобальный минимум?
Заранее большое спасибо!

[Troki]

Доброго времени суток! Рекомендую посмотреть книгу: Б.Хэссард, Н.Казаринов, И.Вэн Теория и приложения бифуркации рождения цикла. М., Мир, 1985. Мне эта книга очень помогла. С дружеским приветом Сергей.

[Yuri Gendelman]

Katyunya писал(а):

Нет ли каких-то модификаций симплексного метода, позволяющих искать не локальный, а глобальный минимум?

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

[PAV]

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

[незваный гость]

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

[PAV]

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

[Katyunya]

Всем большое спасибо за советы!