XIV Аттетков и др. Методы оптимизации (1081420), страница 52
Текст из файла (страница 52)
НИСЛЕННЪ|Е МЕТОДЪ| Несложно проверить, что точка у = Рп(х) является проекцией точки х ф Й* на полупространство Й* = (я е Б'."; (и, я) < Ь), (8.24) так как она для всех я Е Й* удовлетворяет неравенству (8.19). Лемма 8.1. Если ранг матрицы А равен количеству ее т строк, то квадратная матрица АА невырожденнэл. т ~ Предположим противное: матрица АА вырожденная и сут ществует такой ненулевой вектор у Е К, что АА у = О. Тогда получим у АА у= (А у) А у= (А у, А у) = ~А у~э =О, откуда А у = О. Но система линейных уравнений А у = О не имеет т ненулевых решений, поскольку ранг матрицы А системы равен количеству столбцов матрицы [Ш). > Пример 8.5. Найдем проекцию точки и е Кв на множество Й = 1я Е К": (пъ я) = Ь„| = 1, нч ), которое является замкнутым и выпуклым (см.
3.1). Примем, что единичные нормальные векторы и, линейно независимы, причем пн < ц (если т = и, то множество Й состоит из одной точки). Искомун> проекцию представим в виде и = Рп(а) = а+ ~) Л|п;, Л,, Е К. (8.25) Из условия у е Й получим систему линейных алгебраических уравнений (С,ЛАУ) т ,'~ Л„(пь,п,)=Ь,— (ти;.,х), 1=1,тв., (8.26) ы= для нахождения коэффициентов Лы й = 1,пп При линейно независимых векторах пь определитель этой СЛАУ отличен 8.3. Проектирование точки на множество от нуля, так что она однозначно разрешима относительно коэффициентов Л,.
Для этого решения подстановка (8.25) в (8.19) с учетом (8.26) дает ти т со (я — у, а — у) = — ~Л,,(я — х, и) +~~ Л,~Ля(пы и) = в=1 г=1 й=ч 1И т =-'~'Л,(6,— (ж.,п,))+У Л;(Ь,— (и;,ж)) =О,. ~=1 в=1 т.е. неравенство (8.19) выполнено для любых я Е й. Пусть векторы по г' = 1, тп, являются строками прямоугольной матрицы А размера ти х и. Тогда систему (8.26) можно записать в виде АА Л = Ь вЂ” Аа, где Л = (Л1 ... Л,„,), Ь = т = (61 ... 6,„) . Так как строки матрицы А линейно незанят симы, то, согласно лемме 8.1, матрица АА невырождена. Поэтому Л = (АА ) '(Ь вЂ” Аж), а у = Рн(а) = а — А (АА ) '(Ав — Ь).
(8.27) Пример 8.6. Если допустимое множество является аьмерным параллелепипедом 11 = (а Е Ки: а, < и < Ьп у = 1, и ), где а,. и 6 -. заданные числа, то координаты проекции у = = (ун ..., ун) т. й точки а = (хм ...., ни) е ~Я'." на множество й можно представить в виде аа, нй <аб и., и.<х <6; Ьз, х, >6., 1 = 1, и. Тогда для координат любой точки я = (нн ..., ьн) Е й справед- ливы неравенства (и. — у )(и — у ) < О, у = 1, и. Суммируя эти неравенства по у' от 1 до и и учитывая формулу для стандарт- ного скалярного произведения в К", приходим к (8.19). 362 8. ЧИСа|ЕННЪ|Е МЕТОДЫ 8.4. Метод проекции точки на множество Сочетание метода градиентного спуска, используемого при безусловной минимизации целевой функции, и операции проектирования точки на допустимое множество й составляет существо льепаода проекции точки на льножесгпво, применяемого для решения общей задачи (8.18) нелинейного программирования.
Такое сочетание позволяет на каждой й-й итерации обеспечивать соблюдение ограничений, задающих множество й. При этом элементы релансационной последовательности (х ) находят из рекуррентного соотношения х =Ро(х +ньго~) =Рн(х ), .ь 61ч, нь ) О, (8.28) где хь = х~ ~ + него" — точка, используемая в обычном методе градиентного спуска, гоь = — йгас11в(хь ') — вычисленный в точке х~ ' Е Й (на первой итерации — в выбранной начальной точке х Е Й) аньпиградиент целевой функции А(х), х Е РЦ), дифференцируемой в ее области определения Р((), а выбор значения ня определен используемым вариантом метода градиентного спуска.
Таким образом, на каждой ь-й итерации в качестве следующего приближения к точке х* минимума целевой функции в соответствии с (8.28) берут проекцию хь = = Рн(х ) Е Й точки х на допустимое множество Й. Если й .. замкнутое вьгоуклое множество, то проекцию х~ = Рп(х ) е Й можно найти непосредственно минимизацией на множестве й квадратичной функции Фь(г) = — нь(г — х, го ), г Е Й. ь-ь~г ь-! ь В самом деле, эта функция является сильно выпуклой (см.
пример 3.14), а значит, и просто вьтуклой Она, согласно теореме 3.15, достигает минимума в точке х Е Й тогда и только тогда, когда выполнено неравенство (8гас1Фь(х ), г — х~) ) О. 8.4. Метод проекции точки кв множество В данном случае ятас1 Фь(г) = я — х~ 1 — тсью" и поэтому О < (8тас1Фь(х~), я — хв) = (х~ — хь 1 — всыпь, я — х~) = = — (х~ — х~, я — х ).
(8.29) Сравнивая с (8.19), убеждаемся, что точка хь минимума функции Ф~(а) на множестве Й является проекцией точки х~ = = х~ 1+ тсьюь на это множество. Различные варианты метода проекции градиента связаны со способами выбора значения гсь в (8.28), пропорционального шагу спуска в направлении антиградиента ю~. Например, этот выбор можно провести, исходя из условия исчерпывающего спуски в направлении вектора ю" или же,. задавшись некоторым исходным значением тсо ) О, при необходимости на каждой Й-й итерации уменьшать его до приемлемого значения ны гарантирующего сходимость последовательности (х 1 к ись комому решению., т.е.
использовать метод дробления ищга. Критерием прекращения поиска точки х* Е Й минимума целевой функции на допустимом множестве Й с ж!в при применении метода проекции градиента служат те же условия вида (4.18) и (4.19), что и в случае безусловной минимизации. На примере решения задачи (8.1) опишем подробнее последовательность действий при выполнении Й-й итерации варианта этого метода, в котором используется исчерпывающий спуск в направлении антиградиснта ю~. Примем, что допустимоо множество Й задано ограничением д(х) = О типа равенства, где д(х) —.— функция, дифференцируемая на множестве Й". Графическая иллюстрация Й-й итерации в двумерном случае представлена на рис.
8.8. Здесь Й есть множество точек плоской гладкой кривой Г, заданной уравнением д(х) = О. Пусть хь ' е Й точка, найденная на предшествующей, (Й вЂ” 1)-й итерации (на первой итерации, Й = 1, она является выбранной начальной точкой хо е Й). После вычисления антиградиента ю~ = — 8гас1 Д(х~ 1) в точке х~ 1, ортогонального линии УРовнЯ 1о(х) = 1о(х~ ) целевой фУнкции Д(х), пРовеДем 8. ЧИСЛЕННЫЕ' МЕТОДЫ я(х)=дв0 (я)=0 Рис.
8.8 исчерпывающий спуск в направлении антиградиента до точки х~ касания прямой спуска с линией уровня ~в(х) = Тв(х~) (см. рис. 8.8). Поскольку д(х") = 4 у'= О, то ограничение типа равенства, задающее допустимое множество й, нарушено. Для завершения в-й итерации и нахождения точки х~ необходимо спроектировать точку х~ на множество й. В данном случае это означает, что нужно найти точку плоской кривой Г, наименее удаленную от точки х~. Так как функция д(х) дифференцируема, то можно доказать, что точка х~ будет основанием кратчайшего перпендикуляра, опущенного из точки х на кривую Г (см.
рис. 8.8). Отметим, что проекция точки х~ на кривую Г в общем случае может быть не единственной. Аналогичную последовательность действий можно выбрать и в случае, когда допустимое множество й задано оервничвнивм типа неравенства д(х) < О, где функция д(х) дифференцируема в К". На рис. 8.8 это множество - . часть плоскости, ограниченная кривой Г, которая описывается уравнением д(х) = О.
При д(хь) = д ) О имеем х~ ф й, так что геометрически проекция точки х~ на множество й снова является основанием кратчайшего перпендикуляра, опущенного из этой точки на кривую Г. Рассмотрим условия сходимости последовательности (х~Т. Теорема 8.1. Если й замкнутое выпуклое множество, а ЦелеваЯ фУнкЦиЯ Тв(х) на этом множестве огРаничена снизУ, непрерывно дифференцируема и для любых х., у е й удовлетво- 8.4. Метод проекции точки на множество ряет условию ~8гас1Уо(х) — 8гас1~о(УИ < Х~х — У~, А > О., (8.30) то при любой начальной точке х~ Е Й для релаксационной последовательности 1х~1, построенной по формуле (8.28), где О < ео < хе < , е > О, верно равенство 1пп ~х" ' — ха~ = Ьд-2е ' Ь-чее = О.
Если при этом множество Хо = 1х Е Й; 4'е(х) < Д(х~)) ограничено, то такая последовательность имеет хотя бы одну предельную точку х*, в которой для любых х Е Й выполнено неравенство (8гас1,~а(х*), х — х*) > О. (8.31) ~ В силу леммы 4.4 из неравенства (4.26) при х =Хи ' и у =Ха имеем Ы,х" ) — 4"о(,х ) > (8гас14о(х '),. х ' — х ')— — — — — 18.32) 2 Из равенства (8.28) при ю~ = — 8гас1Яхь -') и свойств операции проектирования точки на множество (см. 8.3) вытекает, что для любой точки х Е Й 1 (8гас1Ях~ ').,х — х ) > — (х~ ' — х~,х — х ), аЕЫ. (8.33) жь Отсюда при х = х" 1 и иь < 2/(А+ 2е) получим ,ь — 1 .а~2 (8гас14е1х ), х — х ) ) )) )~ — + е) ~х — х тсь Подставляя это неравенство в (8.32), находим А(х~ 1) — А(х~) > е~х~ ' — хь~, х Е Й,.
й Е 1Ч. (8.34) Так как последовательность 1х~) является релаксационной, т.е. 4е(х~) < Яха '), то последовательность 1Д(хь)) невозрастающая и ограничена снизу в силу ограниченности снизу функции 1о1х) на множестве Й. Согласно признаку Вейер- 8. ЧИСЛЕННЫЕ' МЕТОДЫ штрасса сходимости монотонной ограниченной последовательности ~Ц, послеДовательность (Тв(х~)) схоДитсЯ к некотоРомУ конечному пределу 1„> — оо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
