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

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


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

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

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

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

Алгоритм

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

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

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

Подготовка. Вначале выбирается n + 1 точка x_i = \left(x^{(1)}_i,x^{(2)}_i,\ldots,x^{(n)}_i\right), образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: f_1=f(x_1), f_2=f(x_2),\ldots, f_{n+1}=f(x_{n+1}).

Дальнейший план действий:

1. Сортировка. Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.
2. Найдём центр тяжести всех точек, за исключением xh: x_c=\frac{1}{n}\sum\limits_{i\neq h} x_i. Вычислять fc = f(xc) не обязательно.
3. Отражение. Отразим точку xh относительно xc с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку xr и вычислим в ней функцию: fr = f(xr). Координаты новой точки вычисляются по формуле:
xr = (1 + α)xc − αxh
4. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh,fg,fl:
4а Если fr < fl, то направление выбрано удачное и можно попробовать увеличить шаг — производим растяжение. Новая точка xe = (1 − γ)xc + γxr и значение функции fe = f(xe).
  • Если fe < fl, то можно расширить симплекс до этой точки: заменяем точку xh на xe и заканчиваем итерацию (на шаг 8).
    Если fe > fl, то переместились слишком далеко: в набор берём xr (опять вместо xh) и заканчиваем итерацию (на шаг 8).
4b Если fl < fr < fg, то выбор точки уже неплохой (новая лучше двух прежних). Заменяем точку xh на xr и переходим на шаг 8.
4с Если fh > fr > fg, то меняем обозначения xr,xh (и соответствующие значения функции) местами и идём на шаг 5.
4d Если fr > fh, то просто идём на следующий шаг 5.

В результате (возможно, после переобозначения) fr > fh > fg > fl.

5. Сжатие. Строим точку xs = βxh + (1 − β)xc и вычисляем в ней значение fs.
6 Если fs < fh, то заменяем точку xh на xs и идём на шаг 8.
7 Если fs > fh, то первоначальные точки оказались самыми маленькими. Делаем глобальное сжатие симплекса — гомотетию к точке с наименьшим значением x0:
x_i \to x_0 + (x_i-x_0)/2 для всех требуемых точек xi.
8 Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 1.

См. также

Источники


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


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

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

  • Метод Нелдера — …   Википедия

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

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

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

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

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

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

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

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


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

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