2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Многомерная оптимизация "пупырчатой" функции: Как
Сообщение09.12.2006, 02:08 


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

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

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

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

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

 Профиль  
                  
 
 Re: Многомерная оптимизация "пупырчатой" функции:
Сообщение12.12.2006, 16:01 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 
Сообщение12.12.2006, 18:03 


01/06/06
107
Насколько я знаю, задачи многомерной глобальной оптимизации - хлеб одной из кафедр кафедр Нижегородского госуниверситета, тематика Р.Г. Стронгина. Вот список книжек с его странички:
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.

 Профиль  
                  
 
 Re: Многомерная оптимизация "пупырчатой" функции: Как
Сообщение15.09.2012, 10:38 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: nimepe


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group