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

Метод Нелдера
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+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.

Источники

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Метод Нелдера" в других словарях:

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

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

  • Метод Хука — Дживса (англ. Hooke  Jeeves), также как и алгоритм Нелдера Мида, служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две… …   Википедия

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

  • Метод золотого сечения — метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации Содержание 1 Описание… …   Википедия

  • Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия …   Википедия

  • Метод роя частиц — (МРЧ)  метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Ши[1] [2] и изначально предназначался для имитации социального поведения.… …   Википедия

  • Метод потенциалов — является модификацией симплекс метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Содержание… …   Википедия

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

  • Метод Гаусса (оптимизация) — У этого термина существуют и другие значения, см. Метод Гаусса. Метод Гаусса[1] прямой метод решения задач многомерной оптимизации. Содержание 1 Описание 2 Примечания …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»