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

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

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

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

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

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

Алгоритм

Пусть требуется найти безусловный минимум функции 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_{i}^{(1)},x_{i}^{(2)},\ldots ,x_{i}^{(n)}\right),i=1..n+1$, образующие симплекс 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_{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}\gets x_{l}+(x_{i}-x_{l})/2$, $i\neq l$.

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

Источники

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