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

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

(Фрагмент методических указаний, подготовленных /3/)

Метод Нелдера-Мида (деформируемого многогранника) предназначен для приближенного решения безусловной n-мерной задачи нелинейного программирования вида: f ( x1 , x2 , ……. , xn ) ® min ( max ). Этот метод относится к группе методов 0-го порядка (прямого поиска), так как в нем не используются производные. Метод является развитием симплексного метода Спендли и других (не путать с симплекс-методом!).

Идея метода. В пространстве En тем или иным образом выбираются (n+1) пробный вектор, в каждом из которых может быть вычислено значение целевой функции. Худшая (в смысле значения целевой функции) вершина A отражается через центр тяжести остальных вершин многогранника, в результате строится новый многогранник, называемый отраженным, из оставшихся вершин и одной точки, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести (рис.6.1).

Алгоритм метода

1.  Предварительная операция.

Пусть x1 , x2, ……. , xn+1 - вершины начального многогранника. Выберем xl - “лучшую“ точку и xh - “худшую точку”, т. е.

xl : f( xl ) = min { f( x1), f( x2),……… , f( xn+1) }

xh : f( xh ) = max { f( x1), f( x2),……… , f( xn+1) }

Рассчитываем координаты центра тяжести всех вершин, исключая xh, т. е. точки xn+2 :

xj n+2 = , .

Затем вычисляем критерий останова. Если окажется, что

то вычисления прекращаются и в качестве оптимальной принимается точка, наилучшая из рассчитанных.

2. Операция отражения:

xn+3 = xn+2 + a( xn+2 - xh ) ,

где a > 0 - коэффициент отражения (как правило, a полагается равным 0).

3. Операция растяжения. Если f(xn+3) < f(xl), что означает выбор удачного направления поиска, то вектор xn+3 - xn+2 растягивается, т. е.

xn+4 = xn+2 + b( xn+3 - xn+2 ) ,

где b > 1 - коэффициент растяжения.

Если полученная точка xn+4 такова, что f(xn+4) < f(xl), то xh заменяется на xn+4 , если же f(xn+4) ³ f(xl), то xh заменяется на xn+3.

4. Операция сжатия. Если после отражения получилось f(xn+3) ≥ f(xi),

" i ¹ h, что означает неудачный выбор направления, то рассчитывается новая точка

xn+5 = xn+2 + g( xh - xn+2 ) ,

где gÎ( 0 , 1 ) - коэффициент сжатия. Затем точка xh заменяется на xn+5 .

5. Операция редукции .Если f(xn+3) > f(xh) ( это означает, что поиск идет вблизи оптимальной точки и текущий многогранник слишком велик для поиска), то пересчитываются координаты всех точек многогранника, кроме наилучшей (т. е. многогранник “сжимается” по направлению к «лучшей» точке):

xi = xl + 0,5( xi - xl ), " i ¹ l.

6.  Если после операции отражения не выполняются условия, предопределяющие операцию растяжения, сжатия или редукции, то xh заменяется на xn+3 (отраженную точку). Затем так же, как и после операций растяжения, сжатия и редукции, переходят на вычисления в соответствии с 1-ым пунктом алгоритма.

Рассмотрим решение численного примера.

Исходная задача:

f(x1 , x2) = 4(x1-5)2 + (x2-6)2 ® min ( xÎR2 ).

Начальные точки: x1 = , x2 = , x3 =.

Параметры алгоритма: a = 1, b = 2, g =, e = 10-6 (заданная точность).

Решение.

Шаг 1. Так как f(x1) = 45, f( x2) = 125, f( x3) = 65, то наилучшая точка xl = x1, а наихудшая xh = x2. Тогда центр тяжести: x4 =

Отражение: x5 = x4 + 1×( x4 - x2 ) = .

Так как f( x5) = 13 < f( x1), то выполняем операцию растяжения, т. е. вычисляем:

x6 = x4 + 2×( x5 - x4 ) = =, а так как f( x6) = 8 < f( x1), что означает, что операция растяжения завершилась удачно, то точку x2 заменяем на x6 и переходим на следующий шаг.

Шаг 2. x1 = , x2 = , x3 = , x4 =

f(x1) = 45, f( x2) = 8, f( x3) = 65, f(x4) = 10,25. Следовательно:

x2 - ” лучшая точка ”, x3 -” худшая точка ”.

Критерий останова:

>>e =10-6 .

Очевидно, что заданная точность не достигнута. Опять выполняем операцию отражения: x5 = , f( x5) = 4 < f( x2).

Выполняем операцию растяжения:

x5 = , так как f( x6) = 42,25 > f( x2), то точку x3 заменяем на x5 и переходим на следующий шаг.

В табл.6.1 сведены результаты расчетов по первым четырем итерациям для данного примера, на рис.6.2. на фоне линий уровня исследуемой тестовой функции показана траектория сходимости, построенная на основании проведенных расчетов.

Таблица 6.1

Решение примера по методу Нелдера-Мида

Номер шага	x1	f(x1)	x2	f(x2)	x3	f(x3)	Центр тяжести	Значение критерия останова	Отражение	Растяжение или сжатие	Примечания
x4	f(x4)	x5	f(x5)	x6	f(x5)
1		45		125		65		52	74,5		13		8	Растяжение
x6(1)®®x2(2)
2		45		8		65		10,25	64,9		4		42,25	Отражение
x5(2)® x3(3)
3		45		8		4		5	40,1		101	-	-	Редукция
-
4		6,25		5		4		4	2,3		36,25	-	-	Редукция
-

Рис. 6.2. Графическая иллюстрация процесса сходимости при решении примера методом Нелдера-Мида

 

Литература

1.  и др. Оптимизация в технике: В 2-х кн.-M.: Мир, 1986.

2.  Прикладное нелинейное программирование. М.: Мир, 1983г.

3.  Оптимизация в САПР. Составитель , Новосибирск, НГТУ, 1992г. № № 000.