XIV Аттетков и др. Методы оптимизации (1081420), страница 54
Текст из файла (страница 54)
Применим теорему 8.2 для поиска минимума 1 кваДРатичной фУнкции Тв(х) = — Ях, х) с положительно опРе- 2 деленной матрицей Я порядка и на множестве Й вида (8.37). Так как в данном случае 8гай Тв(х) = Цх, то в соответствии с (8.44) и (8.45) можно записать 8г Мр) = Р*Ях" +7*И). Из условия 8гаЛу(у*) = 0 получим С,ЛАУ о (8.49) которой должна удовлетворять стационарная точка у* функции ~р(р) (8 АЗ) . Остановимся на частном случае функции двух переменных.
Пусть Те(х) = )а(х1,тз) = х~1+ х~з, а допустимое множество задано одним ограничением хз = 2. Тогда 0 2 т а в (8.37) т = 1, а~ = (О 1) и 6~ = 2. Ограничению типа равенства удовлетворяет, например, точка х = (2, 2), лежащая на прямой, задаваемой уравнением 1а1, х) = 2, или хз = 2. В данном случае имеем А = о1 — — 10 1), АА = а~ а~ = ~а1~~ = 1 и Р=А (АА ) 1А= 1 (01)= 0 1 О 1 О 0 '" =(' ")(' ') (' ') =(' ') 0 0 0 2 2 0 375 8.5. Метод яроеацяя аятяградяеята Тогда СЛАУ (8.49) относительно координат точки у* = (у,*, уг) принимает вид или 2у1+О у~ — — — 4 и О у1+О у~ — — О. Из первого уравнения находим у1 — — — 2, а второму уравнению удовлетворяет произвольное значение у,*.
Используя (8.46), получаем Таким образом, х* = (О, 2) и 1е(х*) = 4. Эта точка минимума функции 7о(х) на множестве Й точек прямой с уравнением хг = = 2,так как функция строго выпуклая. Полученный результат очевиден с геометрической точки зрения: х* = (О, 2) является точкой касания прямой хг = 2 и линии УРовнЯ уо(хмхг) = х1+ хг = 4 целевой функции (рис. 8.10). Для поиска стационарной точки у* Е Й функции у(у) можно использовать численные методы (см. 4.-6). В частности, можно применить один из вариантов метода градиентного спуска. Однако при решении прикладных задач иногда удобнее минимизировать исходную целевую функцию 7о(х), поскольку координаты точки х Е Иа являются параметрами оптимизации и имеют вполне определенную содержательную интерпретацию.
Рассмотрим процедуру поиска минимума дифференцируемой целевой функции Ях) на множестве Й (8.37). Выберем начальную точку х Е Й, вычислим в этой точке антиградиент ао~ = — 8гае17о(хе) и антиградиент р1 = Р*ао функции р(у) в 8. ЧИСЛЕННЫЕ' МЕТОДЫ точке у = ы1. Если р' = О, то градиент функции у(у) в точке ы равен нулевому вектору, т.е. ы = у* — стационарная точка этой функции, а в силу теоремы 8.2 хс точка, удовлетворяющая необходимому условию минимума целевой функции на множестве Й (для выпуклой целевой функции х — точка ее наименьшего значения на Й).
При численном решении целесообразно считать у = ы1 стационарной точкой функции д(у) при выполнении условия, аналогичного (4.19): ~р ( < ез, где ез > 0 — поуомегпр точности поиска. Если ~р1~ > ез, то вектор р' определяет направление спуска для функции у(у) при ее безусловной минимизации. По этот жс вектор задаст возможное направление спуска для целевой функции, если в соответствии с (8.45) для первой (й = 1) итерации записать х1= хе+и Р*ы'=хо+н1р~ м1 >О. (8.50) Действительно, точка х' принадлежит множеству Й при любом значении нм так как, учитывая равенства (пь Р'ы) = О,.
г = 1, т, для лн)бого вектора ы' имеем (апх ) =(аьх~)+(а;, Р'ы') = (аьх~) =Ь, г'=1,пь Поскольку с учетом равенств (8.39) и (8.40) (р', ягадУо(х )) = — (Р'ы', ы') = — ((Р*) ы', ы') = вектор р задает направление спуска и для целевой функции, в котором ее значение уменьшается. Значение н~ в (8.50) можно найти при помощи исчерпывающего спуска в направлении р~ или методом дробления шага, задаваясь некоторым первоначальным значением мс и при необходимости уменьшая его так, чтобы добиться выполнения неРавенства Тс(х ) < Ях~).
Это позволит начать фоРмиРовать релаксаиионную последоеагпельность 1хя). 377 8.5. Метод проекции внтигрвдиеята После нахождения при помощи (8.50) точки хт переходим ко второй итерации и т.д. Пусть на й-й итерации известна точка х~ ' Е Й. Вычисляя в этой точке антиградиент от~ = = — 8гат1Ях~ '), находим возможное направленно спуска р~ = = Р'то~, при движении в котором (если ~р ~ > вз) ищем точку хн = ха '+ньР'то~ =х" '+ттьр"', тть > О, (8.51) подбирая соответствующим образом значение ны Как и в случае х, можно показать, что х Е Й при любом значении тть. 1 ь Поэтому можно переходить к следующей, (й+1)-й итерации. Если же ~р ~ < вз, то итерации прекращаем, полагая пт' = пт ' и ь ь ,ь — 1 Поскольку на каждой й-й итерации вектор р является проекцией антиградиента тв целевой функции на ортогональное дополнение подпространства Ег,то описанную процедуру поиска минимума этой функции на множестве Й назовем метподом проекции антпиерадиентпа.
Общий случай линейных ограничений. Пусть задача оптимизации содержит линейные озранинсния типа неравенстпва и равенства. В этом случае допустимое множество можно записать в виде Й=1хЕЖ":(а„х)(б,„гЕХ, (а;,х)=5, гбао ), (852) где Х и Х~ .-. конечные множества индексов. Множество Й (8.52), согласно замечанию 7.1, является выпуклым. Предположим, что на й-й итерации точка х удовлетворяет ть Е И равенствам (ан х~ 1) — 5, = О, г Е,4ы где 7ь С Х = Х 0 Хв некоторое подмножество множества Х индексов всех векторов а, Е 1т:.
в (8.52), пРичем Хв С,Уь, Составим матрицу Аь размера тив х и, строками которой т слУжат матРицы-стРоки а,, г Е,7ь. Если В.8Аь = тов < п, то в т силу леммы 8.1 матрица АяАя невырожденная и можно опредет т лить квадратные проекционные матрицы Рв = Аь(АяАь) Аь и Р' = 1, — Рл порядка п. 378 8.
НИСЛЕННЫЕ МЕТОДЫ После вычисления антиградиента юь = — 8гас1 То(вь ~) целевой функции 1о(а) в точке а Е й находим р =Рею'. ь * ь (8.53) 6,> (а;,а +нью ) =(а;,ж )+мь(аою ), 1ЕХ . Отсюда видно, что при (аб юг) > О выбор нь > О ограничен значением (6,; — (а О а ) ) / (а;, ю ), иначе ограничение с этим индексом будет нарушено.
С учетом всех ограничений типа неравенства, для которых (а;, ю") > О, получим йь = ппл ', Х+ = (гсов: (аб ю ') > О). (8.54) 6; — (амх~ ~) 'сто (аь ю~) Отметим, что в частном случае в (8.52) могут отсутствовать ограничения типа равенства, т.е. множество Х индексов пусто. Тогда возможна ситуация, при которой на й-й итерации все ограничения птипа неравенсгаеа не являются антанвнымн. При этом ть = О, т.е. пусто и множество,71, а ж ' — внутренняя ь — 1 точка множества й, для которой (а;, жь ~) (6; при всех 1еХ В этом случае полагаем, что Р* совпадает с единичной матрицей 1о порядка по а в (8.53) рь = ю~.
для внутренней точки антиградиент ю ' задает возможное направление спуска, по которому на этой итерации можно двигаться вплоть до границы дй выпуклого множества й (на -ь рис. 8.11 такая ситуация показа/ на на плоскости). Чтобы найти точку а б дй, в выражения для ограничений типа неравенства в (8.52) подставим ж = а" из (8.51) Рис.
8.11 при Р* = 1: при 379 8.5. Метод нроекции антитрадиента После вычшления аея следует выбрать такое значение аеа Е 6 (О. аеа), которому соответствует точка х" = х~ 1+ аеато~, обеспечивающая возможно меньшее значение 7е(х~) ( Ях" ') целевой функции. Отметим, что можно выбрать аеа = аею т.е. на пересечении направления антиградиента ти и гиперплоскостей, для которых отношение 6,— (а;,х~ 1) (а;, ита) в (8.54) оказалось наименьшим.
х~ = х~' " + теаит" Е Й (см. рис. 8 что Уо(х ) > Уо(х ). Пусть Я, ф О. Если ~ра~ > ез возможное направление спуска. аленин не будут нарушены ограничения типа равенства и активные ограничения типа неравенства, но опять возникает опасность нарушения ограничений, которые в точке х не являются активными (на рис. 8.12 эта ситуация изображена на плоскости Кз при одном активном и двух неактивных ограничениях в точке х" '). Поэтому аналогично (8.54) вычисляем предельно допустимое для аеа значение В результате найдем точку 11).
Но при этом возможно. > О, то вектор р определяет При движении в этом напра- Рис. 8.12 — 7-е ( Е2 —. ( ) >О) (855) 5; — (а„ха 1) ге.та (ан Р ) и затем в (8.51) подбираем аеа Е (О, аеа] так, чтобы получить возможно меньшее значение ях ) ( яха ) целевой функции. После выбора значения аеа и нахождения точки х~ можно переходить к следующей, (й+ 1)-й итерации. 380 3. ЧИСЛЕННЫЕ Х|ЕТОДЪ| Л = (АяАь) 'Аьыь е Б'. ', (8.56) координаты Л;, 1 Е,7, которого являются множителями,Ла- 00 гранжа в функции Лагранжа Хь(в, Л) = 7я(в) + ~~ Л, ((а,, т) — 5|).
(8.57) Если Л, ) 0 длЯ всех 1 Е,7я '1Х, т.е. длЯ всех активных огРани- 60 о чений типа неравенства, то, согласно теореме 7.6, это означает, что точку х" ' можно приближенно считать стационарной точкой функции Лагранжа (8.57) и можно положить и* .вы. Но если найдутся индексы г 6,7я 1,1, для которых Л, ( О, то один о Ф) из них (обозначим его у) следует удалить из множества,7я и для нового множества 7я =,7я 1 Я индексов найти проекционную матрицу Р„'размера (ть — 1) х п. Если при этом Д = Я, т.е.
|и| — 1 = 0, то Р„' =1„. Покажем, что новый вектор р = Рг)и~в ф О и определяет возможное направление спуска на к-й итерации. Этот вектор можно представить в виде рв = ю" — А, Л", где ЛЯ = (АьА ) |Ария и Ая — матрица размера (~пь — 1) х и, состоящая из матрицт строк а,, 1 Е Я,. Аналогично для вектора р" = 0 с учетом (8.56) имеем р = Р~и|~ =ив — АьЛ = и~ — Л~~ ~а — ~~~ Л~ '1а, = О. (8.58) |ЕЛ т ь Об Предположим, что рЯ=О, откуда ге~=А, Л~ = 1 Л, аь ПодгеА ставляя гв в (8.58), находим ,') Л, а,— Л~~ а — ~~) Л, а,= — Л 1а + ) (Л, — Л, ~)а,=О, ген„, Если ~рь~ ( сз„то при,7ь = О итерации прекращаем и полагаем и' —,и, а при,Дя у= Я вычисляем вектор 381 8.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
