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

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

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

Содержание

1 Введение
- 1.1 Постановка математической задачи
- 1.2 Рассматриваемая задача
2 Изложение метода
3 Анализ метода
4 Числовой эксперимент
5 Рекомендации программисту
6 Заключение
7 Список литературы
8 См. также

Введение

Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Выпуклая оболочка множества $(n+1)$ -й равноудаленной точки в $n$ -мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. В двухмерном пространстве регулярным симплексом является правильный треугольник, а в трехмерном - правильный тетраэдр. Идея метода состоит в сравнении значений функции в $(n+1)$ вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных при $n \le 6$ .

Главными особенностями алгоритма можно назвать следующие:

Метод Нелдера-Мида не накладывает ограничений на гладкость функции
Данный метод явялется эффективным при низкой скорости вычисления минимизируемой функции. Как правило, на каждой итерации происходит вычисление значения функции не более чем в 3 точках.
Отсутствие теории сходимости. АЛгоритм может расходиться даже на гладких функциях.

Постановка математической задачи

Задачей оптимизации называется задача поиска экстремума функции, заданной на некотором множетсве.

$f: \: \mathbb{X} \rightarrow \mathbb{R}$

( 1.1)

$f(x) \rightarrow min, \: x \in \mathbb{X} \subseteq \mathbb{G}$ .

Как правило, под задачей оптимизации также подразумевается поиск элемента $x$ , при котором целевая функция $f(x)$ достигает экстремума.

( 1.2)

$x_{*}=arg \mathrm{}\min_{x \in \mathbb{X}} {f(x)}, \: \mathbb{X} \subseteq \mathbb{G}$

Для того, чтобы корректно поставить задачу оптимизации необходимо задать:

Допустимое множество $\mathbb{X}$
Целевую функцию $f: \: \mathbb{X} \rightarrow \mathbb{R}$
Критерий поиска (max или min)

Тогда решить задачу $f(x) \rightarrow \mathrm{}\min_{x \in \mathbb{X}}$ означает одно из:

Показать что $\mathbb{X} = \emptyset$
Показать, что целевая функция $f(x)$ не ограничена.
Найти $x_{*}$
Если не существует $x_{*}$ , то найти $\mathrm{}\inf_{x \in \mathbb{X}} {f(x)}$

Если допустимое множество $\mathbb{X}=\mathbb{G}$ , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

Рассматриваемая задача

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

$\mathbb{X}=\mathbb{G}=\mathbb{R}^n$ .

Кроме того, одним из главных преимуществ данного метода является то, что в нем не используется градиента целевой функции, что позволяет применять его к негладким функциям. Метод Нелдера-Мида использует понятие симплекса $n$ -мерного пространства'.

Множество $C$ называется выпуклым, если $\forall a,b \in C \: [a,b] \subseteq C$ .

Выпуклой оболочкой множества $X$ называется наименьшее выпуклое множество $C$ такое, что $X \subseteq C$

Симплексом или $n$ -симплексом называется выпуклая оболочка множества $(n+1)$ точек.

Например:

1-симплексом является отрезок

2-симплексом является треугольник

3-симплексом является тетраэдр.

Изложение метода

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

коэффициент отражения $\alpha >0$ , обычно выбирается равным 1.
коэффициент сжатия $\beta >0$ , обычно выбирается равным 0.5.
коэффициент растяжения $\gamma >0$ , обычно выбирается равным 2.

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

1. Сортировка. Из вершин симплекса выбираем три точки: $x_h$ с наибольшим (из выбранных) значением функции $f_h$ , $x_g$ со следующим по величине значением $f_g$ и $x_l$ с наименьшим значением функции $f_l$ . Целью дальнейших манипуляций будет уменьшение по крайней мере $f_h$ .

2. Найдём центр тяжести всех точек, за исключением $x_h: x_c=\frac{1}{n} \sum_{i\neq h} x_i$ . Вычислять $f_c=f(x_c)$ не обязательно.

3. Отражение. Отразим точку $x_h$ относительно $x_c$ с коэффициентом $\alpha$ (при $\alpha=1$ это будет центральная симметрия, в общем случае — гомотетия), получим точку $x_r$ и вычислим в ней функцию: $f_r=f(x_r)$ . Координаты новой точки вычисляются по формуле $x_r = (1+\alpha)x_c - \alpha x_h$

4. Далее сравниваем значение $f_r$ со значениями $f_h, f_g, f_l$ :

4а. Если $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$ и заканчиваем итерацию (на шаг 8).

Если $f_e>f_l$ , то заменяем точку $x_h$ на $x_r$ и заканчиваем итерацию (на шаг 8).

4b. Если $f_l < f_r < f_g$ , то заменяем точку $x_h$ на $x_r$ и переходим на шаг 8.

4с. Если $f_h > f_r > f_g$ , то меняем обозначения $x_r, x_h$ (и соответствующие значения функции) местами и переходим на шаг 5.

4d. Если $f_r > f_h$ , то переходим на шаг 5.

5. Сжатие. Строим точку $x_s = \beta x_h + (1-\beta) x_c$ и вычисляем в ней значение $f_s$ .

6. Если $f_s < f_h$ , то заменяем точку $x_h$ на $x_s$ и переходим на шаг 8.

7. Если $f_s > f_h$ , то производим сжатие симплекса — гомотетию к точке с наименьшим значением $x_0$ : $x_i \to x_0 + (x_i-x_0)/2$ для всех требуемых точек $x_i$ .

8. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 1.

Анализ метода

Изучение сходимости алгоритма Нелдера-Мида является трудной математической задачей. Известные результаты о сходимости симплекс-методов основаны на следующих предположениях:

Симплекс не должен вырождаться при итерациях алгоритма

На гладкость функции накладываются некоторые условия

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

Алгоритм Нелдера-Мида дает сильное уменьшение значение функции уже при первых нескольких итерациях и быстро достигает необходимой точности. Как правило, алгоритм производит одно или два вычисления функции на каждой итерации, если не учитывать сжатие, которое редко используется на практике. Это крайне важно в тех ситуациях, когда вычисление значений функции очень дорого или же требует много времени. Для подобных задач алгоритм Нелдера-Мида гораздо эффективнее многих других методов, требующих вычисления не менее $n$ значений функции на каждой итерации.

Главными преимуществами алгоритма являются его простота и эффективность.

С другой стороны, в силу отсутствия теории сходимости, на практике метод может приводить к неверному ответу даже для гладких функций. Также возможна ситуация, когда рабочий симплекс находится далеко от оптимальной точки, а алгоритм производит большое число итерации, при этом мало изменяя значения функции. Эвристический метод решения этой проблемы заключается в запуске алгоритма несколько раз и ограничении числа итераций.

Числовой эксперимент

В качестве числового эксперимента метод Нелдера-Мида был применен для вычисления минимума функции Розенброка:

$f(x_1,x_2)=100(x_2-x_1^2)^2+(1-x_1)^2;$

для которой $x_*=(1;1)$ и $f_*=0$ . В качестве начального прибилжения был взят симплекс $\{ (10;9),(10;-2),(21;1) \}$ .

Ниже приведена таблица промежуточных результатов после каждых 10 итераций алгоритма.

Число итераций	Координаты первой точки симплекса	Координаты второй точки симплекса	Координаты третьей точки симплекса	$f_l$	$f_h$
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. Вычисленный минимум функционала равен $0.6 * 10^{-5}$ .

Заключение

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

Список литературы

Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
http://www.scholarpedia.org/article/Nelder-Mead_algorithm

См. также

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D0%B5%D0%BB%D0%B4%D0%B5%D1%80%D0%B0-%D0%9C%D0%B8%D0%B4%D0%B0»

Категория: Численные методы безусловной оптимизации

@@ Строка 1: / Строка 1: @@
+: ''Не путать с «симплекс-методом» из линейного программирования — методом оптимизации линейной системы с ограничениями.''
 == Введение ==
 Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Выпуклая оболочка множества <tex>(n+1)</tex>-й равноудаленной точки в <tex>n</tex>-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. В двухмерном пространстве регулярным симплексом является правильный треугольник, а в трехмерном - правильный тетраэдр. Идея метода состоит в сравнении значений функции в <tex>(n+1)</tex> вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных при <tex>n \le 6</tex>.
+Главными особенностями алгоритма можно назвать следующие:
+* Метод Нелдера-Мида не накладывает ограничений на гладкость функции
+* Данный метод явялется эффективным при низкой скорости вычисления минимизируемой функции. Как правило, на каждой итерации происходит вычисление значения функции не более чем в 3 точках.
+* Отсутствие теории сходимости. АЛгоритм может расходиться даже на гладких функциях.
 === Постановка математической задачи ===
 Задачей оптимизации называется задача поиска экстремума функции, заданной на некотором множетсве.
@@ Строка 167: / Строка 174: @@
 |}
-Итоговое количество итераций 79. Точность составила <tex>0.6 * 10^{-5}</tex>.
+Итоговое количество итераций 79. Вычисленный минимум функционала равен <tex>0.6 * 10^{-5}</tex>.
 == Рекомендации программисту ==
@@ Строка 173: / Строка 180: @@
 <tex>\alpha = 1</tex>, <tex>\beta = 0.5</tex>, <tex>\gamma = 2</tex>.
+В качестве начального, как правило, используется произвольный симплекс. Также возможно многократное вычисление минимума при различных случайных начальных симплексах.
 Ниже приведен пример функции на языке C++, реализующей алгоритм.
@@ Строка 253: / Строка 262: @@
 				for (i=0; i<=N_DIM; i++)
 					smpl->v[i]=x_l + (smpl->v[i] - x_l)/2;
+//возможно в этом цикле ошибка, так как минимальным будет вектор не x_l а x_h. проверяйте.
 			}
 		}
@@ Строка 272: / Строка 282: @@
 == См. также ==
-[[Практикум ММП ВМК, 4й курс, осень 2008]]
+*[[Практикум ММП ВМК, 4й курс, осень 2008]]
+*[[Media:Nelder_Mead_Example1.zip‎| Код программы]]
+[[Категория:Численные методы безусловной оптимизации|Нелдера-Мида]]

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

Материал из MachineLearning.

Текущая версия

Содержание

Введение

Постановка математической задачи

Рассматриваемая задача

Изложение метода

Анализ метода

Числовой эксперимент

Рекомендации программисту

Заключение

Список литературы

См. также

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты