Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 14
Текст из файла (страница 14)
Один шаг метода скорейшего спуска (4), (5) применительно к задаче (1) — (3) при 0=1.»[ю„Т! описан. Приведем теорему сходимости метода скорейшего спуска, представляющую собой обобщение теорем 5.1.1— 5.!.3 из [41 на случай гильбертовых пространств. Здесь мы ограничимся рассмотрением варианта (4), (5). Теорема 1. Пусть ю[лункю(ия /(и) определенанаеильбертовом пространстве Н, д(и) я С" (Н), д = !п! /(и)) и ~ — со. П!юсть (и») — последовательность, полученная методолю (4), (5) при некотором начальном приближении и»енН.
Тогда последовательность (/(и,)', монотонно убьювает и (9) !пп (,ю'(и»)ю=О. » со 70 Если, кроме того, функция 7 (и) выпукла на Н и»сножество М(и,) =с,и ен 1/: 1(и)«У(ио)) огранич.но, то последоеательность си») минимизирует зту функцию на Н и слабо в Н сходится к множеству (с'о, причем справедлива оценка скорости сходимости 0 = о'(и») — 7 «с,сн, сс=!, 2, ..., с,=сопз1з:О. (10) Если функция г'(и) есце и сильно выпукла на Н, то (и») сходится к единственной точке минимума и по норме Н, причем 0«2(и») — (о «(У (ио) — )о) У», ! и» вЂ” ио ,'~о (2с!») (7(ио) — У ) у» (с = 0 1 где д=! — р)Ь, О==с)(1, р)0 — постоянная из теоремьс 2.2.
Д о к а з а т е л ь с т в о. Справедливо неравенство ,) (и») — У (сс»ы) )!7(2Е.) ( Г (и») 1», (с = О, 1, ..., (1!) которое доказывается точно так же, как неравенство (5.1.12) из [4). Отсюда следует монотонность и сходимость (У(и»)), а также равенство (9). Далее с учетом выпуклости 7(и) рассуждая так же, как при доказательстве оценки (5.!.!5) из [4), устанавливаем, что О « а» =,У (и») — Уо « с(;~,l'(и»),'~, )с = О, 1, ..., (12) где с(= зцр [и — о( — диаметр множества М (и,). и, оем сии Отсюда и из (9) следует, что последовательность ',и») минимизирует г'(и) на Н.
Поскольку (и„) ~М(и,), то согласно теореме 3.7 (и») сходится к сс' слабо в Н. Из (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знО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
