Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 47
Текст из файла (страница 47)
Будем предполагать, что 7„= = !п1,7(и)~ — со, Уе=(и: и еи У, l(и) = У„)чеф и функ- и 5 ция Лагранжа 7. (и, Л)=('Си, и)+,'с, и)+ ~~ Л;((а|, и) — Ь!) |=| имеют седловую точку в смысле условия 2) теоремы 1. Функция з'(и) дифференцируема и ее градиент имеет вид Г(и)=(С+С*) и+с (см. пример 1.2.2). Отсюда следует, что !<У' (и) (!((2(С!!+!<с() (1+(и[), и ен У». Штрафная функция Р(и)= ! — ~ (|пах [(а|, и) — Ь;; О[!'+ — ~~ [(а„ и) — Ь»!~ 1 |= | 1=»е+! и Ф. П. Весел»ее 257 также дифференцируема, и для ее градиента П3 Я Р'(и)= ~|пах ((а„и) — Ь,; 0)аг+ '~ ((аь и) — Ь!)а, |= ! г=т+! имеем оценку 1 Р' (и) ! ( ~ (,' а| 1+ ~ Ь, !) ! а! (1 + ' и !), и ен Уд.
|=! Таким образом, условие (7) теоремы 1 в рассматриваемой задаче выполнено. Пусть вместо точных С, с, аи Ь, известны их приближения С» (С» — линейныи ограниченный оператор), сд, а;ы Ь;„ юг = 1, 2, ..., с погрешностью гпах()С» — С); ';с» — с)„'а!» — а;"й !Ь;» — Ь,!') = а», й = 1, 2, ..., Игп о, = О. Тогда вместо точных г'(и), дг(и)=(аг, и) — Ь! будем иметь дело с их приближениями гд (и)=(Сди, и)+(см и), д|д(и) = =(а;д, и) — Ьм. В качестве приближений для градиентов Г (и), Р' (и) возьмем соответственно l» (и) =(С»+ С») и + с„ Р»(и) =- У |пах ((а;», и) — Ьгд, '0) а|»+ + ~~', ((а|„и!) — Ь!|,) ам, 1=1, 2, Тогда ! )» (и) — Г (и) 1 ( 2од (1 + ! и,") и 1 Р» (и) — Р' (и) 1(,Ъ ' д!» (и) а;д — аг (и) а; ! ~ |=! (,У', ~дгд(и) — й!'(и) ~)ам'+~а'(и),'(а|,— а|г.
|=! С учетом определения (г.5), (8.6) функций г(д(и), д,'»(и) здесь чмеем ~ д!» (и) — и,' (и) ~ ~ ~ й|» (и) — д! (и) ~ < (ад(1+(и!), !д) (и) ~.=()аг!+,,'Ь; ~)(1+;и!!). 3чг) Кроме того, »а!ь,!(!а,(+оь. Поэтому ! Р; (и) — Р' (и),' ~ 5 ==па ~ (2!!а!(+) Ь; ~+о,) (1+!! и!), и ие. г=! Таким образом, в рассматриваемой задаче условия 1) — 3) теоремы 1 выполнены.
Итерационный процесс (6) здесь будет выглядеть так: оа,,=Рщ о, — ра'(С„+С;) о„+с„+ т + А, ~', !пах ((ам, и', — й,а; О) а!а+ !=! 5 ~а, т. (О„, чо-Сь! „<-,.„)), ~=. п-! ! )! = 1, 2, ...; и! е ()а. (42) !. — ф )-а !'ч-з ь ! *!!ч„,! — г;;.с!ь !=! ! +Аа ~, '((аоь о„) — Ига)а)а+и,4~), !-и+ ! 1=1, и, й=!, 2, ...; о,енУо. Упражнения. !. Примени!ь метод (6) нлн (28) к задачам нз примеров !.2 — !.4, 3.1, 3.2, 8.! — 8.4. 2. Применять к задаче (ЗЗ), (34) метод (28), предполагая, что мнол!ество (7 имеет внд (!.4.)7) нлн (!.4.!9). 3.
Применить метод (28) к задаче минимизации функции а'(и)= =)Аи — Ь!й на гнльбертовом пространстве Н, где А — линейный ограннченный оператор, действующий нз Н в Н, а Ь вЂ” злсмснт Н. ! 9* 259 Если величины А,, х,, бь удовлетворяют условиям (8) при р=с) ==", 1!ш о!Азха' =О, то согласно теореме 1 построенная таким образом последовательность (еа) при любом выборе начально!о приближения и! ен Са сходится по норме Н к решении! и. ~ (7„, имеющему минимальную! орму, В частносъ. сслп Н = Е", С =- О, ()с=-,!и = (и', ..., ь'). и! == О, ! = 1, л), то рассматриваемая задача превращается в конечномерную задачу линейного программирования н процесс (42) запишется в следующем виде: 4. Применить метод (6) к задаче лнлейного программнронання нз примера 8.5. 5.
Рассмотреть аозмо:кность прнменення методов (6), 128) к задачам оптимального управления нз 45 !.5 — РЛО $10. Непрерывная регуляризация градиентного метода Как отмечалось в 2 5.1 из [4], для минимизации дифференцируемой функции на всем пространстве Е" может быть использован непрерывный вариант градиентного метода, заключающийся в определении траектории дифференциального уравнения и (()= — Г (и(()), ! ~ О, при некотором начальном условии и (0) = и„. Там же было показано, что для сильно выпуклой функции любая траектория этого дифференциального уравнения минимизирует функцию 2(и) на Е" и сходится к точке минимума (см. теорему 5.1.4 из (4]).
Однако если задача минимизации некорректна в метрике Е", то не всякая минимизирующая траектория будет сходиться к множеству (/е точек минимума /(и) на Е". В этом случае можно попытаться модифицировать непрерывный вариант градиентного метода по аналогии с предыдущим параграфом и получить такое дифференциальное уравнение, траектории которого сходились бы к Уе, или, иначе говоря, провести непрерывную регуляризацию градиентного метода. Следуя 1118], покажем, как это можно сделать для задачи минимизации функции l (и) на множестве (г=]щ ияН, д;(и)~0, (=1, и; д;(и)=0, 1=и+1, з], (1) где л'(и), дт(и), ..., п,(и) — функции, определенные на гильбертовом пространстве Н. В качестве стабилизатора возьмем ь) (и) =1и 1й)2.
Будем предполагать, что вместо точных значений функций l(и), д;(и) нам извсстны лишь их приближения l (и, (), и, (и, (), зависящие от параметра г')О. Введем штрафные функции сл Р(и)= 'У, 'щах ]Ел(и); 0],л+ ~, '~дг(и) ~л, ~=! =-ь. Р(и, ()= У, гнал ',д,(и, 1); 0).а+ )~~,дг(и, ()]л, г=~ =т+! р>1, 1- О. 260 Пусть функции У(и), у;(и) и их приближения )(и, !), у,. (и, !) дифференцируемы по и и пусть погрешности вычисления их градиентов удовлетворяют условиям шах(! Г(и) — )'(и, !) (/; (Р'(и) — Р'(и, Г) !Д « «6(!)(1+(и!), (=-О, ияН, (2) где 6(!) )О, (пп 6(!) =О.
Введем функцию Тихонова Т (и, !)= / (и, !)+. А(!) Р (и, !)+ + 2 а(!)(и,,', и ~Н, (~0, (3) где А(!)) О, а(!)) О, !) О, 11ш А (!) =+ со, )пп а(!) = 1 со ! и =О. При сделанных предположениях эта функция дифференцируема по и, причем ее градиент имеет вид Т'(и, ()=Г(и, !)+А(!)Р'(и, ()+а(!)и, иенН, !)О. (4) Рассмотрим траектории и = и (!) дифференциального уравнения и(!)= — ()(!)Т'(и(!), !), !)О, (5) при произвольном начальном условии и (0) = и„где (1(С) ~0, (гьО, 1(гни (!) =О. Здесь и(!)= 1пп (и((+Л()— с- ы ь — и (!))(Лц и сходимость понимается по норме Н.
Нетрудно видеть, что итерационный процесс (9.6) при Уь= = Н превращается в метод ломаных Эйлера для численного интегрирования уравнения (5). Однако ясно, что для численного решения уравнения (5) могут быть применены и другие, вообще говоря, более точные методы решения задач Коши [2, 32, 153, 193, 194), и это обстоятельство является достоинством рассматриваемого подхода к регуляризации некорректных задач минимизации. Т е о р е м а 1.
Пьсть 1) функции ) (и), д1 (и), ..., у (и), 'д,,(и) 5 ..., >д,(и)! выпукльс и )(и), д,(и), ! =1, в, непрерывно дифференцируеиы но всем гильбертовом пространстсе Н; гродиенты функций ) (и), д; (и) таковы, что шах((,)'(и) 1",, !Р' (и) !) ==(ь(1+: и;), и ц= Н, Т.ь = сопз! -ь 0; (6) 26! множество У, определяемог условиями (1). непусто; ,), = (п! ) (и) ) — схз, У, = (и: и в- =(1,,) (и) = /, ) ~ (у); 2) функция Лагранжа Л(и, Л) = )(и)-(- 'У, 'Лгдг(и), и ~ г=! я(lз=Н, Ля==Го=(Л: Лв-:Е', Л,=-.О, ..., Л )О) на множестве Н хЛ, имеет седловую точку в смысле неравеншпв (8.33); 3) финкции 1(и, 1), д;(и, 1) непрерывно дифференцируемы по и, причем соответствуюи(ие градиенты .1'(и, 1), д,'(гг, 1) измеримы (например, непрерывны) по 1 ни любом конечном отрезк.
(О, Т'1 и при любом фиксированно.н и ~ е=' Н; погрешнпспги удовлгтворягот неравенством (2); 4) функции 6(1), А(1), а(1), р(1) из (2) — (5) непреоывны при 1) 0 и таковы, что 6(1) зв О, А (1) ) О, х(1)) )О, (з(1))0 при всех 1 0; Л(1) вогнута и возраспгоегп, !1пт А(1) =+ сто', а(1) выпукла и убывает, 1(пз а(1)=0; г ' сс г (.О 11 (1) убывает и 1ип (1 (1) = 0; зцр р (1) А (1) (+ со, г со ! саз (нп сз(1) Лч-' (1) =+ схз, где ц= р (р — 1)-г; 1(пт 6(1) = с т с = О, (пп 6(1) А (1)я-'(1) =0; Л (1), а(1) и р(1) имеют ьо непрерывные производные и А(0 !. «(О .
6(О Игп,, ) 6(0 — — (пп оз(1 6 ) — — 1пп йз( ( — — О. Тогда решения дифференциального уравнения (5) при тобом начальном условии и (0) = и, продолжимы на всю числовую полуось (О, +со) и 1(гп ! и(1) — и 1=0, где и ! со в-=Н„и„= 1п((и!. и, Бок а за те.ч ь гтв о. Прежде всего заметим, что функции А(О, а (О, 6 (О, удовлетворяющие условиям теоремы, существуют. Их можно подобрать, например, в виде А (1~ =(1+1) 'Л, и (0=(1+1) 6 У) (1+1) "Р, где А, а, () — натуральные числа, удовлетворяющие неравенствам 2и '+6 '+ А '(1, 6 ~ А, Л (( — 1) а. Существование таких А, а, () очевидно, можно взять сначала 6 достаточно большим, затем А и, наконец, и.
В частности, при р=2 можно взять А(0 1 ге, и(0 Гхгз, 1)(0=1 и условия 11гп 6(0= 1пп 6(цх Г о г со х А (О и ' (0=0 выражают требования к погрешностям в задании производных в соответствии с условиями (21. 262 Рассмотрим точную функцию Тихонова Т(и, 1)/ 2(и)+А(1)]с ! хР(и)+ — и(0 и з; ее градиент по и равен 2 Т'(и, 1)=Г (и)+А(1) Р'(и)+сс(1)и, и ш Н, 1~0 (7) Из (2),,4), (7) имеем ', Т' (ч, 1) — Т'(и, 1) !»(6(1)+ А (1) 6(1)) (! -(-/ и ')» » 6 (1) А (1) ( ! + А г (0)) (! + ! и;) = С„б (1) А (1) (1 +"; и !), 1~0, иеН; (8] чтись и ниже через Сп 1=-0, ], 2, ..., будем обозначать положитель- ные константы, не зависящие от и и 1. /(злее, из (8), (7) следует ! Т' (и, 1),» ' Р (и) + А (1)', Р' (и) "+а (1) ! и,'» » (1 з (! + А (1))+се (1)) (! + ! и,',)» СтА (1) (! +,', и (), (9) ишН, 1~0. Тогда из (8), (9) получим, Т' (щ 1) ! /Т' (и, 1)!]+! Т' (и, 1)— — Т'(и, 1)" »(С,А(1)-+Сьб(1) А(1))(!+(и',,)»СзА(1)(!+;,'и!), так что щвх (6(1) Т' (и, 1)"; б(1], Т'(и, 1) )-- »Сзб (1) А (1) (]+' и")»С,(!+! и,',,), (]О) иш Н, /свО Из выпуклости я;(и), !=1, лм 88(и) й !=и+1, з, следует выпуклость Р (и] при либор р) ! Согласно теореме !.2.1 ГР (и) — у' (с), и — о) О, (Р' (и] — Р' (о), и — о) 0 при всех и, о Й Н.
Позтому из (7) получим (Т'(и, 1) — Т'(о, 1), и — о))а(1) и — о,з, и, оьв Н, 1-0 (!!) Согласно теореме ! 2.2 отсюда следует сальная выпуклость Т(и, 1) по и на Н По теореме ! 3 8 тогда существует, и притом единственнаяя, точка и, (1) ш Н, для которой ! п1 Т ( и, 1) = Т (и „(1], 1), 1 ) О. (!2) Н Наряду с и„(1) рассмотрим еще функции о(1, т), о(1), являющиеся решениями следующих вспомогательных задач Коши: до(1, т] 8! — )](1) Т'(о(1.
т), т), 1)О, тгвО, о(0, т)=из, (!3) б(1)= — )](1) Т'(о(1), 1), 1)0, о(0)=и,. (!4) Заметим, что правые части уравнений (5), (!3), (!4) имеют вяд /(и, 1), где функция /(и, 1) измерима по 1 на любом конечном отрезке !О, Т) при всех фиксированных и ш Н и непрерывна по и на Н для всех 1~0. Кроме того, нз (!0) имеем, что !/(и, 1)!» »С (]+! и !). Отсюда следует, что в случае Н =Е" дифференциальйме уравнения (5), (!3), (!4) при любах! начальном условии па си Еа 253 имеют хотя бы одно решение, определенное на л!сбом конечном отрезке [О, Т[ или, иначе говоря, при всех 1 си 0 — см., например, (49[, стр 217 (в случае, если Н ~ Ев, то будем предполагать существование и продолжнмость на полуось [О, +со) решений зтих уравнений) Наконец заметим, что существование и единственность ()-нормального решения и, задачи минимизации в'(и) на (7 доказывается гак же, как о те,!реме 8 2 или 9 ! Теперь можем напигать неравенство и, — и ( г) ц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
