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