Метод Нелдера — Мида | это... Что такое Метод Нелдера — Мида? (original) (raw)

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

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

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

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

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

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

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

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

Алгоритм

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

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

  1. «Подготовка». Вначале выбирается 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}).
  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 с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия), получим точку x r и вычислим в ней функцию: f r = f(x r). Координаты новой точки вычисляются по формуле:
    x r = (1 + α)x c − α_x_ h.
  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_, то можно расширить симплекс до этой точки: присваиваем точке _x_ _l_ значение _x_ _e_ и заканчиваем итерацию (на шаг 9).
    Если _f_ _e_ > f l, то переместились слишком далеко: присваиваем точке x l значение x r и заканчиваем итерацию (на шаг 9).
    Если f l < _f_ _r_ < _f_ _g_, то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке _x_ _h_ значение _x_ _r_ и переходим на шаг 9.
    Если _f_ _h_ > f r > f g, то меняем местами значения x r и x 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:
    x_i \gets x_l + (x_i-x_l)/2, i \ne l.
  9. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.

Источники

Методы оптимизации
Одномерные Метод золотого сечения • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод Фибоначчи • Метод троичного поиска
Прямые методы Метод Гаусса • Метод Нелдера — Мида • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса
Первого порядка Градиентный спуск • Метод покоординатного спуска • Метод сопряжённых градиентов
Второго порядка Метод Ньютона • Метод Ньютона-Рафсона
Стохастические Дифференциальная эволюция • Имитация отжига
Методы линейного программирования Метод эллипсоидов • Симплекс-метод • Метод потенциалов

Wikimedia Foundation.2010.

Полезное

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