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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Nelder Mead1.gif
Nelder Mead2.gif

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

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

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

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

Алгоритм[править | править вики-текст]

Пусть требуется найти безусловный минимум функции 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)}_i\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_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.

Источники[править | править вики-текст]

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