FUNNYDMAN Jul 2 2017 at 20:58

Метод оптимизации Нелдера — Мида. Пример реализации на Python

5 min

69K

Python*Algorithms*Mathematics*Machine learning*Programming*

+33

Comments 17

Andy_U Jul 2 2017 at 22:51

Хмм, а чем Ваша реализация лучше, чем вот эта: https://docs.scipy.org/doc/scipy-0.19.0/reference/optimize.minimize-neldermead.html#optimize-minimize-neldermead?

FUNNYDMAN Jul 2 2017 at 22:55

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

Andy_U Jul 4 2017 at 12:34

Как забавно получилось, вы молча добавили первый абзац к своей публикации после моего второго комментария, а я в результате получил кучу минусов.

И, да, вы ошиблись, утверждая, что обсуждаемый метод:

Используется по умолчанию в функции optimize из модуля scipy.optimize

Нас самом деле по умолчанию используются: one of BFGS, L-BFGS-B, SLSQP, depending if the problem has constraints or bounds.

FUNNYDMAN Jul 4 2017 at 12:45

Спасибо за ваш ответ, Andy_U. Первый абзац был изначально, и я его никак не видоизменял. Да, вы правы. По умолчанию используется BFGS, L-BFGS-B, SLSQP. Обязательно внесу поправки в статью. Спасибо за уточнение. Всего доброго!

Andy_U Jul 4 2017 at 14:07

И вам спасибо за совет не читать статьи по диагонали.

Andy_U Jul 2 2017 at 23:19

Может быть, тогда стоило начать статью с какой-нибудь подобной фразы?

redfs Jul 2 2017 at 23:54

Может у кого-нибудь есть реализация алгоритма на других языках программирования? С радостью расширю статью, естественно указав автора реализации

А каков смысл?
Деформируемый многогранник Нелдера-Мида — метод старый, реализаций немеряно. У меня со студенчества (это середина 80-х) остались реализации на Алголе для БЭСМ-6 и Фортране для ЕС и СМ-4. Не думаю, что расширение ими статьи будет кому-то полезно:)

Kazancev Jul 3 2017 at 19:29

Писал этой весной на Scilab, затем переносил в ANSYS APDL — сначала не увидел встроенных процедур, а когда их абсолютно случайно увидел их в СТАРОМ 11-м Хэлпе и прогнал примеры — не понравилась точность встроенных в ANSYS оптимизаторов. Ничётак получилось, несколько процентов форы отжал у ANSYS =)
И автор прав, требуется гонять алгоритм несколько раз до победного и правильно выбирать длину вектора старта и вектора корректировки на очередном витке цикла, иначе велик шанс не дойти до точки минимума. Хотя сам алгоритм работает шустро.

dmagin Jul 3 2017 at 10:14

Интересно, спасибо. Странно, правда, что в этом методе не используются значения функции в точках, — все равно же их считать приходится. Ну то есть те же производные по направлениям, соединяющим точки. Ясно же, что если в одном направлении функция уменьшается на 8, а в другом только на 5, то логичнее сделать шаг в первом направлении в 8/5 раза больше, чем во втором. Быстрее сходиться должно. Думаю, такой алгоритм тоже известен.

FUNNYDMAN Jul 3 2017 at 12:26

Здравствуйте, dmagin! Спасибо за Ваш комментарий. Под ваше описание подходит метод покоординатного спуска (градиентные методы).

iroln Jul 4 2017 at 01:52

Тут смысл именно в том, что это derivative free метод поиска (т. н. direct search). Функции могут быть шумные и негладкие, да вообще любые. Кстати, более продвинутые методы direct search также давно существуют, например, Generalized Pattern Search, Mesh Adaptive Search, но они и более медленные.

dmagin Jul 4 2017 at 08:28

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

makondo Jul 3 2017 at 13:39

Я когда-то на Delphi писал для диплома )
Еще на Фортране у меня был, откуда-то качал из математических библиотек.
Нелдер-Мид хорош, когда функция недифференцируема.

jetu Jul 4 2017 at 10:06

Спасибо за статью, все очень доходчиво и понятно.

Arastas Jul 4 2017 at 13:56

Офтопик, но в каком пакете Вы делали геометрические картинки?

FUNNYDMAN Jul 4 2017 at 20:56

Здравствуйте, Arastas. Я использовал сайт: http://yotx.ru/

againHelloWorld Jul 4 2017 at 20:54

Писала этот алгоритм (он еще в некоторых источниках называется «метод деформируемого многогранника») на c++ для оптимизации функции с неограниченным количеством параметров.