MO_conspect

3.Редукция интервала неопределенности в методе дихотомии? В методе золотого сечения? В методе Фибоначчи?

2. Прямые методы поиска

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

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

Прямые методы предназначены для решения безусловных задач оптимизации вида

min f (x ) .

x En

2.1. Алгоритм Гаусса

Это простейший алгоритм [2], заключающийся в том, что на каждом шаге (каждой итерации) минимизация осуществляется только по одной компоненте вектора переменных x .

Пусть нам дано начальное приближение x 0 (x10 , x20 ,..., xn0 )T . На пер-

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

x11 arg min f (x1, x20 ,..., xn0 ) .

x1

В результате получаем новую точку x1 (x11, x20 ,..., xn0 ) . Далее из

точки x1 ищем минимум функции, изменяя вторую координату и считая фиксированными все остальные координаты. В результате получаем значение

x12 arg min f (x11, x2 , x30 ,..., xn0 )

x2

и новую точку x 2 (x11, x22 , x30 ,..., xn0 ) . Продолжая процесс, после n шагов получаем точку x n (x11, x22 ,..., xnn ) , начиная с которой процесс поиска во-

зобновляется по первой переменной.

В качестве условий прекращения поиска можно использовать следующие два критерия:

1) f (x k 1 ) f (x k ) 0 ;

2)xik 1 xik i , i .

11

Рис. 2.1. Пример траектории спуска в алгоритме Гаусса

Метод очень прост, но не очень эффективен. Проблемы могут возникнуть, когда линии уровня сильно вытянуты и "эллипсоиды" ориентированы, например, вдоль прямых вида x1 x2 . В подобной ситуации поиск

быстро застревает на дне такого оврага, а если начальное приближение оказывается на оси "эллипсоида", то процесс так и останется в этой точке.

Хорошие результаты получаются в тех случаях, когда целевая функция представляет собой выпуклую сепарабельную функцию вида

n

f (x ) fi (xi ) .

i 1

2.2.Алгоритм Хука и Дживса

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

1)исследующий поиск вокруг базисной точки x k ;

2)поиск по "образцу", т.е. в направлении, выбранном для мини-

мизации.

Впервую очередь задается начальная точка поиска x 0 и начальное

приращение (шаг) x 0 . После этого начинается исследующий поиск. Исследующий поиск. Делаем пробный шаг по переменной x1 , т.е.

определяем точку x10 x10 и вычисляем значение функции в точке x ' (x10 x10 , x20 ,..., xn0 ) .

12

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

положном	направлении. Если			значение		функции и в	точке
x '' (x0 x0		, x0	,..., x0 ) больше чем		f (x 0 ) ,	то оставляем точку	x0 без
1	1	2	n				1
изменений. Иначе заменяем точку				x 0	на x ' или на x '' в зависимости от

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

Если в процессе исследующего поиска не удается сделать ни одного удачного пробного шага, то x необходимо скорректировать (уменьшить). После чего вновь переходим к исследующему поиску.

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

Поиск по образцу. После исследующего поиска мы получаем точку

x 01 . Направление x 01 x 0 определяет направление, в котором функция уменьшается. Поэтому проводим минимизацию функции в указанном направлении, решая задачу

min f (x 0 (x 01 x 0 )) .

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

приближение x1 x 0 0 (x 01 x 0 ) , где

0 arg min f (x 0	(x 01 x 0 )) .

Рис. 2.2. Пример траектории спуска в алгоритме Хука и Дживса

13

Из точки x1 начинаем новый исследующий поиск и т.д.

Возможны модификации алгоритма, в которых в процессе исследующего поиска ищется минимум по каждой переменной или в процессе поиска по образцу ищется не минимум функции, а просто делается шаг в

заданном найденном направлении с фиксированным значением параметра

.

2.3. Алгоритм Розенброка

Этот итерационный метод имеет некоторое сходство с алгоритмом Хука и Дживса. Метод Розенброка называют также методом вращающихся координат. Этот метод заметно эффективнее предыдущих методов, особенно при минимизации функций овражного типа.

Общая идея метода [2] заключается в том, что выбирается система

ортогональных направлений S10 , S 02 ,..., S 0n , в каждом из которых последовательно ищется минимальное значение, после чего система направлений поворачивается так, чтобы одна из осей совпала с направлением полного перемещения, а остальные были ортогональны между собой.

Пусть x 0 - вектор начального приближения; S10 , S 02 ,..., S 0n - система ортогональных направлений. На первой итерации это может быть орто-

нормированная система координат. Начиная с x 0 , последовательно осуществляем минимизацию функции f (x ) в направлениях, соответствующих

S10 , S 02 ,..., S 0n , находя последовательные приближения:

x 0

x 0

0 , где

arg min f (x 0

0 ) ,

S

S

1

0

1

1

1

0

1

….

x 0

x 0

arg min f (x

0

0 ) .

S

0 , где

n

S

n

n 1

n

n

n 1

n

Следующая итерация начнется с точки x1 x 0 .

n

Если не изменить систему направлений, то мы будем иметь алгоритм Гаусса. Поэтому после завершения очередного k -го этапа вычисляем новые направления поиска. Ортогональные направления поиска поворачивают так, чтобы они оказались вытянутыми вдоль "оврага" ("хребта") и, таким образом, будет исключаться взаимодействие переменных ( xi x j ). На-

правления поиска вытягиваются вдоль главных осей квадратичной аппроксимации целевой функции.

Рассмотрим k -ю итерацию алгоритма Розенброка. В результате минимизации по каждому из ортогональных направлений мы имеем на дан-

ной итерации систему параметров k1 , k2 ,..., kn , с помощью которой опре-

		k			k			k
делим систему векторов A1			, A2			,..., An , вычисляемых по формулам сле-
дующего вида:
						14

k

k

k

k

A1

k1 S1

k2 S 2

... kn S n ;

k

k

k

A2

k2 S 2

... kn S n ;

… ;

k

k

An kn S n .

k

k

k

строим но-

С помощью полученной системы векторов A1

, A2

,..., An

вую систему ортогональных направлений S1k 1, S k2 1,..., S kn 1 . Причем первый вектор направляется так, чтобы он совпал с направлением общего перемещения на k -м шаге, а остальные направления получаются с помощью процедуры ортогонализации Грама-Шмидта:

k

1k 1

A1

S

;

k

A1

k 1

k 1

k

k

k

;

B2

A2

( A2 )T

S1

S1

k

2k 1

B

2

S

;

(1)

k

B

2

k

k

l 1

k

k 1

k 1

Bl

Al

( Al )T S m

S m

;

m 1

k

lk 1

Bl

l 2,..., n

S

;

k

Bl

Рис. 2.3. Пример траектории спуска в алгоритме Розенброка

15

Для эффективной работы алгоритма необходимо, чтобы ни один из векторов системы S1k 1, S 2k 1,..., S nk 1 не стал нулевым вектором. Для этого в алгоритме следует располагать параметры k1 , k2 ,..., kn в порядке убывания

по абсолютному значению, т.е.	k		k	...	k	. Тогда если любые m из
	2		2		n

ki обращаются в нуль, то отыскиваются новые направления по соотноше-

ниям (1) только для тех (n m)	направлений, для которых ki	0 . Остав-
шиеся же m направлений				ik 1		ik ,
	остаются неизменными:		S		S

i (n m 1), n . Так как первые (n m) векторов взаимно ортогональны,ki 0 , i (n m 1), n , первые (n m) векторов не будут иметь состав-

ляющих в направлениях S ik 1 , i (n m 1), n . А поскольку эти последние

направления взаимно ортогональны, то из этого следует, что все направления являются взаимно ортогональными.

k

k

пропорциональны kj

Палмером [2] было показано, что B j 1

и

B j 1

n

ki

2

(при

условии, что

0 ).

Следовательно, при вычислении

i j

k 1

k

k

kj

S j

B j

B j

, величина

сокращается, и, таким образом, направление

kj 1

остается определенным, если даже kj 0 . Имея это в виду, Палмер

S

предложил для вычисления

kj 1

S

следующие соотношения:

k

n

k

i 1,.., n ,

Ai

kj S j

,

j i

k

k

2

k

k

2

ik 1

Ai

Ai 1

Ai 1

Ai

i 2,...,n ,

S

,

2

2 1/ 2

k

k

k

k

Ai 1

Ai

Ai 1

Ai

k

1k 1

A1

.

S

k

A1

Критерии останова алгоритма могут быть стандартными (т.е. описанными в предыдущих алгоритмах прямых методов).

16

2.4. Симплексный метод Нелдера-Мида или поиск по деформируемому многограннику

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

гулярными симплексами. Регулярные многогранники в пространстве E n называются симплексами. Для 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 исключается и строится новый отраженный симплекс из оставшихся старых точек и одной новой, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести.

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

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

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

17

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

	Будем		рассматривать			k -ю	итерацию	алгоритма.		Путь
k	k	k	k		, i 1,..., (n 1) , является i -й вершиной в E				n
xi	xi1	, xi 2	,..., xin							на k -м

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

шине	f (x k ) . Отметим вершины с минимальным и максимальным значе-
	i
ниями. И обозначим их следующим образом:
		f (x k ) max f (x k ),..., f (x k					) ;
		h	1	n 1
		f (x k ) min f (x k ),..., f (x k				) .
		l	1	n 1
	Многогранник в E n		состоит из n 1 вершин x k , x k ,..., x k . Обозна-
								1 2	n 1
чим через x k		- центр тяжести вершин без точки			x k			с максимальным зна-
	n 2						h

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

			1	n 1
	xnk 2, j			xik, j xhk, j		,	j 1,..., n .	(1)
			n i 1

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

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

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

18

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

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

в соответствии со следующим соотношением:

h

n 2

x k

x k

(x k

x k ),

(2)

n 3

n 2

n 2

h

где 0 - коэффициент отражения.

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

f (x k

) . Если зна-

n 3

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

f (x k

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

n 3

h

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

f (x k

) f (x k )

f (x k

) f (

lk ) ,

Если

x

то

выполняем

операцию

n 3

h

n 3

растяжения.

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

f (x k

) f (x k )

f (x k

) f (x k ) , то вы-

n 3

h

n 3

l

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

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

заключается

в

следующем.

Если

f (x k

) f (x k ) (меньше минимального значения на k -м этапе), то вектор

n 3

l

(x k

x k

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

n 3

n 2

x k

,

x k

x k

x k

(3)

n 4

n 2

n 3

n 2

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

Если

f (x k

) f (x k ) ,

то

x k

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

x k

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

n 4

l

l

n 4

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

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

l

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

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

n 3

3. Сжатие. Если

f (x k

) f (x k )

для i i h , то вектор (x k x k

)

n 3

i

h

n 2

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

x k

x k

x k

x k

,

n 5

n 2

h

n 2

где 0 1 - коэффициент сжатия. После этого, точка xhk

xnk 5 , и переходим к операции отражения с k k 1.

xhk 1 .

	4. Редукция. Если		f (x k	) f (x k ) ,		то все векторы
			n 3		h
i		уменьшаются в два раза с отсчетом от точки							x k
	1, (n 1)
		x k x k 0.5 x k x k ,							l
						i
							1, (n 1)
		i	l	i	l

заменяется на Заново ищется

xik xlk , где

по формуле

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

kk 1).

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

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

19

1				k	k	1/2
			n 1			2
							.
			f (xi		) f (xn 2 )
n 1			i 1

Выбор коэффициентов , , обычно осуществляется эмпирически. После того, как многогранник подходящим образом промассштабирован, его размеры должны поддерживаться неизменными пока изменения в топологии задачи не потребуют многогранника другой формы. Чаще всего рекомендуют 1, 0.4 0.6, 2 3.

2.5. Метод Пауэлла и сопряженные направления

2.5.1. Обоснование применения сопряженных направлений в алгоритмах оптимизации

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

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

	Ti H		j 0,	i j ,
S		S
						Ti H		i 0 ,	i j ,
					S		S

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

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

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

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

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

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

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

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

длина шага 1 определяется из условия минимальности функции в данном направлении т.е.

1 arg min f (x 0			1 ) .
		S
Для квадратичной функции

20