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

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

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

Содержание

Введение

Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта. Выпуклая оболочка множества (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}

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

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

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

  1. Показать что \mathbb{X} = \emptyset
  2. Показать, что целевая функция f(x) не ограничена.
  3. Найти x_{*}
  4. Если не существует 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}.

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

Метод Нелдера-Мида прост в реализации, в качестве параметров алгоритма как правило используются следующие:

\alpha = 1, \beta = 0.5, \gamma = 2.

В качестве начального, как правило, используется произвольный симплекс. Также возможно многократное вычисление минимума при различных случайных начальных симплексах.

Ниже приведен пример функции на языке 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;
}

Заключение

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

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

См. также

Источник — «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»
Личные инструменты