Метод деформируемого многогранника (метод Нелдера-Мида)

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

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

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

Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.

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

1) коэффициент отражения α > 0, обычно выбирается равным 1.

2) коэффициент сжатия β > 0, обычно выбирается равным 0,5.

3) коэффициент растяжения γ > 0, обычно выбирается равным 2.

Алгоритм данного метода такой:

1. «Подготовка». Вначале выбирается n + 1 точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .

2. «Сортировка». Из вершин симплекса выбираем три точки: x_h с наибольшим (из выбранных) значением функции f_h, x_g со следующим по величине значением f_g и x_l с наименьшим значением функции f_l. Целью дальнейших манипуляций будет уменьшение по крайней мере f_h.

3. Найдём центр тяжести всех точек, за исключением x_h: . Вычислять f_c = f(x_c) не обязательно.

4. «Отражение». Отразим точку x_h относительно x_c с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку x_r и вычислим в ней функцию: f_r = f(x_r). Координаты новой точки вычисляются по формуле:

x_r = (1 + α)x_c − αx_h (2)

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

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

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

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

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

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

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

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

6. «Сжатие». Строим точку x_s = βx_h + (1 − β)x_c и вычисляем в ней значение f_s = f(x_s).

7. Если f_s < f_h, то присваиваем точке x_h значение x_s и идём на шаг 9.

8. Если f_s > f_h, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением x_l:

  (3)

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