Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 15
Текст из файла (страница 15)
Из (11) и (12) имеем а»„,— а»)а»с(2Ы»), 7»=0, 1, ... Отсюда и из леммы 2.3.4 из [4) следует оценка (10). Последнее утверждение теоремы для сильно выпуклых функций доказывается точно так же, как это делалось в теореме 5.1.3 из [4). 2. Метод проекции градиента может применяться для приближенного решения задачи У (и) -«! п1; и ен У, (13) где У вЂ” выпуклое замкнутое множество из гильбертова пространства Н, 7 (и) е- =С' ((с). Для описания этого метода нам понадобится понятие проекции точки на множество.
7! Определение 1. Проекцией точки иенН на множество (/с Н называется точка ю ен (/ такая, что )и — щ„= 1п1 )и — о<. аяо Проекцию точки и на множество (/ чзсто обозначают через Ро (и). Теорема 2. Пусть 1/ — выпуклое замкнутое множество из Н. Тогда 1) всякая точка иенН имеет, и притом единственную, проекцию на вто множество; 2) для того чтобы точка ю ен 1/ была проекцией точки и на множество (/, необходимо и достапючно выполнение неравенства (го — и, о — гс))О при всех оен(/; 3) справедливо нерпвенство )Ро(и) — Ри(о)((!и — о! при всех и, ос-=Н. Доказательство этой теоремы проводится дослови о так же, как и доказательство аналогичных теорем 4,4.1, 4.4.2 из (4). С помощью оператора проектирования можно сформулировать условия оптимальности в задаче (13) следующим образом.
Теорема 3. Пусть (/ — вьтуклое зал~кнутов множество из Н, /(и) С'(!/) ипусть(/„,Фф. Если и, ~(/„ то необходимо вьтолняется равенство и, = Р„(и„— а/' (и,)) при всех а) О. Если, крол1е того, /(и) вьтукла нп (/, то всякая точка и„ен 1/, удовлетсоряюи)пя приведенному равенству, принадлежит множеству (/„. Доказательство этой теоремы полностью совпадает с доказательством аналогичной теоремы 4А.З нэ !4).
Метод проекции градиента для решения задачи (13) заключается в построении последовательности (иь) по правилу иь+,— — Ри(и,— аь/'(ил)), /г=О, !... (14) где аь — положительная величина. Если при некотором й оказалось, что ил„ил, то процесс (14) прекращают. В этом случае согласно теореме 3 точка и, удовлетворяет необходимому условию оптимальности. Для выяснения 72 того, будет ли ид принадлежать ()д, нужно провести дополнительное исследование поведения функции ) (и) в окрестности точки и,. В частности, если /(и) — выпуклая функция, то и» ~ ()„.
Существуют различные способы выбора величины ад в методе (14). Приведем некоторые нз них: 1) ад выбирается из условия 7» (ад) = 1п1 )д (а), )д (а) =,1 (Ри (и„— аР (ид))); а гд О 2) полагают ад=а)0, затем проверяют условие монотонности: ) (и„,) < 1(и,), и при необходимости дробят величину а, добиваясь выполнения условия монотонности; 3) если 7 (и) ев С' '(()) (см. определение 2.5) и константа Липшица 7. для градиента известна, то в (14) в качестве ад можно взять любое число, удовлетворяющее условиям 0<е»=.ад -2Н1.+2е), (15) где е„е — положительные числа, являющиеся параметрами метода; 4) возможен выбор ад из условия ,1 (и,) — 1(Ри(ид — а»Г (ид))) ) е, 'ид — Ри (ид — а»Г (ид)) )д, е) 0 (для определения такого а, можно задать а„=а н затем дробить ад до тех пор, пока не выполнится указанное неравенство); 5) возможно априорное задание величин ад из условий ад) О, /».=-0, 1, ..., ~„" ад=со, ~Ч,' ад»<оо, Заметим, что описанные здесь варианты метода (14) прн 1/=Н переходят в соответствующие варианты градиектного метода.
Методом (14) удобно пользоваться лищь в тех случаях, когда имеется явная формула для проекции точки на множество. Укажем несколько примеров множеств, когда нетрудно получить такую формулу. Проекция точки не= Н на шар Е/=5 (й, Н) =',и ев Н: „'и — й1=--Н) 73 представима в виде ( и+ Я(и — йЯ и — й) при ! и — й ! ) )7, Рс (и) и при )и — и!(Я; проекция на гиперплоскость Г =(и ен Н: (с, и)=у) выражается формулой Ри (и) = и+ (у — (с, и)) сН с !з; если (16) У=(и ен Н: Аи=Ь), где А а=Ж(Н вЂ” э-Н), Ь ен Н, оператор АА* имеет обрат- ный, то проекция точки и ен Н может быть записана в виде Ри (и) и — А* (АА")-'(Аи — Ь).
Приведенные формулы для проекций доказываются так же, как это делалось в примерах 4.4.1 — 4.4.6 из )4). Посмотрим, как выглядит метод проекции градиента для задачи (!) — (3), когда множество 0 имеет вид У = ( и = и (!) = (и' (!), ..., и' (!)) ~ 7.' (С, Т~): а,(!) ~ (и'(!)(~;(Г) почти всюду на (Гр, Т~,!=1 «); (17) здесь а;(!), ()с(!) — заданные функции из В (1„Т7.
Про- екция любой точки и=и(С) =(и'(!), ..., и" (!)) е=Ц(Е, Т1 на это множество представляет собой вектор-функцию Ри(и) (ю~(!), ..., и«(!)), (о(! =Т, где а~ (Г) при и'(!) (а; (!), гас (!) = и' (Г) при ар (!) ( и '(!) = 8с (!), р; (!) при р;(Е) ( и'(т), Е = 1, « (ср. с примером 4.4 5 из [4)). Поэтому (Уг+!)-е прибли- жение и +, (г) =(и'+, (г), ..., и'+, (е)), ! ( г( т, метода проекции градиента для задачи (1) — (3), (17) будет полу- чаться по правилу а,.
(!) при и' (Г) — а (Вт (!) ф(Г, и„)),( (а,. ((), и$ (!) и' (!) — аз (Вт (!) ф((, иД), при ас (() == (18) ~ и' (!) — а„(В т (Г) 'ф (Г, и )), -=. й, (т), )) (!) при и' (!) — а (Вт (!)ф(!, иа)),.) $),(!), г и=[,- ~о ивы~:1~ ° р) — апов~о*) во~ где й=й(() — заданная функция из 1;[(„Т1, Р— задан- ное положительное число, то в силу формулы (16) метод проекции градиента приведет к последовательности, кото- рая строится по правилу ио(Π— аоВ (Оф(б ио) — и(О т )г ~ по (и — и о В г (О 4 (й и о ) — и (О о ш) ио и г пРи ~ !ио(() — аоВг(()оР((, и,) — й(())ой()Р, (18') и и,(() — аоВг(() ф((, и,) пРи ~ ! ио (() — сооВг(!) ф((, ио) — й (())ой((йо, ! ивы(!) = Приведем теорему сходимости метода (!4), (15), обобщающую теоремы 5.2.1, 5.2.2 из [4) на случай гильбертовых пространств.
Т е о р е м а 4. Пусть функция 7 (и) определена на вьтуклом замкнутом множестве У гильбертова пространства Н, г'(и) ~Сп1(У), У,=!п(У(и)) — оо. Пусть (ил[ — последовательность, полученная методом (14), (15) при произвольном начальном приближении ноя У. Тогда последовательность ( г' (ио) ) монотонно убывает и 1!ш(и, — ио,,')=О. Если, кроме того, функция /(и) выпукла на Н и множество М(и,) = [и ~ У: г'(и) =- 3(ио)[ 75 (=1, г; здесь (Вт (()ф((, и,)),— 7-я координата вектора В" (() ф((, и,).
Согласно теореме 2.6 градиент функции (1) удовлетворяет условию Липшица с постоянной Ь = = 2(Т вЂ” (о) Вг„„егл '"'г и). Поэтому при выборе ао в (18) можно воспользоваться условием (15). Однако следует заметить, что указанная выше оценка для ) может оказаться довольно грубой, а это может привести к слишком малым значениям ао из (15) и к слишком медленной сходимости метода проекции градиента. Если в задаче (1) — (3) множество 0 является шаром из Ы[(о Т1, т. е.
ограничено, то последовательность (и„) минимизирует вту функцию на (7 и слабо в Н сходится к множеству (7„, причем справедлива оценка 0 -7(иь) —,7,„(с,/я, у=1, 2, ...; с,=сопз1)0. Если фУнкЦиЯ /(и) еа(е и сильно выпУкла на (7, то (иь) сходится к единственной точке минимума и„по норме Н, причем 1иь — и,~'~с,/А, у=1, 2, ...; с,=сопз1знО. До к а з а тель с т в о. Первое утверждение теоремы вытекает из оценки 7(а„) — 1(илью)е(иь — иь„,(', й=О, 1, 2 „...
которая доказывается так же, как соответствующая оценка (5.2.11) из 141. Доказательство второго утверждения тео- ремы для выпуклых функций полностью аналогично дока- зательству теоремы 5.2.2 из 14] с той лишь разницей, что вместо теоремы 2.1.2 здесь нужно использовать тео- рему 3.7. Утверждения теоремы для сильно выпуклых функций являются следствием предыдущих утверждений и теоремы 3.8. Для сильно выпуклых функций можно предложить другой вариант метода проекции градиента, имеющий бо- лее высокую скорость сходимости 178). Теорема 5. Пусть (7 — вьтуклое замкнутое множе- ство из Н, функция 7(и) принадлежит С" (П) и сильно выпукла на (7 и пусть 0(и(ай-, гдг постоянные р, Е, р=.Е, взяты из определения 2.5 и теоремы 2.2.
Тогда послгдовательность (иь), получаемая из (14) при иь = и, А=О, 1, ..., сходится к точке минимулча и по норме Н, причем справедлива оценка (иь — и„(()иь — и,((д(и))ь, у=О, 1, ..., где у (и) = (1 — 2ри+ иЧ,')"', 0 ( д (и) " 1, Доказательство этой теоремы проводится дословно так же, как и доказательство аналогичной теоремы 5.2.3 из 14).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
