Я пытаюсь реализовать алгоритм Nelder-Mead для оптимизации функции. Страница Википедии о Nelder-Mead удивительно ясна обо всем алгоритме, за исключением критерия его остановки. Там это печально говорит:
Проверьте сходимость [требуется уточнение] .
Я попробовал и протестировал пару критериев сам:
Стоп , если , где ε мала и где х я это я -я вершина симплекса, заказал у минимума ( е ( х 1 ) ) до высокой ( F ( х N + 1 )) значения функции. Другими словами, когда максимальное значение симплекса почти равно минимальному значению. Я обнаружил, что это не работает должным образом, так как это не дает никаких гарантий относительно того, что функция делает внутри симплекса. В качестве примера рассмотрим функцию: Это, конечно, тривиальная задача для оптимизации, но давайте скажем, что мы делаем это с NM, и пусть наши две симплексные точки будут x 1 = - 1 и x 2 = 1 . Алгоритм будет сходиться здесь, не находя своего оптимума.
Второй вариант предполагает оценку центроида симплекса: остановите, если . Это предполагает, что если нижняя точка симплекса и центроида имеют такие сходные значения, симплекс достаточно мал, чтобы вызвать сходимость.
Это правильный способ проверки на сходимость? Или есть проверенный способ проверить это? Я не смог найти никаких источников по этому поводу, так как большинство поисковых хитов фокусируется на сложности алгоритма.
Ответы:
Изложение этого «алгоритма нисходящего симплекса» в оригинальных версиях Numeric Recipes особенно понятно и полезно. Поэтому я процитирую соответствующие части этого. Вот фон:
Теперь о проблеме под рукой, заканчивая алгоритм. Обратите внимание на общность учетной записи: авторы дают интуитивно понятный и полезный совет для завершения работы любого многомерного оптимизатора, а затем показывают, как конкретно он применяется к этому конкретному алгоритму. Первый абзац отвечает на вопрос перед нами:
[Страницы 290-292.]
Ссылка
Уильям Х. Пресс и соавт. , Численные Рецепты: Искусство Научного Вычисления. Издательство Кембриджского университета (1986). Посетите http://numeric.recipes/ для последних выпусков.
источник
Не полный ответ, но слишком длинный для комментария и может поставить вас на правильный путь.
Эта тема кратко рассматривается на странице 171 "Компактные численные методы для компьютеров" 2-е издание, Джон С. Нэш. И, как оказалось, это ссылка, процитированная для подпрограммы Nelder-Mead, реализованной в
optim()
функции R. Цитирую соответствующую часть:Беглый взгляд на источник
optim()
показывает, что он использует разницу между самым высоким и самым низким значениями функций (точек, определяющих симплекс), чтобы определить сходимость:if (VH <= VL + convtol || VL <= abstol) break;
гдеVH
находится высокое значение иVL
низкое значение. Это связано с предупреждением, что я очень быстро взглянул на источник и, возможно, что-то упустил.Теперь ваш вариант (1) представляется вторым подходом, отстаиваемым Нэшем. Он также обсуждает проблему, с которой вы столкнулись:
Оригинальные ссылки, на которые ссылается Нэш здесь:
Нелдер Дж. А., Мид Р. 1965. Симплексный метод минимизации функций. Компьютерный журнал 7: 308-313.
О'Нил Р. 1971. Алгоритм А.С. 47: Минимизация функций с помощью симплексной процедуры. Прикладная статистика 20: 338-345.
источник
еще предстоит выяснить - реальные тестовые случаи приветствуются.
(Реальный
Stopiter
класс имеет много условий остановки, в дополнение кpatience
; самое простое - время настенных часов.)Смотрите также:
NLopt : множество алгоритмов, включая Nelder-Mead, их легко сравнивать. В особенности обратите внимание на примечания по сравнению алгоритмов
Downhill : терпение останавливается с
min_improvement
источник