МО-Лекции

2.4.СИМПЛЕКСНЫЙ МЕТОД НЕЛДЕРА–МИДА ИЛИ ПОИСК ПО ДЕФОРМИРУЕМОМУ

МНОГОГРАННИКУ

Вданном методе [2] в процессе поиска осуществляется работа с регулярными симплексами. Регулярные многогранники в пространстве

En называются симплексами. Для n	2 регулярный симплекс пред-
ставляет собой равносторонний треугольник, при		n	3	тетраэдр
и т. д.
Координаты вершин регулярного	симплекса	в	n -мерном про-

странстве могут быть определены следующей матрицей D , в которой столбцы представляют собой вершины симплекса, пронумерованные

от 1 до ( n 1 ), а строки – координаты вершин, i

1, n . Матрица имеет

размерность n (n

1) :

0

d1

d2 ....

d2

0

d2

d1 ....

d2

D

0

d2

d2 ....

d2

,

.... .... .... .... ....

0

d2

d2 ....

d1

n (n 1)

где

t

t

d1

( n 1 n 1) ; d2

;

n

2

n

2( n

1 1)

t – расстояние между вершинами.

В самом простом виде симплексный алгоритм заключается в сле-

дующем. Строится	регулярный симплекс. Из вершины, в которой
f (x ) максимальна	(точка 1, рис. 2.4), проводится проектирующая

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

Продолжение этой процедуры, в которой каждый раз исключается вершина, где целевая функция максимальна, а также использование правил уменьшения размера симплекса и предотвращения циклическо-

20

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

Представление об идее алгоритма дает рис. 2.4.

Рис. 2.4. Траектория спуска в простейшем симплексном алгоритме

В симплексном алгоритме Нелдера и Мида минимизация функций

n

переменных

осуществляется

с использованием деформируемого

многогранника.

Будем

рассматривать

k -ю

итерацию

алгоритма.

Пусть

x k

xk

, xk

,..., xk

,

i 1,..., (n

1) , является i -й вершиной в

En на

i

i1

i2

in

k -м этапе поиска, k

0,1, 2,... , и пусть значения целевой функции в

этой вершине

f x k

.

Отметим вершины с минимальным и макси-

i

мальным значениями. И обозначим их следующим образом:

f (x k )

max

f (x k ),..., f (x k

1

)

;

h

1

n

f (x k )

min

f (x k ),..., f (x k

1

) .

l

1

n

21

Многогранник в En состоит из			n 1 вершин x k ,	x k	,..., x k	1	. Обо-
			1	2	n
значим через x k	2	центр тяжести вершин без точки		x k	с максималь-
n				h

ным значением функции. Координаты этого центра вычисляются по формуле

		1	n 1
xk	2, j		xk	xk	, j 1,..., n .	(2)
n		n	i, j	h, j
			i 1

Начальный многогранник обычно выбирается в виде регулярного симплекса (с вершиной в начале координат). Можно начало координат

поместить в центр тяжести. Процедура отыскания вершин в En , в которых f (x ) имеет лучшее значение, состоит из следующих операций:

1)отражения; 2) растяжения; 3) сжатия; 4) редукции.

1.Отражение. Отражение представляет собой проектирование точ-

ки x k

через центр тяжести

x k

2

в соответствии со следующим соот-

h

n

ношением

x k

x k

2

(x k

2

x k ) ,

(3)

n 3

n

n

h

где

0 – коэффициент отражения.

Вычисляем значение функции в найденной точке

f x k

3

. Если

n

значение функции в данной точке

f (x k

)

f (x k ) , то переходим к

n 3

h

четвертому пункту алгоритма – операции редукции.

Если f

x k

3

f x k

f

x k

3

f

x k

,

то выполняем операцию

n

h

n

l

растяжения.

В противном случае, если

f

x k

3

f

x k

f x k

3

f

x k , то

n

h

n

l

выполняется операция сжатия.

2. Растяжение. Эта операция

заключается в следующем. Если

f x k

f x k

(меньше минимального значения на

k -м этапе), то

n 3

l

вектор

x k

3

x k

2

растягивается в соответствии с соотношением

n

n

x k

x k

2

x k

3

x k

,

(4)

n 4

n

n

n 2

где

0 – коэффициент растяжения.

22

Если

f (x k

4

)

f (x k ) ,

то

x k

заменяется на

x k

4

и процедура про-

n

l

l

n

должается с операции отражения при

k

k

1 . В противном случае

x k

заменяется на x k

, и также переходим к операции отражения.

l

n 3

3.

Сжатие.

Если

f

x k

3

f

x k

для

i

i

h ,

то вектор

n

i

x k

x k

2

сжимается в соответствии с формулой

h

n

x k

x k

x k

x k

,

n 5

n 2

h

n 2

где 0

1 – коэффициент сжатия. После этого точка x k

заменяется

h

на x k

5

, и переходим к операции отражения с

k

k

1 . Заново ищет-

n

ся x k

1 .

h

4. Редукция. Если

f (x k

)

f (x k ) ,

то все векторы

x k

x k , где

n 3

h

i

l

i

1, (n

1)

, уменьшаются в два раза с отсчетом от точки x k по фор-

l

муле

x k

x k

0.5 x k

x k

, i

1, (n 1)

i

l

i

l

и осуществляется переход к операции отражения (на начало алгоритма с k k 1 ).

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

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

1		n 1					1/2
			f (x k )	f (x k			2
						)
					2		.
	n 1 i 1		i	n
Выбор коэффициентов , ,				обычно осуществляется эмпириче-

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

другой формы. Чаще всего рекомендуют

1 , 0.4

0.6 , 2

3 .

23

2.5. МЕТОД ПАУЭЛЛА И СОПРЯЖЕННЫЕ НАПРАВЛЕНИЯ

2.5.1. ОБОСНОВАНИЕ ПРИМЕНЕНИЯ СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ В АЛГОРИТМАХ ОПТИМИЗАЦИИ

Метод Пауэлла [2] относится к прямым методам (методам нулевого порядка). Этим методом наиболее эффективно осуществляется минимизация функций, близких к квадратичным. На каждой итерации алгоритма поиск осуществляется вдоль системы сопряженных направлений.

Два направления поиска S i , S j называются сопряженными, если

SiT H S j 0, i j ,

S iT H S i 0 , i j ,

где H – положительно определенная квадратная матрица.

В методе Пауэлла H 2 f (x k ) – матрица вторых частных произ-

водных. Идеи метода Пауэлла относятся к квадратичной функции f (x ) .

Основная идея заключается в следующем. Если на каждом этапе поиска определяется минимум квадратичной функции f (x ) вдоль ка-

ждого из p ( p n) -сопряженных направлений и если затем в каждом

из направлений делается шаг до минимальной точки, то полное перемещение от начала до шага с номером p сопряжено ко всем подна-

правлениям поиска.

Применение сопряженных направлений лежит в основе ряда алгоритмов.

Пусть f (x ) – квадратичная функция и процесс минимизации начи-

	нается в точке x 0	с начальным направлением						1 . Для удобства возь-
						S
				1 T			1
	мем этот вектор	единичным, т. е. S			S				1. Тогда вектор

24

x1 x 0

1

1

и длина шага

1

определяется из условия минималь-

S

ности функции в данном направлении т. е.

1

x 0

1 .

arg min f

S

Для квадратичной функции

df (x 0

1)

S

1

1

1

T f (x 0 ) S

(S

)T

2 f (x 0 ) S

0 ,

(5)

d

и, таким образом, оптимальное значение

на первом шаге определя-

ется в соответствии с соотношением

T f (x 0 )

1

T f (x 0 )

1

1

S

S

,

(6)

1

T 2

0

1

1

T

1

(S

)

f (x

)S

(S

)

H S

где H

2 f (x k ) .

Из точки

1

процесс минимизации должен осуществляться в дру-

x

гом сопряженном направлении

2 , при этом в силу сопряженности

S

2

T

1

0 .

S

H S

Отметим, что квадратичная функция может быть представлена в виде

				T		1		T	Hx ,
	f (x) a b				x		x
						2
	где положительно определенная матрица H								2 f (x ) .

В общем случае система n линейно независимых направлений по-

иска S1, S 2 ,..., S n называется сопряженной по отношению к некоторой положительно определенной матрице H , если

			i		T			j		, 1 i j n .
	(S			)		H S			0

25

Так как сопряженные направления линейно независимы, то любой

вектор в пространстве En можно выразить через систему S1, S 2 ,..., S n следующим образом:

n

v j

j

V

S

,

j 1

где

j

T

v j

S

HV

.

(7)

j

T

j

S

H S

Известная формула, примем ее на веру.

Для некоторой матрицы

H всегда существует,

по крайней мере,

одна система из n взаимно сопряженных направлений, так как сами собственные векторы матрицы H представляют собой такую систему.

Отметим, что для квадратичной функции справедливо следующее соотношение, которое потребуется в дальнейшем:

n

j

j T

H 1

S

S

.

(8)

T

j 1

j

H

j

S

S

Чтобы убедиться

в

его справедливости, рассмотрим

матрицу

n

j

S

j (

S

j ) . Умножение ее справа на H

S

k дает

j 1

n

j (

j ) H

k

k (

k ) H

k

k ,

j

S

S

S

k

S

S

S

S

j 1

1

если положить

k

H

k .

k

S

S

Вообще говоря, справедливо общее правило, заключающееся в том,

что если используются сопряженные направления для поиска минимума квадратичной функции f (x ) , то эта функция может быть мини-

26

мизирована за n шагов, по одному в каждом из сопряженных направ-

лений. Более того, порядок использования сопряженных направлений несуществен.

Покажем, что это действительно так. Пусть

f x – квадратичная

функция и

T

1

T

Hx ,

f

x

a

b

x

x

2

при этом

f x

b

Hx .

В точке минимума

f

x

0 ,

и эта точка

H 1

.

x

b

Заметим, что

T f x k

k

k T

f x k .

S

S

Так как

x1

x 0

1

1 ,

(9)

S

где 1 определяется в соответствии с соотношением (6):

T f x 0

1

T f x 0

1

1

S

S

,

1 T

2 f x 0

1

1 T

H

1

S

S

S

S

а затем минимум находится в следующем сопряженном направлении по аналогичным формулам

x 2	x1	2			2
			S
и так далее, то на n -м шаге имеем
		n
x n	x 0		i	S		i .	(10)
		i 1

27

На

каждом шаге минимизируем

одномерную

функцию

f x i 1

i

i

в направлении

i ,

чтобы получить i . На основании

S

S

(6) это приводит к следующему выражению

i

T

f x i

1

n

S

i .

x n

x 0

S

(11)

i T

i

i 1

S

H S

Кроме того,

i T

f xi 1

i T

Hxi 1

i T

H x 0

i 1 k

k

S

S

b

S

S

b

k 1

и получаем

i T

f x i 1

i T

Hx 0

,

S

S

b

i

T

k

i

k , вследствие сопряженности

i

k

так как все

S

H S

0 ,

S

и S

.

Таким образом,

n

i

T

Hx 0

i

.

x n

x 0

S

b

S

(12)

T

i

1

i

i

S

H S

Выразим векторы x 0

и H 1

через систему сопряженных векторов

b

i следующим образом (по аналогии с (7)):

S

n

i T Hx 0

i

x 0

S

S

,

i

1

i T

i

S

H S

i

T

1

i

i T

i

n

S

H H

b S

n

S

bS

H 1b

.

i 1

i T H

i

i 1

i T

H

i

S

S

S

S

28

С учетом этого из (12) получим

x n x 0 x 0 H 1	b	H 1	b	.	(13)

Таким образом, точка x n , полученная в результате минимизации квадратичной функции на n -м шаге, совпадает с точкой минимума

квадратичной функции f x .

Покажем теперь, что для сопряженных направлений, если f x

каждый раз минимизируется в сопряженном направлении S j в соответствии с формулой (6), то при этом выполняется следующее равенство:

j T

f x l

S

0 ,

1 j l

1 ,

при использовании не более чем n направлений, т. е.

f xl ортого-

нален использованным сопряженным направлениям.

f x l

Hx l . Следовательно,

Для квадратичной функции

b

l

1

j

l

1

j ,

f x l

b

H x k

j

S

b

Hx k

H

j

S

j

k

j

k

где x k – произвольная точка, из которой начинается поиск по сопряженным направлениям.

Так как

f x k

Hx k ,

b

то

f xl

f x k

l

1

j H

j .

S

j

k

Умножение этого равенства слева на

k

1

T

S

дает

k 1 T

f x l

k 1 T

f x k

l 1 j

k 1 T H

j .

S

S

S

S

j k

29