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

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

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

Версия 19:13, 17 декабря 2008

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

Содержание

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++, реализующей алгоритм.
@@ Строка 272: / Строка 281: @@
 == См. также ==
-[[Практикум ММП ВМК, 4й курс, осень 2008]]
+*[[Практикум ММП ВМК, 4й курс, осень 2008]]
+*[[Media:Nelder_Mead_Example1.zip‎| Код программы]]

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

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

Версия 19:13, 17 декабря 2008

Содержание

Введение

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

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

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

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

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

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

Заключение

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

См. также

Просмотры

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

Навигация

Поиск

Инструменты