МО-Лекции

Первый член в правой части S k 1 T f x k 0 , так как градиент в

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

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

k

1

и

j , и таким образом,

S

S

j T

x l

S

f

0 ,

1

j

l 1 ,

(14)

т. е. градиент в точке xl

ортогонален всем использованным ранее со-

пряженным направлениям.

2.5.2. АЛГОРИТМ МЕТОДА ПАУЭЛЛА

Переход из точки x k

в точку

x k

на k

-м шаге алгоритма Пауэлла

0

n

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

x k

x k

n

k

kj .

S

n

0

j

j

1

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

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

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

	k			k				k
		arg min f					S j		,
	j			x j 1
		x jk x jk		kj		kj .
			1		S

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

30

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

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

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

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

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

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

T f x a

T Hx a

S

S

b 0 ,

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

T f xb

T Hxb

S

S

b 0 .

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

T H xb x a

0 .

S

Следовательно, векторы

и xb

x a являются сопряженными.

S

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

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

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

Рис. 2.5 служит иллюстрацией теоремы.

31

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

Пусть в начальный момент для двумерной задачи поиск осуществляется из точки x 0 вдоль направлений, параллельных осям координат:

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

следует вести поиск:		02 и	x 0	x 0 .
	S
			3	1

Рис. 2.6. Построение сопряженных направлений в процессе поиска

32

10 должно быть заменено на

В системе исходных направлений

S

x 0

x 0

, представляющее собой полное перемещение из первого ми-

3

1

нимума. Направления поиска на следующем этапе:

11

02 ,

S

S

12

x 0

x 0 .

S

3

1

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

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

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

x k	и ведется по следующему алгоритму.
0
	1. Начиная с точки x k ,	решается последовательность задач мини-
	0
		x jk			kj , j		, в направлениях
мизации функции min f			1	S		1, n

1k ,...,

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

S

S

1

n

исходную функцию в заданных направлениях, причем x k

x k

1k ,

1

S

1

0

x k

x k

2k , …, x k

x k

nk .

2

S

n

S

2

1

n

n 1

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

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

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

33

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

	k T			k
S i		H S i			1 , i 1, n ,

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

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

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

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

3. Обозначим наибольшее уменьшение

f (x )

на k -м шаге

k

max

f x k

1

f

x k

,

i

1,n

i

i

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

mk .

S

Обозначим:

f

f x k

, f

2

f x k

,

f

3

f 2x k

x k

,

1

0

n

n

0

где

x k

x k 1

x k

x k

nk

x k

n

ik .

,

1

n

S

i

S

0

n

n

n

0

i 1

Тогда, если

f

3

f

и

(или)

( f

2 f

2

f

3

)( f

f

2

k )2

1

1

1

0.5 k ( f1 f3 )2 , то следует использовать на k 1 -м этапе те же

34

1k ,...,

kn ,

ik 1

ik ,

направления

S

S

что и на

k- м этапе, т. е.

S

S

i

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 -м

этапе. А в системе сопряженных направлений сохраняются все, кроме

направления S km , которое заменяется на новое направление S kn 1 , но новое направление помещается в последний столбец матрицы направ-

лений. На

k

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

1k 1,

2k

1,...,

kn

1

1k ,

k2 ,...,

km 1,

km 1,...,

kn ,

kn 1 .

S

S

S

S

S

S

S

S

S

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

ветствующей переменной или	x k	x k	.
	n	0

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

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

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

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

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

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

35

3. МЕТОДЫ ПЕРВОГО ПОРЯДКА

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

3.1. АЛГОРИТМ НАИСКОРЕЙШЕГО СПУСКА

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

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

шего спуска.

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

x k 1

x k

k f x k

,

или

k

f

x k

k

x k 1 x k

x k

k S

.

f

x k

Очевидно, что в зависимости от выбора параметра

траектории

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

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

k arg min f x k S k ,

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

36

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

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

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

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

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

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

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

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

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

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

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

37

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

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

3.2.МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ

Валгоритме наискорейшего спуска на каждом этапе поиска ис-

пользуется только текущая информация о функции f (x k ) и градиенте

f (x k ) . В алгоритмах сопряженных градиентов [2–5] используется информация о поиске на предыдущих этапах спуска.

Направление поиска S k на текущем шаге k строится как линейная комбинация наискорейшего спуска f xk на этом шаге и направле-

ний спуска S0 , S1, ..., S k 1 на предыдущих шагах. Веса в линейной

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

При выборе весов используется только текущий градиент и градиент в предыдущей точке.

В начальной точке x 0 направление спуска					0	f x 0 :
				S
x1 x 0	0		0 ,			(1)
		S

где 0 выбирается из соображений минимальности целевой функции в данном направлении

0			arg min f x 0					0 .
						S
Новое направление поиска
		1	f x1	1			0 ,
	S				S				(2)

38

где

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

1 и

0

сопряжен-

1

S

S

ными по отношению к матрице H :

0

H

1

0 .

(3)

S

S

Для квадратичной функции справедливы соотношения:

f x

f x 0

f x 0

x

1

x

2 f x 0

x ,

2

где

x x x 0 ,

f x

f x 0

2 f x 0

x .

Если положить x

x1 , тогда x1

x0

0

0

и

S

f x1

x 0

2 f

x 0

x1

x 0

0

0 .

(4)

f

H

S

Воспользуемся (4),

чтобы исключить

0

из уравнения (3). Для

S

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

H , поэтому, транспонировав (4) и умно-

жив справа на H 1 , получим

f x1

f x 0

H 1

x1

x 0

H H 1

и далее

0 T

x1 x 0

f x1

f x 0

H

1

S

.

0

0

Следовательно, для сопряженности

0 и

1

S

S

f x1

f x 0

H 1H

1

S

f x1

f x 0

f x1

1

0

S

0.

39