Метод Нелдера-Мида
Материал из MachineLearning.
- Не путать с «симплекс-методом» из линейного программирования — методом оптимизации линейной системы с ограничениями.
Содержание |
Введение
Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Выпуклая оболочка множества -й равноудаленной точки в -мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. В двухмерном пространстве регулярным симплексом является правильный треугольник, а в трехмерном - правильный тетраэдр. Идея метода состоит в сравнении значений функции в вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных при .
Главными особенностями алгоритма можно назвать следующие:
- Метод Нелдера-Мида не накладывает ограничений на гладкость функции
- Данный метод явялется эффективным при низкой скорости вычисления минимизируемой функции. Как правило, на каждой итерации происходит вычисление значения функции не более чем в 3 точках.
- Отсутствие теории сходимости. АЛгоритм может расходиться даже на гладких функциях.
Постановка математической задачи
Задачей оптимизации называется задача поиска экстремума функции, заданной на некотором множетсве.
- .
Как правило, под задачей оптимизации также подразумевается поиск элемента , при котором целевая функция достигает экстремума.
Для того, чтобы корректно поставить задачу оптимизации необходимо задать:
- Допустимое множество
- Целевую функцию
- Критерий поиска (max или min)
Тогда решить задачу означает одно из:
- Показать что
- Показать, что целевая функция не ограничена.
- Найти
- Если не существует , то найти
Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.
Рассматриваемая задача
Метод Нелдера-Мида, также известный как метод деформируемого многогранника, — метод безусловной оптимизации вещественной функции от нескольких переменных. Иными словами на допустимое множество накладываются следующие ограничения:
- .
Кроме того, одним из главных преимуществ данного метода является то, что в нем не используется градиента целевой функции, что позволяет применять его к негладким функциям. Метод Нелдера-Мида использует понятие симплекса -мерного пространства'.
Множество называется выпуклым, если .
Выпуклой оболочкой множества называется наименьшее выпуклое множество такое, что
Симплексом или -симплексом называется выпуклая оболочка множества точек.
Например:
1-симплексом является отрезок
2-симплексом является треугольник
3-симплексом является тетраэдр.
Изложение метода
Параметрами метода являются:
- коэффициент отражения , обычно выбирается равным 1.
- коэффициент сжатия , обычно выбирается равным 0.5.
- коэффициент растяжения , обычно выбирается равным 2.
Инициализация.Произвольным образом выбирается точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .
- 1. Сортировка. Из вершин симплекса выбираем три точки: с наибольшим (из выбранных) значением функции , со следующим по величине значением и с наименьшим значением функции . Целью дальнейших манипуляций будет уменьшение по крайней мере .
- 2. Найдём центр тяжести всех точек, за исключением . Вычислять не обязательно.
- 3. Отражение. Отразим точку относительно с коэффициентом (при это будет центральная симметрия, в общем случае — гомотетия), получим точку и вычислим в ней функцию: . Координаты новой точки вычисляются по формуле
- 4. Далее сравниваем значение со значениями :
- 4а. Если , то производим растяжение. Новая точка и значение функции .
- Если , то заменяем точку на и заканчиваем итерацию (на шаг 8).
- Если , то заменяем точку на и заканчиваем итерацию (на шаг 8).
- 4b. Если , то заменяем точку на и переходим на шаг 8.
- 4с. Если , то меняем обозначения (и соответствующие значения функции) местами и переходим на шаг 5.
- 4d. Если , то переходим на шаг 5.
- 5. Сжатие. Строим точку и вычисляем в ней значение .
- 6. Если , то заменяем точку на и переходим на шаг 8.
- 7. Если , то производим сжатие симплекса — гомотетию к точке с наименьшим значением : для всех требуемых точек .
- 8. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 1.
Анализ метода
Изучение сходимости алгоритма Нелдера-Мида является трудной математической задачей. Известные результаты о сходимости симплекс-методов основаны на следующих предположениях:
- Симплекс не должен вырождаться при итерациях алгоритма
- На гладкость функции накладываются некоторые условия
В общем случае для метода Нелдера-Мида не выполняются сразу оба эти предположения, а следовательно, об условиях сходимости известно весьма мало. МакКиннон в 1998 году описал семейство строго выпуклых функций и класс начальных симплексов в двухмерном пространстве, для которых все вершины рабочего симплекса сходятся не к оптимальной точке. В 1998 году Лагариас опубликовал статью, в которой он исследовал сходимость метода в одно- и двухмерном пространствах для некоторых строго выпуклых функций с ограниченными поверхностями уровня.
Алгоритм Нелдера-Мида дает сильное уменьшение значение функции уже при первых нескольких итерациях и быстро достигает необходимой точности. Как правило, алгоритм производит одно или два вычисления функции на каждой итерации, если не учитывать сжатие, которое редко используется на практике. Это крайне важно в тех ситуациях, когда вычисление значений функции очень дорого или же требует много времени. Для подобных задач алгоритм Нелдера-Мида гораздо эффективнее многих других методов, требующих вычисления не менее значений функции на каждой итерации.
Главными преимуществами алгоритма являются его простота и эффективность.
С другой стороны, в силу отсутствия теории сходимости, на практике метод может приводить к неверному ответу даже для гладких функций. Также возможна ситуация, когда рабочий симплекс находится далеко от оптимальной точки, а алгоритм производит большое число итерации, при этом мало изменяя значения функции. Эвристический метод решения этой проблемы заключается в запуске алгоритма несколько раз и ограничении числа итераций.
Числовой эксперимент
В качестве числового эксперимента метод Нелдера-Мида был применен для вычисления минимума функции Розенброка:
для которой и . В качестве начального прибилжения был взят симплекс .
Ниже приведена таблица промежуточных результатов после каждых 10 итераций алгоритма.
Число итераций | Координаты первой точки симплекса | Координаты второй точки симплекса | Координаты третьей точки симплекса | ||
---|---|---|---|---|---|
10 | x=2.78; y=7.55; | x=2.39; y=6.39; | x=1.73; y=6.87; | 6.725 | 1479.400 |
20 | x=2.63; y=6.96; | x=2.70; y=7.29; | x=2.64; y=6.88; | 2.769 | 3.225 |
30 | x=2.24; y=4.94; | x=2.35; y=5.50; | x=2.42; y=5.86; | 1.823 | 2.017 |
40 | x=1.90; y=3.58; | x=1.83; y=3.38; | x=1.97; y=3.89; | 0.821 | 0.996 |
50 | x=1.51; y=2.28; | x=1.53; y=2.36; | x=1.57; y=2.47; | 0.273 | 0.327 |
60 | x=1.20; y=1.42; | x=1.23; y=1.51; | x=1.27; y=1.61; | 0.050 | 0.079 |
70 | x=0.99; y=0.97; | x=1.01; y=1.02; | x=0.96; y=0.93; | 0.000 | 0.003 |
Итоговое количество итераций 79. Вычисленный минимум функционала равен .
Рекомендации программисту
Метод Нелдера-Мида прост в реализации, в качестве параметров алгоритма как правило используются следующие:
, , .
В качестве начального, как правило, используется произвольный симплекс. Также возможно многократное вычисление минимума при различных случайных начальных симплексах.
Ниже приведен пример функции на языке C++, реализующей алгоритм.
double NMA(Simplex* smpl, double alpha=1.0, double beta=0.5, double gamma=2.0) { double f[N_DIM + 1]; double f_h, f_g, f_l, f_r, f_e, f_s, tempD; Vertex x_h, x_g, x_l, x_r, x_e, x_s, x_c, tempV; int i; bool flag; for (i=0; i<=N_DIM;i++) f[i]=Func(smpl->v[i]); // Вычисление значений функции на начальном симплексе while (!QuitCase(smpl)) // Проверка на условие выхода { // Шаг 1. Сортировка Sort(smpl,f); x_h = smpl->v[N_DIM]; f_h = f[N_DIM]; x_g = smpl->v[N_DIM - 1]; f_g = f[N_DIM - 1]; x_l = smpl->v[0]; f_l = f[0]; // Шаг 2. Вычисление центра тяжести симплекса x_c.x=x_c.y=0; for (i=0; i<N_DIM; i++) x_c += smpl->v[i]; x_c = x_c/N_DIM; // 3Шаг . Отражение x_r = x_c * (1+alpha) - x_h * alpha; f_r = Func(x_r); // Шаг 4. if (f_r <= f_l) { // Шаг 4a. x_e = x_c * (1-gamma) + x_r * gamma; f_e = Func(x_e); if (f_e < f_l) { smpl->v[N_DIM] = x_e; f[N_DIM] = f_e; } else { smpl->v[N_DIM] = x_r; f[N_DIM] = f_r; } } if ((f_l < f_r) && (f_r <= f_g)) { // Шаг 4.b smpl->v[N_DIM] = x_r; f[N_DIM] = f_r; } flag = false; if ((f_h >= f_r) && (f_r > f_g)) { // Шаг 4c. flag = true; tempD=f_h; tempV=x_h; smpl->v[N_DIM] = x_r; f[N_DIM] = f_r; x_r=tempV; f_r=tempD; } // Шаг 4d. if (f_r > f_h) flag = true; if (flag) { // Шаг 5. Сжатие x_s = x_h * beta + x_c * (1 - beta); f_s = Func(x_s); if (f_s < f_h) { // 6. tempD=f_h; tempV=x_h; smpl->v[N_DIM] = x_s; f[N_DIM] = f_s; x_s=tempV; f_s=tempD; } else { // Шаг 7. Глобальное сжатие for (i=0; i<=N_DIM; i++) smpl->v[i]=x_l + (smpl->v[i] - x_l)/2; } } } return f_l; }
Заключение
Симплекс-метод Нелдера-Мида является очень эффективным алгоритмом поиска экстремума функции многих переменных, не накладывающим ограничений на гладкость функции. На каждой итерации алгоритма производится как правило одно-два вычисления значений функции, что чрезвычайно эффективно если эти вычисления очень медленны. Кроме того, алгоритма очень прост в реализации. Главным же его недостатком является отсутствие теории сходимости и наличие примеров, когда метод расходится даже на гладких функциях.
Список литературы
- Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
- http://www.scholarpedia.org/article/Nelder-Mead_algorithm