книги / Математические методы принятия решений
..pdf1. Градиентный метод. Численным методом безусловной ми нимизации функций является градиентный метод с алгоритмом
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. |