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

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

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

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

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

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

Алгоритм

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

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

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

1. «Подготовка». Вначале выбирается $n+1$ точка $x_i = \left(x^{(1)}_i,x^{(2)}_i,\ldots,x^{(n+1)}_i\right)$, образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: $f_1=f(x_1), f_2=f(x_2),\ldots, 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\limits_{i\neq 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_l$, то можно расширить симплекс до этой точки: присваиваем точке $x_h$ значение $x_e$ и заканчиваем итерацию (на шаг 9).

   Если $f_l<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 \gets x_l + (x_i-x_l)/2$, $i \ne l$.

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

Источники

• КУРС «Многомерная оптимизация». Лекция 10. Метод Нелдера-Мида на сайте Института дистанционного обучения ИНТУИТ

. Подробное описание, есть иллюстрации.

• Метод Нелдера-Мида. Краткий алгоритм.
• Список ссылок на численные методы
• J.A. Nelder and R. Mead, Computer Journal, 1965, vol 7, pp 308—313 [1] (текст не общедоступен) (англ.)