Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 48
Текст из файла (страница 48)
П р и м е р 4. Рассмотрим задачи квадратичного и линейного программирования; минимизировать функцию l(и)=(Ссс, и)+(с, и) на множестве У=(и: и»= У„(аь и) — Ь! (О, | =-1, т; (аь и) — Ь!=О, |=т+1, з[! где Уе — выпуклое замкнутое множество из гильбертова пространства Н, (а, и,' — скалярное произведение в Н; С вЂ” линейный ограниченный оператор, действующий из Н в Н; с, а„, ..., а,— некоторые элементы из Н, Ь„..., Ь,— числа.
В частности, если С=О, то получим задачу линейного программирования. Будем предполагать, что 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) а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
