книги / Математические методы принятия решений

1. Градиентный метод. Численным методом безусловной ми­ нимизации функций является градиентный метод с алгоритмом

xi+1 = х* - Xi

* = 0 ,1 ,2 , ...

(1.19)

где а;0 — начальное приближение, Х* — шаговый множитель на г-й

итерации,	дfix*)	V f ( x 1) —градиент функции f(x) в точке х г.
	=

Очередное приближение х г+х получается из предыдущего х г пу­ тем движения в направлении антиградиента (в направлении наи­ более быстрого убывания функции /(ж ) в окрестности точки ж1).

Наиболее широко распространены две модификации градиент­ ного метода:

1)простой градиентный метод, где шаговый множитель X или остается постоянным на протяжении всей итерационной процеду­ ры, или изменяется через какое-то число итераций;

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

внаправлении антиградиента, т. е. минимальное значение X* > 0 выбирается из условия

Вэтой процедуре соседние градиенты ортогональны, т. е.

V T/ ( жг+1)У /(ж г) = 0 для всех г.

Доказано, что всякая предельная точка ж последовательнос­ ти {ж1} стационарна, т. е. V /( ж) = 0.

Выбор шагового множителя X, можно проводить и другими ме­ тодами, в частности методом дробления. Если вектор sk указывает направление убывания значений функции /(ж), то дробление шаго­ вого множителя осуществляется следующим образом.

Выбираются некоторые константы р > 0, 0 < а < 1 (часто а = = 1/2). При X = р проверяется условие

f ( x k + Xsk) < f ( x k).

Если оно выполнено, то полагают \ k = Р- Если не выполнено, про­ изводится дробление шагового множителя, т. е. принимают \ к = <*Р- Далее вновь проверяется выполнение приведенного условия.

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

Если проверяемое в процессе дробления шагового множителя условие оказывается выполненным на первом шаге при значении X = р, то иногда бывает полезно увеличить шаг, положив X = рр, где (i > 1. Может оказаться, что умножение на р следует повто­ рить несколько раз. Последнее значение X, при котором произошло уменьшение значения функции /(х ), и принимают за Х*.

Градиентный метод имеет следующие недостатки, затрудняю­ щие его применение на практике.

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

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

3.Скорость сходимости итерационного процесса во многом за­ висит от вида функции /(х). Если отношение наибольшего соб­ ственного значения матрицы G вторых частных производных функ­ ции к наименьшему (коэффициент обусловленности матрицы G)

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

квиду сфер (окружностей).

Для увеличения скорости сходимости и для минимизации овраж­ ных функций применяется метод «тяжелого шарика»:

x i+l = x i - XiV/(x*) + (3(х* - х*~'),

где коэффициент (3 подбирается в числовом эксперименте, 0 < (3 < 1.

2. Метод сопряженных направлений. Как уже отмечалось ранее, векторы Si и Sj называются сопряженными относительно матри­ цы G, если sJGsj = 0 , г ф j.

Пусть функция fix ) имеет вид
fix ) = bTx + у xTGx,	( 1.20)

где G —положительно определенная матрица, 6 — вектор коэффици­ ентов при линейных членах.

Пусть s o , , sn_i — ненулевые векторы и числа X* таковы, что

/k—1

f ( x k+l) = f ( x ° + ^ XiSi + \kSk

'i= 0

есть минимум функции f( x ) в направлении вектора sк, если начи­ нать движение от точки

к- 1

Хк = Х° + 2 h s i ,	к = 1 , 2 , . . . , п - 1.
г=0

Точка х п будет безусловным минимумом функции f(x) на всем пространстве, если so, s ь ..., sn_i — сопряженные векторы.

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

Пусть х° —начальная точка и so = —V /(x°). Обозначим че­ рез хг+1 точку минимума функции f{x) на луче, выходящем из х г в направлении вектора s*.

П°Л0ЖИМ . | У № » ' У

Новый вектор Sj+i вычисляется по формуле

S»+1 = - V / ( x î+1) + PiSi-

Векторы i = 0 ,1 , ... , п — 1, оказываются сопряженными, если функция f{x) задана в форме (1.20). Этот метод получил название

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

Алгоритм метода сопряженных градиентов можно представить в виде

х г+х = х г -XjSi+1, г = 0 , 1 ,2 , ... ,

Si = V f{x°), s*+i = V /(x°) + PiSj, |V/(x»)|2

Рг |V/(x«-')|2'

Значение шагового множителя Xj находится из условия x f ( x l - XjSj+i) = nain /(ж 1 - Xsj+i).

Анализ сходимости последовательности {ж*} к точке миниму­ ма показывает, что метод сопряженных градиентов имеет примерно такую же область сходимости, что и метод наискорейшего спуска, но скорость сходимости — квадратичная. Метод сопряженных гра­ диентов может быть применен к функциям произвольного вида. Однако в данном случае рекомендуется производить обновление на­ правления вектора Sj либо через п -I-1 шагов, либо подобрать время обновления направления в числовом эксперименте, т. е. при обнов­ лении направления в точке х к вновь выбрать вектор s^+i = V f ( x k).

Метод переменной метрики

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

Пусть ж0 —начальная точка, #о — произвольная положительно определенная матрица, являющаяся начальным приближением об­ ратной матрицы вторых частных производных функции /(ж) в точ­ ке ж0. Обозначим через s* ненулевой направляющий вектор, полу­ ченный на г-й итерации, s* = —H iV f(x l), Oi = XiSu x l+l = х г + au

вектор Si является линейно независимым со всеми предыдущими векторами so, • • •, «i-i- Общее требование к векторам Sj следующее:

Ут/(ж г)вг < 0 для всех г.

Здесь Xj выбирают так, чтобы минимизировать функцию /(ж) в на­ правлении вектора вг, выходящего из точки ж1. Поскольку матри­ ца Щ положительно определена, то шаговый множитель Xj должен быть больше нуля, если только хг не является точкой минимума функции /(ж).

Пусть га = \7/(жг+1) —У /(ж г). Тогда очередное приближение обратной матрицы вторых частных производных функции /(ж)

	вычисляется по формуле	HiViyJHj
	Hi+ 1 = Щ + Qjàj
		yJHiVi
	°iVi

Если матрица Щ положительно определена, то матрица Hi+\ тоже положительно определена, а этим и обеспечивается убывание функции /(ж) на каждом шаге. Векторы оо, о \ , ... , оп- \ сопряжены относительно матрицы А, если функция f( x ) задана в виде (1.20). В методе переменной метрики существует большая свобода в вы­ боре Si и Но.

Рассмотрим модифицированный метод переменной метрики. В данном методе новое приближение для обратной матрицы вторых частных производных /(ж) имеет вид

H i+ 1 = H i + (ai - H iyiX yJioi - Щ уг)) ‘(о- - у}Щ ),

г = 0 , 1,2,...

Если yj(üi — Hiyi) = 0, то новое приближение для Щ не вычис­ ляют, а только выбирают новые направления движения. Поэтому полагают, что у}(а* - Щ у^ Ф 0.

После п преобразований матрицы Н выбирают направление вектора s11 = —HnV f ( x n). Тогда жп+1 будет искомым безуслов­ ным минимумом положительно определенной квадратичной фор­ мы. В этом методе на каждой итерации добавляется только один член к текущей обратной матрице вторых частных производных функции f(x).

Пример 1. Минимизируем функцию, являющуюся квадратич­

ной формой:
f(x) = ( 1 , 1)ж + у	хТ ^	X -► min.
Пусть ж0 = (0 ,0)т, Н 0 = ^	^ . Тогда V /( ж0) = ( 1 ,1)т.
Пусть so = (—1,0)т. Получим
Хо = у ,
о : '= ( 0 . 0 ) - + ( - i , 0 ) T= ( - i , 0 ) T		V / ' = ( o , ' ) ' .

(“’ т )Т -(1, 1>т=(- 1, - т )Т’

о0 - Н о у 0 =

о)

у1(<70 - Ноуо) = у ,

Я , =

Пусть si = (О, —1)т. Тогда

^1 = у ,

X

У1

2 ( - 1 , 0 ) = У	»
О	О;

01

у	) '	v	/ 2 = ( -
/		1	1 \ т
V		2 ’ ~ j )

		1 \	(	- \
ci —Н\у\ =		2	- 1	4
		1
			L	i
yftoi	- H \ y \ ) = - ,
	1 \
Нг =	4	8
	1
\"Т/
Матрица Яг равна обратной к матрице ^			.

На последнем шаге получаем безусловный минимум

	/ _ ±
z 3 =	+
	V'

Решение получено.

Если известна какая-нибудь квадратная подматрица порядка п — г матрицы вторых частных производных порядка п функции f(x), то для минимизации положительно определенной квадратичной формы потребуется только п + 1 шагов алгоритма переменной мет­ рики (при выполнении предыдущих предположений).

Пусть, например, известны вторые частные производные

d2f(x)

i , j = 1,2

dxidxj ’

Обозначим квадратную подматрицу матрицы, составленной из вторых частных производных, через G. Тогда

		G	а\
		G = V 2/	Ъ)
Имеем		ат
G "'	+	- G - î .	- /	ï- l
G~x =		( - a TG~ 1а + b y 1( - a rG ~ 1, /),

О

где / — единичная матрица. Здесь второе слагаемое есть матрица ранга г. Ее можно найти за г шагов. При известной матрице G - можно вычислить G~l .

Единственное отличие этого метода от прежней вычислитель­ ной процедуры состоит в том, что матрица Но берется в виде

Переход от матрицы к Нь+\ выполняется, как и прежде, но теперь Я*, положительно полуопределена и не станет положи­ тельно определенной до тех пор, пока не будет полностью получена обратная матрица.

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

Пример 2. Минимизируем ту же функцию, что и в предыдущем примере:

/(ж) = (1,1)х + j X r L j j х —►min.

Допустим, что диагональный элемент </ц матрицы G известен и равен 2.

Пусть Но =	, х° = (1, —2)т. Тогда /(х °) = (1 ,0)т.
Если so = (—1, —1)т, то
* 4	- ( 4	- \ У

УО= (^ , - | ) - (1, 0)Т = , Yt = y Ti(O i - НгУг),

	1 \			( Л	\
Сто - НоУо =		- 4	“	5
	1			2	Y0 = 5Ô-
	4	О	О,	\ ~ 5 /
		/

Найдем обратную матрицу:

Отсюда видно, что уже после первой итерации мы получили иско­ мую обратную матрицу.

Использование вторых частных производных

Рассмотрим обобщенный метод Ньютона, в котором использу­ ются вторые частные производные минимизируемой функции fix), т. е. учитывается дополнительная информация о форме поверхно­ сти f{x). Предположим, что матрица вторых частных производ­ ных G(x) = V 2f(x) невырождена. Итерационный процесс отыска­

ния точки минимума функции fix) имеет вид
xi+l = х * ~ bcr'ia tyvfix* ),	(1.21)

где шаговый множитель X* > 0 выбран так, чтобы минимизиро­ вать fix ) по направлению вектора —G _1(xt)V /(x l) от точки х \ Если Xi = l, то получим «чистый» метод Ньютона. Идея метода состоит в следующем: функция fix) заменяется двумя первыми

членами ее разложения в ряд Тейлора и полученная квадратичная форма минимизируется.

Если /(ж) —положительно		определенная квадратичная форма,
то итерационный метод (1.21)		при Xi = 1 позволяет достичь ми­
нимум за один шаг. Если	/(ж) — произвольная выпуклая функция,
то итерационный процесс	(1.21) гарантирует ее монотонное убыва­

ние от итерации к итерации.

Однако метод Ньютона имеет следующие недостатки:

1)не всегда существует матрица, обратная к G(x);

2)в невыпуклых функциях, т. е. когда матрица G(ж) не является положительно определенной, не гарантировано монотонное убы­ вание функции, если точка ж1 не близка к точке минимума; тогда получим Xj = 0 и процесс остановится в точке ж1;

3)для некоторых функций с непрерывными вторыми частны­ ми производными бывает сложно аналитически вычислять произ­ водные.

Вмодифицированном методе Ньютона эти недостатки пыта­ ются устранить. Направляющий вектор s* вычисляется двумя спо­ собами. В обоих случаях жг+1 = жг + X^Sj, причем шаговый мно­

житель Xj выбран наименьшим из всех X ^ 0, для		которых точка
х г + XjSi является локальным минимумом функции /(ж* + Xsj).
Эти два способа выбора вектора Si следующие:
1) если матрица G(х г) имеет отрицательное собственное значе­
ние, то Si— такой вектор, для которого
^(?(ж > * < 0,	si'7 f ( x i) ^ 0;	(1.22)
2) если все собственные значения матрицы G(х г) больше или
равны нулю, то выбираем s так, чтобы было либо
Gix^s = 0,	sTV /( ж4) < 0 ,	( 1.23)
либо
С?(ж> = -У /(ж *).		(1.24)

Одновременно условия (1.23) и (1.24) выполняться не могут. Единственным случаем, когда с помощью правил 1) и 2) нель­ зя указать ненулевой направляющий вектор s, является тот, ког­

да G(xl) — положительная полуопределенная матрица и У /(ж 1) = 0,

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

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

Однако правила 1) и 2) не гарантируют, что полученная после­ довательность {хг} будет иметь предельные точки, удовлетворяю­ щие необходимым условиям минимума.

В общем случае алгоритм модифицированного метода Ньютона имеет следующий вид.

1. Приводим матрицу G(xl) к виду

G ^ ) = L iD iL l

где Li —невырожденная нижняя треугольная матрица, Д — диаго­ нальная матрица.

2. Если все диагональные элементы матрицы Д положительны, то берем

Si = - e r V ^ / C z 4)3 .

3. Если некоторые диагональные элементы матрицы Д отри­ цательны, то решаем уравнение L \t = сц, где сц — вектор-столбец, j -я компонента которого равна нулю, когда j- й диагональный эле­ мент матрицы Д больше нуля, и равна единице, когда j -й диаго­ нальный элемент матрицы Di не больше нуля. Положим Sj = t при iTV/(x*) ^ 0 и Si = —t в остальных случаях. Отметим, что Si удо­ влетворяет условию (1.22).

4. Если все диагональные элементы матрицы Di неотрицатель­ ны и по крайней мере один из них равен нулю, выбираем s по фор­ муле (1.23) или (1.24).

Пример 1. Минимизировать функцию

/(х ) = 100(х2 —X])2 + (1 —xi)2 + 90(х4	—х2)2 + (1 —хз)2 +
+ 10,1 [(хд - I)2 + (Х4 -	I)2] + 19,8(х2 - 1)(х4 - 1).
Теоретическое решение следующее:
х* = (1 0,10,10,10)т,	/(х*) = 0.