jkff
Удален
|
    
Итак, друзья:
Скажите пожалуйста, каким методом лучше минимизировать (чем глобальнее, тем лучше) функцию большого количества переменных, причем противную - овражную и пупырчатую, со множеством локальных минимумов? Речь идет о функции энергии системы множества тел, взаимодействующих нехитрыми способами - пружинками и электростатическим отталкиванием; мне надо найти установившееся состояние.
Специфика задачи такова, что у меня изначально дано хорошее начальное приближение.
Мне представляется два принципиально разных пути:
1) Минимизировать функционал энергии с помощью методов типа Флетчера-Ривса.
2) Метод тяжелого шарика: просто решать дифур движения системы
Переменных очень много: сотни-тысячи-десятки тысяч.
Проблемы:
1) Из-за дурной формы функции Флетчер-Ривс работает очень плохо и улетает куда-то в заоблачные дали, причем иногда даже из стабильной конфигурации (близкой к оптимуму, градиент близок к нулю).
2) Просто неприемлемо медленно сходится. Может, правда, если использовать не топорный метод Эйлера, а Рунге-Кутта например, то будет сходиться лучше, но я в этом не уверен. Наверняка ведь есть методы, которые находят именно _асимптотическое_ (на бесконечности) решение такого дифура, не заморачиваясь промежуточными шагами?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 9 дек. 2006 1:27 | IP
|
|
sms
Удален
|
То что с сотней переменных и больше кроме тривиальных случаев можно найти оптимум-не верю. Это только в книжках находят в теории.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 9 дек. 2006 20:15 | IP
|
|
jkff
Удален
|
Вы ошибаетесь. Мне кажется, Вы говорите наобум.
Я уже написал программу, которая с приемлемой для меня точностью решает мою задачу в случае примерно тысячи переменных за 3 секунды, и знаю, какие оптимизации надо выполнить, чтобы она решала не за 3, а за 3 сотых доли секунды. Все вполне реально; прошу Вас, не вводите в заблуждение рабочие массы 
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 10 дек. 2006 0:51 | IP
|
|
Old
Долгожитель
|
Если я правильно понял, то функция - потенциал в 3-х мерном пространстве, порождаемый мнгогими телами, причем вид потенциала взаимодействия пары тел ~ k*r1_2+e1*e2/r1_2? Обращается потенциал в бесконечность в точках с координатами равным координатам тел? Пробное тело аналогично взаимодействует с остальными телами?
|
Всего сообщений: 285 | Присоединился: ноябрь 2006 | Отправлено: 10 дек. 2006 1:29 | IP
|
|
jkff
Удален
|
Пространство двумерное, вид потенциала не совсем такой: некоторые тела связаны пружинами (обычными, линейными), и все тела друг с другом отталкиваются, но не по Кулоновскому закону. Потенциал в бесконечность не обращается нигде: я решил от этого избавиться, чтобы не испытывать чрезмерных проблем с неустойчивостью методов. На самом деле phi(r1, r2) ~ a exp(-b|r1-r2|) - k|r1-r2|, примерно так.
У меня, в общем, задача укладки графа.
Насчет пробного тела, если честно, не понял вопроса.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 10 дек. 2006 1:40 | IP
|
|
sms
Удален
|
Про наобум-просто я считать умею и книжки читал, когда учился. Если у вас 100 переменных и по каждой при редукции задачи к одномерной нужно хотя бы просто целевую функцию вычислить хотя бы 50 раз, то это уже 50^100 вычислений-остаётся позавидовать, если есть доступ к компьютеру, который такое тянет. Поэтому понятие "проклятие размерности" и является одним из основных в оптимизации, и пессимизма в книжках тех кто реально считает намного больше, чем оптимизма в книжках у теоретиков.
Если у Вас конкретная задача про конкретный потенциал то её наверное можно решить конкретным способом за приемлемое время-но в первом посте про это не говорилось.
Очеь хорошая небольшая книжечка о: Жилянскас, Шалтянис. Поиск оптимума. М., Наука, 1989.
А так для поиска глобального минимума с высокой точностью в общем положении нет идеальных программ даже для 2 переменных и очень хороших для 3 , насколько я знаю.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 10 дек. 2006 10:17 | IP
|
|
jkff
Удален
|
Согласен, я зря не указал в исходном посте, что мне требуется весьма и весьма невысокая точность: раз уж я укладываю граф, то точности в 0.1% по каждой переменной более чем достаточно, да и уж очень глобальная глобальность не требуется - хотя, конечно, "любой локальный минимум" ни в коем разе не подходит.
Тем более в случае укладки графов редукцию размерности можно выполнять не на 1 переменную, а в ~2-3 раза, используя multigrid. За счет этого у меня есть гарантированно близкое к подходящему оптимуму начальное приближение.
Книжку поищу, спасибо.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 10 дек. 2006 13:49 | IP
|
|
sms
Удален
|
Похоже, что по сути у Вас задача от одной переменной r1-r2.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 12 дек. 2006 18:59 | IP
|
|
jkff
Удален
|
Нет, у меня задача от n-1 переменных вида ri-r1, i=2..n, если уж ставить задачу в терминах именно разностей координат.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 12 дек. 2006 21:14 | IP
|
|
Old
Долгожитель
|
Попытаюсь решить Вашу задачу аналитически (с привлечением статистических методов), но для этого мне нужно знать точный вид потенциала.
Поясню свой интерес. Давненько - и бросил - пытался найти минимум энергии взаимодействия для разных кристаллических конфигураций для системы многих жестких одинаковых сферических диполей. Что-то получил. формулы громоздкие и, не знаю, правильны ли. На "пальцах", по крайней мере, непротиворечивы. Может Ваша задача поддастся?
|
Всего сообщений: 285 | Присоединился: ноябрь 2006 | Отправлено: 28 дек. 2006 22:34 | IP
|
|
|
Форум
Многомерная оптимизация: Как лучше?
