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


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

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

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

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

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

Алгоритм

Пусть требуется найти безусловный минимум функции 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})$ .
«Сортировка». Из вершин симплекса выбираем три точки: $x h$ с наибольшим (из выбранных) значением функции $f h$ , $x g$ со следующим по величине значением $f g$ и $x l$ с наименьшим значением функции $f l$ . Целью дальнейших манипуляций будет уменьшение по крайней мере $f h$ .
Найдём центр тяжести всех точек, за исключением $x h$ : $x_c=\frac{1}{n}\sum\limits_{i\neq h} x_i$ . Вычислять $f c = f (x c)$ не обязательно.
«Отражение». Отразим точку $x h$ относительно $x c$ с коэффициентом $α$ (при $α = 1$ это будет центральная симметрия, в общем случае — гомотетия), получим точку $x r$ и вычислим в ней функцию: $f r = f (x r)$ . Координаты новой точки вычисляются по формуле:

$x r = (1 + α) x c - α x h$ .
Далее смотрим, насколько нам удалось уменьшить функцию, ищем место $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$ .
«Сжатие». Строим точку $x s = β x h + (1 - β) x c$ и вычисляем в ней значение $f s = f (x s)$ .
Если $f s < f h$ , то присваиваем точке $x h$ значение $x s$ и идём на шаг 9.
Если $f s > f h$ , то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением $x l$ :

$x_i \gets x_l + (x_i-x_l)/2$ , $i \ne l$ .
Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.

Источники

КУРС «Многомерная оптимизация». Лекция 10. Метод Нелдера-Мида на сайте ИНТУИТа. Подробное описание, есть иллюстрации.
Метод Нелдера-Мида. Краткий алгоритм.
Список ссылок на численные методы
J.A. Nelder and R. Mead, Computer Journal, 1965, vol 7, pp 308—313 [1] (текст не общедоступен)(англ.)

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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное

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

Метод Нелдера-Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу) Не путать с «симплекс методом» из линейного программирования методом оптимизации линейной системы с ограничениями.… … Википедия
Метод Нелдера — … Википедия
Метод Хука — Дживса (англ. Hooke Jeeves), также как и алгоритм Нелдера Мида, служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две… … Википедия
Метод Ньютона — Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном… … Википедия
Метод золотого сечения — метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации Содержание 1 Описание… … Википедия
Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия … Википедия
Метод роя частиц — (МРЧ) метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Ши[1] [2] и изначально предназначался для имитации социального поведения.… … Википедия
Метод потенциалов — является модификацией симплекс метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Содержание… … Википедия
Метод деформируемого многогранника — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу) Не путать с «симплекс методом» из линейного программирования методом оптимизации линейной системы с ограничениями.… … Википедия
Метод Гаусса (оптимизация) — У этого термина существуют и другие значения, см. Метод Гаусса. Метод Гаусса[1] прямой метод решения задач многомерной оптимизации. Содержание 1 Описание 2 Примечания … Википедия

Словари и энциклопедии на Академике

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