Метод Нелдера — Мида

Последовательные симплексы в методе Нелдера-Мида для функции Розенброка (вверху) и функции Химмельблау (внизу)

Не путать с «симплекс-методом» из линейного программирования — методом оптимизации линейной системы с ограничениями.

Метод Нелдера — Мида, также известный как метод деформируемого многогранника и симплекс-метод, — метод безусловной оптимизации функции от нескольких переменных, не использующий производной (точнее — градиентов) функции, а поэтому легко применим к негладким и/или зашумлённым функциям.

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс. Более развитый подход к исключению локальных экстремумов предлагается в алгоритмах, основанных на методе Монте-Карло, а также в эволюционных алгоритмах.

Алгоритм

Пусть требуется найти безусловный минимум функции n переменных $f(x^{(1)},x^{(2)},\dots ,x^{(n)})$. Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.

Параметрами метода являются:

• коэффициент отражения $\alpha >0$, обычно выбирается равным $1$.
• коэффициент сжатия $\beta >0$, обычно выбирается равным $0,5$.
• коэффициент растяжения $\gamma >1$, обычно выбирается равным $2$.

1. «Подготовка». Вначале выбирается $n+1$ точка $x_i=(x_i^{(1)},x_i^{(2)},\dots ,x_i^{(n)}),i=1..n+1$, образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: $f_1=f(x_1),f_2=f(x_2),\dots ,f_{n+1}=f(x_{n+1})$.
2. «Сортировка». Из вершин симплекса выбираем три точки: $x_h$ с наибольшим (из выбранных) значением функции $f_h$, $x_g$ со следующим по величине значением $f_g$ и $x_l$ с наименьшим значением функции $f_l$. Целью дальнейших манипуляций будет уменьшение по крайней мере $f_h$.
3. Найдём центр тяжести всех точек, за исключением $x_h$: $x_c=\frac{1}{n}\sum _{i\ne h}{x}_i$. Вычислять $f_c=f(x_c)$ не обязательно.
4. «Отражение». Отразим точку $x_h$ относительно $x_c$ с коэффициентом $\alpha$ (при $\alpha =1$ это будет центральная симметрия, в общем случае — гомотетия), получим точку $x_r$ и вычислим в ней функцию: $f_r=f(x_r)$. Координаты новой точки вычисляются по формуле:

   $x_r=(1+\alpha )x_c-\alpha x_h$.

5. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место $f_r$ в ряду $f_h,f_g,f_l$.

   Если $f_r<f_l$, то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка $x_e=(1-\gamma )x_c+\gamma x_r$ и значение функции $f_e=f(x_e)$.

   Если $f_e<f_r$, то можно расширить симплекс до этой точки: присваиваем точке $x_h$ значение $x_e$ и заканчиваем итерацию (на шаг 9).

   Если $f_r<f_e$, то переместились слишком далеко: присваиваем точке $x_h$ значение $x_r$ и заканчиваем итерацию (на шаг 9).

   Если $f_l<f_r<f_g$, то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке $x_h$ значение $x_r$ и переходим на шаг 9.

   Если $f_g<f_r<f_h$, то меняем местами значения $x_r$ и $x_h$. Также нужно поменять местами значения $f_r$ и $f_h$. После этого идём на шаг 6.

   Если $f_h<f_r$, то просто идём на следующий шаг 6.

   В результате (возможно, после переобозначения) $f_l<f_g<f_h<f_r$.

6. «Сжатие». Строим точку $x_s=\beta x_h+(1-\beta )x_c$ и вычисляем в ней значение $f_s=f(x_s)$.
7. Если $f_s<f_h$, то присваиваем точке $x_h$ значение $x_s$ и идём на шаг 9.
8. Если $f_s>f_h$, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением $x_l$:

   $x_i\leftarrow x_l+(x_i-x_l)/2$, $i\ne l$.

9. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.

Источники

• КУРС «Многомерная оптимизация». Лекция 10. Метод Нелдера — Мида на сайте Института дистанционного обучения ИНТУИТ. Подробное описание, есть иллюстрации.
• Метод Нелдера-Мида. Краткий алгоритм.
• Список ссылок на численные методы
• J. A. Nelder and R. Mead, Computer Journal, 1965, vol. 7, p. 308—313Шаблон:Ref-en.