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

вопросы строения молекул и квантовой химии
Ответить
YuraM
Сообщения: 459
Зарегистрирован: Пн ноя 26, 2007 11:07 pm

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

Сообщение YuraM » Пт окт 20, 2017 3:41 pm

Здравствуйте, в своей научной работе (если ее так можно назвать) у меня следующая задача. Есть переменные, x1 - xn. Для каждой переменной есть свой интервал значений. Далее, на основании значений всех переменных уменя рассчитываются значения некоторых точек данных y1_theor - ym_theor. Для этих же точек данных у меня есть значения из эксперимента, y1_exp - ym_exp. У меня m>n. В идеале я хочу получить значения переменных x1 - xn которые дают наибольшее согласие y_theor and y_exp. Думаю это стандартная задача. Задача у меня не линейная, производных нет и не предвидется. На данный момент я решаю задачу в лоб, то есть составляю ф-цию F = (1/m)*summ(y_j_theor - y_j_exp)**2 и пытаюсь оптимизировать ее глобально. Я пробывал тпрактически все безградиентные алгоритмы в библиотеке NLOPT и несколько алгоритмов (BASINHOPPING and DIFFERENTIAL_EVOLUTION) from python optimize. BASINHOPPING, NLOPT_ GN_CRS2_LM дают пока наилучшее решения. Но - эти алгоритмы медленные.

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

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

Спасибо!

Спросил этот же вопрос на dxdy.
Кто смел тот и съел

Аватара пользователя
leonidas
Сообщения: 240
Зарегистрирован: Чт дек 23, 2010 6:27 pm

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

Сообщение leonidas » Ср ноя 01, 2017 12:20 pm

Насколько я понял у вас есть функция y(x1,...,xn), известно ли качественное поведение этой функции? Что это за функция?
То что вы описали это называет Fitting of PES. С функцией F=... всё правильно, только можно еще ввести weight functions w(j), если для некоторых точек нужно более точное качество фиттирования, например, в окрестности минимумов.

Я для этих целей использую Levenberg–Marquardt algorithm, он доступен во многих библиотеках, например в MINPACK. Правда этот метод градиентный, а почему вам градиентные методы не подходят?

YuraM
Сообщения: 459
Зарегистрирован: Пн ноя 26, 2007 11:07 pm

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

Сообщение YuraM » Пт ноя 03, 2017 6:26 pm

спасибо за ответ! это, как мне кажется не PES fitting, but rather nonlinear globaloptimization. Задача сводится к подгонке (параметризации) теоретической модели для воспроизведение экспериметальных данных. Я не думаю, что поведение такой функции известно. Градиентов просто нет. Если только считать их численно, но я где-то читал, что методы типа симплекса сойдуться быстрее к локальному минимуму. Я почитал статьи и форумы, тут действительно вариантов не много - либо генетичекие и эволюционные алгоритмы либо Монте-Карло. Да, насчет весов я как-то пока не думал, но наверное есть смысл их вводить при интересе в определенных точках.
Кто смел тот и съел

Аватара пользователя
madschumacher
Сообщения: 883
Зарегистрирован: Ср авг 05, 2015 4:30 pm

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

Сообщение madschumacher » Пт ноя 03, 2017 7:27 pm

А PES fitting -- это одна из разновидностей задачи оптимизации. Вообще точных алгоритмов глобальной оптимизации, afaik, не существует вообще. Или локальная (градиентный спуск, М-Л, квази-Ньютон, minimum volume ellipsoid и т.д.) с последующей заменой начальных условий, либо эвристика (эволюционка, отжиг и т.д.). Можно комбинировать первое и второе.

При увеличении числа точек тоже нельзя ничего определённого сказать: задача может стать более корректной, а может и не стать. Зависит от задачи и от точек. :dontknow:

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

Аватара пользователя
leonidas
Сообщения: 240
Зарегистрирован: Чт дек 23, 2010 6:27 pm

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

Сообщение leonidas » Сб ноя 04, 2017 7:14 pm

Дайте pls ссылку на вашу тему на dxdy, вдруг там что интересное напишут. Не имеет значения, что вы оптимизируете и фитируете,
принцип тот же. В Levenberg–Marquardt можно градиенты считать численно, я обычно так и делаю. Более того, там есть возможность использовать параметр регуляризации, т.е. "damping", что может пригодиться когда значения функции находятся с погрешностью.
В моей среде многие хвалят RKHS, см. 10.1063/1.1288268, но всё не доходят руки и ноги протестировать.

YuraM
Сообщения: 459
Зарегистрирован: Пн ноя 26, 2007 11:07 pm

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

Сообщение YuraM » Сб ноя 04, 2017 10:53 pm

http://dxdy.ru/topic121812.html
i read somewhere that numerical gradients + gradient based optimization is slower than Nelder-Mead (https://en.wikipedia.org/wiki/Nelder%E2 ... ead_method) i'll have a look at the methods you've mentioned, thank you
Кто смел тот и съел

Ответить

Вернуться в «квантовая химия и моделирование»

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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 16 гостей