Загребаев Методы матпрограммирования 2007

3.3.1.2. Метод ортонормальных направлений (метод Розенброка)

В этом методе в каждом цикле производится поиск вдоль n взаимно ортогональных направлений. После завершения цикла с помощью процедуры Грама-Шмидта строится новая система ортогональных направлений. Преимущество этого метода состоит в следующем. Если целевая функция имеет узкий искривленный гребень (точнее, овраг), то поиск по n взаимно ортогональным направлениям эффективен тем, что результирующее направление стремится расположиться вдоль оси оврага. Это существенно ускоряет процесс по сравнению с методом покоординатного спуска.

Рассмотрим процедуры, выполняемые на k -м цикле метода. Пусть в начале цикла имеется точка x0k , числа λ1 , λ2 , K, λn –

ˆ k	ˆ k	ˆ k	– единичные векторы, задающие на-
длины шагов, S1	, S2	, K, Sn
правления поиска		экстремума. (Для первого цикла x01 ,

λ1 , λ2 , K, λn выбираются произвольно, направления, как правило, совпадают с координатными осями.)

	ˆ k	делается шаг λ1 λ1 .
В направлении S1
k	ˆ k	k	то шаг считается успешным и по-
Если f (x0	+ λ1S1 ) ≤ f (x0 ) ,
лученная точка занимает место			k	k	k	ˆ k	. Величина
			x0 ,	т.е. x0 = x0		+ λ1S1
λ1 умножается на число α (α > 1, обычно					α = 3),		т.е. теперь
λ1 = αλ1 .	ˆ k
k		k		шаг считается неуспешным,
Если f (x0	+ λ1S1	) > f (x0 ) , то
точка x0k остается без изменений,				а величина		λ1 умножается на

число β (β < 0, обычно β = −0,5 ), т.е. λ1 = βλ1 .

Далее та же самая процедура повторяется для остальных на-

ˆ k	ˆ k	. В результате будет получена новая точка	k
правлений S2	, K, Sn		x0

и совокупность шагов λ1 , λ2 , K, λn тоже новая. Затем снова воз-

ˆ k	и задаем шаг либо αλ1 , либо βλ1 в
вращаемся к направлению S1

зависимости от того успешным или неуспешным был шаг до этого.

191

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

Второй этап цикла состоит в выборе исходных данных для следующего цикла.

Вкачестве начальной точки следующего цикла x0k +1 берется последняя успешная точка.

Вкачестве шагов λi , i =1, n, – последние получившиеся значе-

ния. После этого выбираются новые направления. Строится система векторов:

ˆ k	ˆ k	ˆ k	;
q1 = Λ1S1	+ Λ2 S2	+K+ Λn Sn
q2 =	ˆ k	ˆ k	;
	Λ2 S2	+K+ Λn Sn
K
qn =		ˆ k	,
		Λn Sn

здесь Λi – алгебраическая сумма длин успешных шагов по i-му

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

Если изобразить условно направления на плоскости, то получим следующий рисунок (рис. 3.16).

Рис. 3.16. Графическое представление метода Розенброка на одной из итераций

Как видно из рисунка, вектор q1 соединяет точку, в которой

процесс находился в начале цикла, с точкой, в которую он попал в конце цикла.

192

Данная система векторов q1,K, qn ортогонализируется с помощью процедуры Грама-Шмидта.

В качестве начального (первого) направления принимается q1

(так как это направление располагается вдоль предполагаемого гребня функции).

Процедура ортогонализации Грама-Шмидта. Пусть имеем n

векторов q1 , K, qn . Необходимо получить n

ˆ k	ˆ k
нальных векторов S1	, K, Sn .

Будем находить эти вектора по формуле:

единичных ортого-

ˆ						yi
Si	=								, где	yi –
						yi

1
вспомогательный вектор, i =	1, n	,		yi		= yi , yi		– норма вектора.
							2

Вектора yi вычисляются по рекуррентным формулам:

y1 = q1,

…

	i−1		qi , y j
yi = qi − ∑				y j , i =1, n;
			y j , y j
	j=1
ˆ	= q1,
S1
…			ˆ
ˆ	i−1		qi , S j		ˆ
Si	= qi − ∑		ˆ ˆ		S j , i =1, n .
	j=1		S j , S j

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

k – номер цикла;

			ˆ
i =1, n – номер итерации при движениях по Si ;
j – счетчик неудачных шагов;
x0		– это x в начале цикла;
x	– текущий аргумент.

193

Вход

Ввод начальных данных

ε α β λ λ ˆ ˆ , n, x0 , , , 1,.. n , S1,..Sn

k = 0

x* ≈ x0

3

Λi = 0

2

j = 0 i = 1

+ λ ˆ <

f (x i Si ) f (x)

Да

= + λ ˆ x x i Si

Λi = Λi + λi

λi = αλi

Нет

λi = βλi

j = j + 1

i = i + 1		i < n
	Да
					Нет
		j = n					2
						Нет
		Да
		x* − x				< ε	x* = x	Выход
	Нет
	Ортогонализация
		x0 = x					Рис. 3.17. Блок-схема
		k = k + 1
							метода Розенброка
	3
	194

3.3.1.3. Метод сопряженных направлений (метод Пауэлла)

Два вектора x и y называются Q-сопряженными (или сопря-

женными по отношению к матрице Q), если x тQy = 0 , где Q – положительно определенная матрица ( x и y называют взаимно ор-

тогональными, если x т y = 0 . Таким образом, понятие сопряженности является обобщением понятия ортогональности).

Направления S1 , S2 , K, Sn являются сопряженными относительно матрицы Q, если

SiтQS j = 0 при i ≠ j , i, j =1, n .

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

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

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

f (x) = a + x тb + 12 x тQx ,

где x – n-мерный вектор, Q – матрица Гессе (Q – положительно определенная матрица), то минимум такой функции может быть найден ровно за «n» шагов от любой начальной точки, если поиск вести вдоль системы из n Q-сопряженных направлений.

На рис. 3.18 приведен пример формирования Q-сопряженных направлений для случая квадратичной целевой функции f (x) .

195

Рис. 3.18. Определение сопряженных направлений (n = 2)

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

аналитически и дает результат x* = −Q−1b ?

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

тывают на квадратичной функции.

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

Метод Пауэлла основывается на следующей особенности: любая прямая, которая проходит через точку минимума квадратичной формы, пересекает под равными углами поверхности уровня. Очевидно, это эквивалентно тому, что все касательные, проведенные к линиям уровня в точках их пересечения прямой, проходящей через экстремум, будут параллельны. На рис. 3.19 приведена иллюстрация этого свойства для квадратичной функции f (x) .

196

Рис. 3.19. Расположение касательных к линиям уровня в точках x1, x2

Из этого следует, что если x1 и x2 – два минимума, расположенные на двух параллельных направлениях, то минимум квадратичной функции нужно искать на направлении x1 − x2 . Причем

легко убедится, что это направление является Q-сопряженным с S. Градиент квадратичной функции:

f (x) = b + Qx .

Поскольку x i – это точки минимума на направлении S, градиент функции в этих точках ортогонален к S, т.е.

S т f (x1 ) = 0 = S т (b + Qx1 ),

S т f (x 2 ) = 0 = S т (b + Qx 2 ).

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

0 = S тQ(x1 − x 2 ) ,

т.е. S и (x1 − x 2 ) – Q-сопряженные направления.

Алгоритм метода Пауэлла.

1. Выбрать в качестве начальных направлений S10 , S20 , K, Sn0 , совпадающие с координатными осями (k = 0). Выбрать начальную точку поиска x0k .

197

2. Определить с помощью одномерного поиска

			min f (x0k + λ1S1k ) .
			λ1
Положить x k	= x k + λ* S k . Затем последовательно осуществить
1	0	1	1

одномерный поиск вдоль направлений S2k , K, Snk , определив последовательность точек

xik = xik+ + λ*i Sik , i = 2, n .

1

3. Вычислить направление S = xnk − x0k и сформировать новые направления для следующей итерации:

{S1k +1 , S2k +1 , K, Snk +1}= {S2k , S3k , K, Snk , S}.

4. Найти	λ* из условия min f (x k + λS k ) (т.е. найти минимум
	λ	n	1

вдоль нового полученного направления) и взять в качестве начальной точки для следующей итерации x0k +1 = xnk + λ* S k , положив

k = k +1 , и перейти к п. 2.

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

будет найдена точка минимума.

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

198

Ввод нач. данных ε, n, x0

i =	1, n	Si = ei
		k = 0
		x = x0 , i =1

Определение λ*i из

i = i +1

min f (x + λi Si )

λ

x = x + λ*i Si

i < n

Да

Нет

Да

x0 − x

≤ ε

x* ≈ x

Выход

Нет

Si = x − x0

Определение λ*i

из

min f (x + λi Si )

λ

0 =

+ λ*i Si

x

x

Sn = S

i = 1

i = i +1

Si = Si+1

Да

i < n −1

Нет

k = k + 1

Рис. 3.20. Блок-схема алгоритма метода Пауэлла

199

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

3.3.2.1.Градиентные методы

Приемлемым направлением, т.е. направлением, в котором функция убывает, как было показано раньше, является направление S, для которого

f (x), S < 0 .

Поэтому направление S = − f (x) является приемлемым. Более

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

Градиентным называется метод, согласно которому точка xk +1 выбирается в соответствии с соотношением

xk +1 = xk − λk f (xk ) .

В зависимости от способа выбора шага λk можно получить раз-

личные варианты градиентного метода.

1 вариант (метод наискорейшего спуска). Согласно этому ме-

тоду λk определяется путем решения одномерной задачи минимизации

min f (xk − λk f (x k )) .

λk

В отдельных случаях эта задача может быть решена точно, аналитически.

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

Двумерная иллюстрация метода представлена рис. 3.21. Действительно, точка xk +1 лежит на данном направлении в точ-

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

200