- Метод Нелдера — Мида
-
Метод Нелдера — Мида
Последовательные симплексы в методе Нелдера-Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу)- Не путать с «симплекс-методом» из линейного программирования — методом оптимизации линейной системы с ограничениями.
Метод Нелдера — Мида, также известный как метод деформируемого многогранника и симплекс-метод, — метод безусловной оптимизации функции от нескольких переменных, не использующий производной (точнее — градиентов) функции, а поэтому легко применим к негладким и/или зашумлённым функциям.
Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.
Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс. Более развитый подход к исключению локальных экстремумов предлагается в алгоритмах, основанных на методе Монте-Карло, а также в эволюционных алгоритмах.
Алгоритм
Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.
Параметрами метода являются:
- коэффициент отражения α > 0, обычно выбирается равным 1.
- коэффициент сжатия β > 0, обычно выбирается равным 0,5.
- коэффициент растяжения γ > 0, обычно выбирается равным 2.
- «Подготовка». Вначале выбирается n + 1 точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .
- «Сортировка». Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.
- Найдём центр тяжести всех точек, за исключением xh: . Вычислять fc = f(xc) не обязательно.
- «Отражение». Отразим точку xh относительно xc с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку xr и вычислим в ней функцию: fr = f(xr). Координаты новой точки вычисляются по формуле:
- xr = (1 + α)xc − αxh.
- Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh,fg,fl.
- Если fr < fl, то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка xe = (1 − γ)xc + γxr и значение функции fe = f(xe).
- Если fe < fl, то можно расширить симплекс до этой точки: присваиваем точке xl значение xe и заканчиваем итерацию (на шаг 9).
- Если fe > fl, то переместились слишком далеко: присваиваем точке xl значение xr и заканчиваем итерацию (на шаг 9).
- Если fl < fr < fg, то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке xh значение xr и переходим на шаг 9.
- Если fh > fr > fg, то меняем местами значения xr и xh и идём на шаг 6.
- Если fr > fh, то просто идём на следующий шаг 6.
- В результате (возможно, после переобозначения) fr > fh > fg > fl.
- Если fr < fl, то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка xe = (1 − γ)xc + γxr и значение функции fe = f(xe).
- «Сжатие». Строим точку xs = βxh + (1 − β)xc и вычисляем в ней значение fs = f(xs).
- Если fs < fh, то присваиваем точке xh значение xs и идём на шаг 9.
- Если fs > fh, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением xl:
- , .
- Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.
Источники
- КУРС «Многомерная оптимизация». Лекция 10. Метод Нелдера-Мида на сайте ИНТУИТа. Подробное описание, есть иллюстрации.
- Метод Нелдера-Мида. Краткий алгоритм.
- Список ссылок на численные методы
- J.A. Nelder and R. Mead, Computer Journal, 1965, vol 7, pp 308—313 [1] (текст не общедоступен)(англ.)
Методы оптимизации Одномерные Метод золотого сечения • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод Фибоначчи • Метод троичного поиска Прямые методы Метод Гаусса • Метод Нелдера — Мида • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса Первого порядка Градиентный спуск • Метод покоординатного спуска • Метод сопряжённых градиентов Второго порядка Метод Ньютона • Метод Ньютона-Рафсона Стохастические Дифференциальная эволюция • Имитация отжига Методы линейного
программированияМетод эллипсоидов • Симплекс-метод • Метод потенциалов
Wikimedia Foundation. 2010.