MO_conspect

	df (x 0		1 )
		S		T f (x 0 )		1 (		1 )T 2 f (x 0 )		1 0 ,
					S		S		S		(1)
	d

и, таким образом,	оптимальное значение на первом шаге определяется в
соответствии с соотношением
				T f (x 0 )		1				T f (x 0 )					1
1					S								S				,	(2)
	(			1 )T 2 f (x 0 )				1		(		1 )T H				1
			S				S				S			S

где H 2 f (x k ) .

Из точки x1 процесс минимизации должен осуществляться в другом

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

(S 2 )T H S1 0.

Отметим, что квадратичная функция может быть представлена в виде f (x) a bT x 12 xT H x ,

где положительно определенная матрица H 2 f (x ) .

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

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

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

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

вектор в пространстве E n можно выразить через систему

1 ,

2 ,...,

n

S

S

S

следующим образом:

n

V

v j

S

j ,

j 1

где

j T

H

v j

S

V

.

(3)

j T

H

j

S

S

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

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

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

n

j

j

T

S

S

H 1

.

(4)

T

j

H

j

j 1

S

S

21

Чтобы убедиться в его справедливости, рассмотрим матрицу

n

j S j (S j ) . Умножение ее справа на H S k дает

j 1

n

j

j (

j ) H

k k

k (

k ) H

k

k ,

S

S

S

S

S

S

S

j 1

если положить k S k H S k 1 .

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

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

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

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

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

Пусть f x

- квадратичная

функция и

f x a

T x

1

xT H x ,

b

2

при этом

f x

H x .

b

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

f x 0 ,

и эта точка

x H 1

b

.

Заметим, что

k

k T f x k .

T f x k

S

S

Так как

x1 x 0 1

1 ,

S

(5)

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

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 S 2

и т.д., то на n -м шаге имеем

n
x n x 0 i S i .	(6)

i 1

22

На

каждом

шаге

минимизируем

одномерную

функцию

f x i 1 i

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

i ,

чтобы получить i .

S

S

На основании (2)

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

T

i

f

n

S

x i 1

i

x n

x 0

S

.

(7)

T

i 1

i

H

i

S

S

Кроме того,

i

T

i

T

i

T

i 1

k

S

x i 1 S

H

b S

f

x i 1

H

x 0

k S

b

k 1

и получаем

i

T

i 1

i

T

0

S

f x

S

так как все

i T H

H x b ,

k

0 ,

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

i

и

k .

S

S

S

S

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

i T H x 0

i

n

S

b

S

x n

x 0

i

T

i

.

(8)

i 1

S

H

S

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

и H 1

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

b

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

S

i

T H x 0

i

n

S

S

x 0

i T H

i

,

i 1

S

S

i T H H 1

i

i T

i

n

S

b

S

n

S

b

S

H 1

b

.

i T H

i

i T H

i

i 1

S

S

i 1

S

S

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

x n x 0 x 0 H 1

b

H 1

b

.

(9)

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

точка

x n ,

полученная в результате минимизации

квадратичной функции на n -м шаге, совпадает с точкой минимума квадратичной функции f x .

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

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

23

S j T f x l 0 , 1 j l 1,

при использовании не более чем n направлений, то есть f x l ортогонален использованным сопряженным направлениям.

Для квадратичной функции f x l b H x l . Следовательно,

			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 b H x k ,

то

l 1

f x l f x k j H

j .

S

j k

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

k 1 T дает

S

T

T

l 1

T

k 1

f x l

k 1

f x k j

k 1

H

j .

S

S

S

S

j k

Первый член в правой части

k 1 T f x k 0 ,

S

так как градиент в

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

женности направлений S k 1 и S j , и таким образом

		j T f x l 0 ,	1 j l 1.
	S			(10)
То есть, градиент в точке x l ортогонален ко всем использованным
ранее сопряженным направлениям.
2.5.2. Алгоритм метода Пауэлла
Переход из точки x k в точку			x k на k -м шаге алгоритма Пауэлла
0			n

осуществляется в соответствии с формулой:

n k xnk x0k kj S j .

j 1

При этом последовательно осуществляется минимизация исходной функ-

ции по сопряженным направлениям S1k ,..., S kn . Результатом минимизации по каждому из сопряженных направлений является система параметров

24

k1 ,..., kn , при которых функция минимальна в каждом из сопряженных направлений:

k	arg min		f (x k						kj ) ,
								S
j				j 1
	x k x k			k			kj .
					S
	j	j 1		j

Начальную систему используемых направлений можно выбрать параллельной осям системы координат.

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

Построение новой системы базируется на следующей теореме.

Теорема: Если при начальной точке x 0 поиска в направлении вектора S

минимум функции f x	находится к точке x a , а при начальной точке
x1 x 0 поиск минимума		f x в том же направлении		приво-
	функции		S
дит к точке x b , то при f	x b f	x a направление x b x a сопряжено с

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

Доказательство. Используя ранее полученные результаты (10), можно записать, что в первом случае

ST f x a ST H x a b 0,

аналогично, во втором случае можно записать

ST f x b ST H x b b 0 .

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

ST H x b x a 0 .

Следовательно, векторы S и x b x a являются сопряженными.

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

из точки x 0 , точка x a определяется после использования при минимизации нескольких сопряженных направлений p ( p n) . И, аналогично, если

из точки x1 x 0 точка x b определяется после использования тех же направлений и функция f x минимизируется на каждом шаге, то вектор

x b x a сопряжен ко всем p направлениям. Рисунок 2.5 служит иллюстрацией теоремы.

25

Рис. 2.5. Сопряженные направления для квадратичной функции

Пусть в начальный момент для двумерной задачи поиск осуществляется из точки x 0 вдоль направлений, параллельных осям координат: S10 и S 02 . Последовательно были найдены точки x10 , x20 , x30 (см. рис. 2.6). Таким образом, определили 2 сопряженных направления, в которых следует вести поиск: S 02 и (x30 x10 ) .

Рис. 2.6

26

В системе исходных направлений S10 должно быть заменено на (x30 x10 ) , представляющее собой полное перемещение из первого минимума. Направления поиска на следующем этапе:

S11 S 02 ,

S12 x30 x10 .

Второй этап начинается с минимизации вдоль направления S12 , за-

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

В общем случае, на k -м шаге алгоритма Пауэлла используется n линейно независимых направлений поиска. Поиск начинается с точки x0k и осуществляется по следующему алгоритму:

1. Начиная с точки x0k , решается последовательность задач миними-

зации функции min f (x k				kj ) ,	j		, в направлениях		1k ,...,		nk . При
			S			1, n		S		S
	j 1

этом находятся точки x k ,..., x k , которые минимизируют исходную функ-

1

n

x k x k

1k ,

x k x k

2k ,

цию в заданных направлениях, причем

S

2

S

1

0

1

2

1

…, x k x k

nk .

n

S

n

n 1

2. Поиск, осуществляемый на первом этапе, может привести к ли-

нейно зависимым направлениям, если, например, в одном из направлений

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

На примере квадратичной функции Пауэллом было показано, что при нормировании направлений поиска в соответствии с соотношением:

S ik T H S ik 1, i 1, n ,

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

поиска, принимает максимальное значение тогда и только тогда, когда S ik взаимно сопряжены относительно матрицы H . Он пришел к выводу, что направление полного перемещения на k -м шаге должно заменять предыдущее направление только в том случае, когда заменяющий вектор увеличивает определитель матрицы направлений поиска. Так как только тогда новый набор направлений будет более эффективным.

Для такой проверки из точки		x k	делается дополнительный шаг в на-
		n
правлении x k x k , соответствующий полному перемещению на				k -м
n	0
				27

этапе, и получают точку (2xnk x0k ) . Для проверки того, что определитель

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

3. Обозначим наибольшее уменьшение f (x ) на k -м шаге

k max f (x k

) f (x k ) ,

i 1,n

i 1

i

соответствующее направление поиска обозначим через

mk .

S

Обозначим:

f f (x k ) ,

f

2

f (x k ) ,

f

3

f (2x k

x k ) ,

1

0

n

n

0

где

n

x0k xnk 1 ,

xnk xnk 1 n

nk

x0k i

ik .

S

S

i 1

Тогда, если f

3

f

1

и (или)

( f

2 f

2

f

3

)( f

f

2

k )2 0.5 k ( f

f

3

)2

,

1

1

1

k 1 -м этапе те же направления

1k ,...,

nk ,

то следует использовать на

S

S

ik 1

ik ,

i

, и начать поиск из точки

что и на

k -м этапе, то есть

S

S

1, n

x k 1

x k

или из точки x k 1 2x k

x k x k

, в зависимости от того, в ка-

0

n

0

n

0

n 1

кой точке функция принимает минимальное значение.

4. Если тест на шаге 3 не прошел, то ищется минимум

f (x ) в на-

nk 1 , проведенного из x k

в x k :

nk 1

x k x k . Точка

правлении вектора

S

S

0

n

n

0

этого минимума берется в качестве начальной точки на k 1 -м этапе. А в системе сопряженных направлений сохраняются все, кроме направления

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

nk 1 , но новое направление

S

S

помещается в последний столбец матрицы направлений. На

k 1 -м этапе

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

k 1

k 1

k 1

k

k

k

k

k

k

S1

, S 2

,..., S n

S1

, S 2

,..., S m 1

, S m 1

,..., S n , S n 1 .

5. Критерий останова. Алгоритм прерывается, если изменение по каждой переменной оказывается меньше заданной точности по соответст-

вующей переменной или xnk x0k .

Контрольные вопросы

1.Алгоритм Гаусса, его достоинства и недостатки, критерии останова?

2.Алгоритм Хука и Дживса, этапы алгоритма?

3.Алгоритм Розенброка, как осуществляется поворот системы координат? Для чего используется ортогонализация Грама-Шмидта?

28

4.Симплексный метод Нелдера-Мида, идея метода, этапы алгоритма поиска по деформируемому многограннику?

5.Что дает применение сопряженных направлений в алгоритмах оптимизации и для каких функций? Теорема, лежащая в основе алгоритма Паулла?

6.Алгоритм Пауэлла, построение сопряженных направлений?

3.Методы первого порядка

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

3.1. Алгоритм наискорейшего спуска

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

следует двигаться в направлении противоположном направлению градиента f (x) в данной точке, то есть в направлении наискорейшего спуска.

Итерационная формула процесса наискорейшего спуска [2-4] имеет

вид
x k 1 x k k f x k ,
или					f x k
x k 1 x k k									k
							x k k S			.
					f x k

Очевидно, что в зависимости от выбора параметра траектории спуска будут существенно различаться (см. рис. 3.1). При большом значении траектория спуска будет представлять собой колебательный процесс, а при слишком больших процесс может расходиться. При выборе малых траектория спуска будет плавной, но и процесс будет сходиться очень медленно.

Обычно выбирают из условия

k arg min f (x k S k ) ,

решая одномерную задачу минимизации с использованием некоторого метода. В этом случае получаем алгоритм наискорейшего спуска.

Если определяется в результате одномерной минимизации, то градиент в точке очередного приближения будет ортогонален направлению

предыдущего спуска f x k 1 S k .

29

Рис. 3.1. Траектории спуска в зависимости от величины шага

Вообще говоря, процедура наискорейшего спуска может закончиться в стационарной точке любого типа, в которой f x 0 . Поэтому следует

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

Эффективность алгоритма зависит от вида минимизируемой функции. Алгоритм наискорейшего спуска сойдется за одну итерацию при лю-

бом начальном приближении для функции f x	x2	x2	(см. рис.3.2). Но
	1	2
сходимость будет очень медленной, например,	в случае функции вида

f x x12 100x22 . В тех ситуациях, когда линии уровня минимизируемой

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

Рис. 3.2. Траектории спуска в зависимости от вида функций

30