Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 50
Текст из файла (страница 50)
(28) С=и+! Рассуждая так же, как в примере 9,4, нетрудно убедиться в том, что для рассматриваемой задачи выполнены условия !) — 3) теоремы 1. Если функции р (!), А(Г), а(!) удовлетворяют условию 4) теоремы 1 при р=о=2 и, кроме того, о (!) непрерывна и !нп о(!)= ! со !пп а(!) А(!)сс х(!)=О, то траектория и(!) системы дифферен! со циальных уравнений (28) при любом начальном условии и(0)=ио сходится к точке и гя У„)и„,",=!п( !и Р и,' 9 11.
Итеративная регуляризация метода условного градиента 1. Рассмотрим задачу: минимизировать функцию г'(и) на множестве У = (и: и ен У,; й ! (и) < О, ! = 1, т, сгг(и) =О, !=т+1, з), (1) где Уа — выпуклое замкнутое ограниченное множество нз гильбертова пространства Н; функции г'(и), дх(и), ..., сг,(и) определены на его и принадлежат классу Сх(уе). Пусть 969 вместо точных значений этих функций известны нх приближения .)»(и), ды(и), ..., д,»(и) ~ С»(У»), (! =1, 2, ...
Составим функции Тихонова с приближенными данными У» (и) = у»У» (и)+ Р» (и) -~-у»а»!и!', и ~ У„(2) и с точными данными (у»(и)=у»,7(и)-гР(и)+у»а»!!и)», и еп(I„(3) где у»)0, а»~0, !ип а»=!пп у„=О, т $ Р»(и) = ~ ! и!ах(0; дм(и)) !'»+ ~ !дм(и),!», Г= ! ! = м -!- ! Р(и)= ~ /гпах(0; у!(и)) !»+ ' У !до(и)!», Р)1. ~=я-ь ! Заметим, что если функции (2), (3) поделим на у» и обозначим А» = у»', то придем к функциям Тихонова, рассмотренным в предыдущих параграфах. Итеративная регуляризация метода условного градиента заключается в том, что к каждой из функций У» (и) применяют один шаг этого метода, а затем переходят к следующей функции А!»,,(и), иен(/о. А именно, пусть о,— произвольная точка нз У,. Пусть (г-е приближение о енто уже известно. В качестве следующего приближения в»!, примем о»»! = о» + ()» (Ỡ— о»), (4) где оы (!» определяются из условий (65] р»е(У» (7!7»(о») о» о»)( !п! (Аг»(о»), и — о»)+е», (5) иапо, 0 6» 1, Ж» (о»»!) ( !п1 А! (о -)-6 (г — о )) ! 6 (6) »<а<! а» О.
6»--0, (г=1, 2 ..., 1цп е»= 1!гп 6»=0. Отметим, что при сделанных предположениях относительно исходных данных задачи нижние грани в (5), (6) достигаются. Покажем, что при определенных условиях на исходные данкые и согласованном изменении параметров метода (4) — (6) последовательность (и») по корме Н сходизся к точке минимума с наименьшей нормой. Теоп ем а 1. Пусть: 1) (7» — пь!пуклоезамкнуопоеограниченное множгство из гильбгртозп пространства Н; 270 функции г(и), ут(и), ..., д,(и)в=С'(Уо) и их градиенты Г(и), дт(и) таковы, что !!Г (и) — 7'(о)(==.Е(и — о!!, 1Р'(и) — Р'(и) (Е,)и — о1 (7) при всех и, о гн(7„Е=сопз(; функции г (и), д!(и), !'=1, т, !д!(и) !, ! =т+1, в, выпуклы на Уо; 2) функция Лагранжа 5 7.
(и, )) =-,/(и)+ У,' )чу!(и) имеет седловую точку в смьсле !=! неравенств (8.33); 3) функции 7»(и), дт»(и),, у, (и) г= г-:Ст(У») и таковы, что (г'(и) — д»(и) ! т!», ! Р(и) — Р»(и) !(т)», и г=(/о, (8) ! г" (и) — г'»(и) !!( ~», /! Р' (и) — Р» (и) (( в», и яро (9) где т)»)0, $»=-0, !о=1, 2, ..., 1!тп т)»= 1'пп в»=0; 4) по:ледоватгльности (а»!т, (у»), (6»), (г»), (т)»), Я») из (2), (5), (6), (8), (9) таковы, что а»)а»„, у»-=у„, 1!тп а,у» !о=ос, у=р(р — 1) ', (!0) а»у„— а» ту»,! .=.
Со (у» — у»т!)' (11) у» — у».,т+т!»+~»+г»+6»-=.С»й ", 0(р<1; (12) у»а»---Ст)г-', 0 <о (р; ~', (6»+т!») < со, (13) »=! где Со, фѻ — какие-либо положительныг постоянные. Тогда !цп (и, — и„!!=О, где и„АУ„, )ио)!= !п1 (и!. » ю и, Доказательство. Заметим, что при любомфиксированном р, 0 ( р ( 1, существуют последовательности (а») (у») (6»), (г»), (т)»), (з») удовлетворяющие всем условиям (10) — (13), Эти последовательности можно, например, взять в виде а, = )г-", у» = /г-т, 6 = н-о, г = )т-о, Ч» = А " в» = 'г о, )г = 1, 2,..., где у — произвольное число, удовлетворяющее условиям 0 < у < р при 0 < р ( 1!2 илн 2р — 1(у<р при 1!2<р(1; а берется из неравенств 0(а<пни(р — у; у(т) — !)); г= В=2р; в качестве т) и 6 можно взять любые числа, лишь бы т! ) тпах (1; 2р), 6 ) гпах (1; 2р); тогда в (13) = (а+ у+р)/2.
В силу теоремы 1.3.6 7, = !п1 7 (и) ) — со, У, = и = (и: иена, г (и) = г'„) чь ф, а из теоремы 1.3.8 следует 271 существование и единственность нормального решения и„: (и„(=1п1!!и(. В дальнейшем наряду с (о») нам понаи. добится последовательность (и,), определяемая условиями и„~ У„Ж,. (и„) =!и! М„(и), й = 1, 2, ...; (14) и, из теоремы !.3.8 следует существование и единственность и, прн каждом )т=1, 2, ... Из теоремы 8.2 при б»=з»=;»=-О, А»=-у»' вы.екает 1пп !!и» вЂ” из =О.
Тогда, » со как следует из неравенства (о» вЂ” и,! ==.(и» вЂ” и»!!+ ~и» вЂ” и (, для доказательства теоремы достаточно получить равенство !1ш '~и» вЂ” и»!!=О. (15) По условию множество Уз ограничено, так что зпр и(()7<ос., зцр (и — о(=0<со. (16) и, з, з~и~ Отсюда и из условий (7) с помощью леммы 1.2.1 имеем: ! з' (и) ! == !,7 (от) !+ ! з" (от) ! ,'! и — оз (+ Е 1 и — оз )з) 2 ( ( ! у (о) !+ д 1 У' (о) (+ Ег(з) 2 == Сз, т. е ьцр ! У(и) ! =.Сз, (17) и.
здесь и ниже через С; обозначаются положительные постоянные, не зависящие от и, Й. Тогда из оценки (8) следует зцр! з»(и) ((зцр ! з'(и) (+т!»( и. и. (Сз+зцР т!»=Си А=1, 2, ... (!8) »)1 Аналогично доказывается, что шах)ьцр!Р(и)!; зцр!Р»(и)(~(С„1=1, 2, ... (19) 1оа У, Из (1б) — (19) имеем птах)знр(У»(и)!; зцр!Ш»(и)!~~С„й=1, 2, ... (20) ти, и, Далее, из условий (8), (9) следует, что Р (и) — А(»(иН-у»1-'т !»-Ст9 ° (21) 3 Ф» (и) — У» (и) ( ~ у» а» + В» ( Ста», а из (11), (16), (17) ( У» (и) — У»„(и) ~ ( (у» — у»„) / у (и) ~+ + (у»а» — у»„а».,) ) и 1» с С, (у» — у,,) (22) при всех и ~ 0», й= 1, 2, ... Тогда с помощью соо.ношений (16), (21) будем иметь ) У» (и) — У», (и) ~-= ( ~ У» (и) — У, (и) (+ ~ У» (и) — У„, (и) ~+ +,' У ° (и) — У (и) ~ ~ С»(Ч»+) ° )+ +С,(у,— у„,) =-С,(),+ )„,+у,— у„,), и е= ()», й = 1, 2...
(23) Далее, из (7), (16) следует ( У» (и) — У» (о) 1 =. -=. ( У» (и) — У» (и) 1+ ) У» (и) — У» (о) 1+ +1У» (о) — У» (о) 1 2СД»+ С»»(и — о ), и, о е=(/о, й= 1, 2, ... (25) Введем числовую последовательность а» = У» (о,)— — У,(и,), 1= 1, 2, ... Из (14) и (20) имеем 0(а»(2С». Выведем рекуррентное неравенство для а,. Имеем аьм = У»„(о» „,) — У»», (и„») = = (У»м (о»ы) — У» (о»»))+ (У» (о»м) — У. (о».»)1+ + (У» (.„,) — У, (о»))+(У» (о,) — У» (о»))+ + [У» (о») — У» (и»)) + (У» (и,) — У» (и»»»)1+ + (У» (и»»») — У»„(и»,»)1. Заметим, что пятое слагаемое из правой части этого ра- венства есть а», шестое слагаемое неположительно в силу (14), первое и седьмое слагаемые оценим с помощью (22), »73 1У» (и) — У» (о) , '( (у»1.
+ Е+ 2а»у») (и — о)( (С,»(и — о), и, о я У», /г=!, 2, ... (24) Поэтому с учетом оценок (21) из (24) получим второе и четвертое — с помощью (21). В результате 0 ~ а» ! ==- 2С» (уг — уг !) + + 2Сг!)»+ !бг» (гг»,!) — 7»г» (о»)!+ а, « ==. а»+ С!! (7» — у» г+ и») + [)»'» (о»;!) — б)» (о»Н, я=-1, 2, ...
(26) С последним слагает!ым из правой части (26) придстся повозиться. Для него нз (6) имеем оценку бГ»(о».») — бг»(о») =б», 1=1, 2..., (27) Из условия (6), оценок (16), (25) с помощью леммы 1.2.1 имеем б»+ й!» (огг) — У» (о»„) ~ ) Лг» (о,) — 1п1 И» (о»+ (! (о» вЂ” о»)) =- »<в<! ) )!7» (о») — Н» (о»+ й (о» вЂ” о»)) ) ) — н я(гЛ!» (о»), о» вЂ” о») — 2С»»ь» ф — С!»»Р!3»)2, или !ч ( ) — !у (» ) - — ~ (К ( ), — )— — С!»!»г»!г2 С»»»ь» б», й=1, 2, ... (31) 274 Однако ниже нам понадобится более тонкая оценка, чем (27). Для ее получения сначала покажем, что )пп (бг» (о»„) — б!» (о„)) = О. Из (23), (27) имеем ггг» (о» ° ) «йг»(о» 1)+С»(г!»+Ч» 1+7» у»! ) « «б!» (о»)+ б»+ С» (г)гг+»)ггг !+ 7» — Уг,.!), /г = 1, 2, ... (2с) Поскольку [ггг» (о»)) ограничена в силу (20), а ~ [б»+С»(Ч»+т)»-!+7» — 7»-.!)1=:-С» .~, (б»+»)»)+ у! ( »=! гг=- ! «оз, то из леммы 2.3.2 [4) следует существование предела 1!т Ж»(о„).
Тогда !!гп [б)»,г(о»„) — Ж»(о»)! = О. » го » Отсюда и из (23) получим ! У» (о„!) — М» (о,) ! «1)у» (о„!)— — й)»„(о„!) !+! б!»,г(о»„) — гт»(о!) ! — 0 при )г — ~со. Равенство (28) доказано. Далее убедимся в том, что !пп (74» (о»), о» вЂ” о„) '= О. (30) Множество натуральных чисел !с) =-(1, 2, ...) разобьем на два множества Р=(!г: (ген г»г, (дг»(о»), о» вЂ” о,) )0) и (-=Ж" )'. С учетом того, что !п1 (!У;(о,), и — о„) ~ и~о, - (Ф' (о ), о» вЂ” о,) = О, из условия (5) получим О ( ( ( Н; (о,), о„— о„) ( е„для всех гг ~ гс.
Следовательно, если 1 — бесконечное множество, то 1!гп (1»'и(о»), о» вЂ” о,) '=О. », »егс (32) О~а»~(»г»(о») о» вЂ” и») =((у»(о») — дг»(о»), о» вЂ” и»)— — (дг»(о»), и» вЂ” о») (С,г(㻠— (!у»(о»), г,— о„)'-1-е, или — (гу»(о»), 㻠— о») ) ໠— С,Д» — е„, 7г = 1, 2, ... (Зз) Множество натуральных чисел (Ч разделим надва класса: множество тех гг ~ (ч', для которых а, ) С,Д»+г», обозначим через 7„а множество тех !ге= 5(, для которых а,— = С,Д„+г», — через 1,. Из (33) следует, что 1» с= /-. Так как О==а»( 2С,, то из (ЗЗ) для всех lг ~1, имеем ! (гсг» (о»), '» — о») ! = а»» — 2 (С»Д»+ е») 2С, == ໠— См (с»+ е,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
