Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 40
Текст из файла (страница 40)
а мы же выше допустили возможность се„=в„что приведет к равенствам = в„— Й„л= 1, 2, ... Олнако нетрудно видеть, что строгое неравенство т]„ ) ℠— Й„ е теореме 1 нсйользовалось только для того, чтобы гарантировать непустоту множества (2]. Поэтому эта теорема остаетсЯ веРной и тогпа, когда Ол =а, — Й, длЯ некотоРых или даже для всех л = 1, 2, ..., лишь бы мйожество Йл = (и: и ш У Й(и) -.Й,+цл=вл) не было пустым. Тем самым случай а,=Й„ рассмотрей полностью. Пусть теперь в, < Й,.
Тогда из условий (15] следует, что вл < Й пРи всех л ) йгс. Следовательно, по лемме 2 найдетса номеР л ) дсе, дли котоРого бУдет спРаведливо неРавенство (21). ПУсть и =а в 1 есть наименьший среди л сз 1 номер, когда впервые выполнилось неравенство (21]. В силу леммы 3 это означает, что вл ви жва с<Й„. Следующее Л-е приближение будем искать так. Положим геа л — — ва х+(й — ва т)2-л 5а л=5а-г 2 '"+"', л=О, 1, ...
(24) Затем, решая задачи минимизации первого типа для функции У(и) на известных множествах Й, из (18) и Й = (ис и ш (lп, Й (и) ( в (25) при фиксированном Л, найдем точки ил, „, ол, „, л=О, 1, ..., такие, что /ф л=]п] а'(и)<а (и л)<Х" „+$» „, и „ем Й „, (26) Йа,л л' =гп1 с'(и)< с' (оа л) <с +5а „ое л сы Йя, (27) Я]е и при каждом л=й, 1, ... будем проверять неравенство 7 (нл. л) — а (ем л] ) $а, л. Так как (ва, л), Да, „', монотонно убывают при л-с-со и в, ~ <ва,= 1!ш ва, л< Й„]1ш $л, „=О, то применяя лемму 2 при л со л сл фиксированном ]с, заключаем, что неравенство (28) обязательно выполнится при некотором конечном л ) О.
Через ла обозначим тот наименьший номер л ) О, для которого впервые выполиится неравенство (28), и положим ва=вл. ла $а=Ьг, ла на=не. ла (29) По лемме 3 неравенство (28) влечет за собой оценку вл=ва, ля < Й,. Описание Ьго шага закончено. Следующий (5+1)-й шаг и все дальнейшие шаги являются повторением процесса (24) — (27) с новыми влв,л=ва+(!Š— гол)2 ", 5лсс.л=5л'2 " ' л=О 1. с проверкой условия (28), соответствующего номеру й+1 и т. д. Из соотношений (24), 28), (29] и леммы 3 следует, что ва х<вгс< < ва ы « ".
Й» 215 Таким образом, при в, < й, рано нли поздно процесс (16) — (20) закончится выполнением условия (21) и заменится аналогичным процессом (24) — (27), ка кдый шаг которого в свою очередь будет завершаться выполнением неравенства (28) и получением очередного приближения по правилам (29). Убелимся теперь, что построенные последовательности (из), Дь), (т!о=℠— й,) удовлетворяют всем зребованиям метода квазирешений (1), (2). Поскольку нас будет интересовать поведение этих последовательностей при Ь вЂ” з-со, то можем пренебречь начальным этапом, когда члены указанных последовательностей определяются процессом (!5) †(21), и считать, что процесс (24) — (29) начался с а=1, 2, ...
Положим уь«=уэ« ~, йэ= = йэ, «», т)э=во — й,. Тогда соотношения [26), (25) с учетом обозначений (29) можно переписать в виде (1), (2). При этом !пп йэ=О, а со так нак в соответствии со вторым из равенств (24) исходная величина со на каждом шаге дробится, по крайней мере пополам. Кроме зого, в, — й„< вэ — й, =з)э < О, Ь=!, 2, ... Остается показать, что )ип т!э=О или !пп вэ=й . По по- Э со а со строению ва,<озэ<й„й=!, 2, ..., поэтому 1пп вэ=асущест. Э со вует и а< й, Предположим, что а< й„. Возьмем произвольное число Ь, а < Ь < й„и обозначим ус (Ь) = !п1 7 (и), где йь = "ь = (и: и сн(зп, й(и) <Ь). Согласно лемме 1 оо (Ь)) l«.
Положим в=ос(Ь) — 7,)0. Так как 1!ш $а=О, Нгп озэ=а, то найдется а оо Э со номер Ь такой, что $« с<2 'е, 0<а — вэ з<Ь вЂ” а. (30) Рассмотрим Ь-й шаг итерацвзнного процесса (24) — (29). Поскольку вь «=оз«, +(Й вЂ” вэ,) 2 " монотонно убывает и стремится к озэ при л-«со и ва з < а < Ь < йс < в«о=)7, то найдется номер паз! такой, что вэ, „< Ь<в«, «.з Зто значит, что йэ, „~ йь и следовательно, (31) /эо „= з'„(Ь) = У«+е. Покажем, что вз,«)а.
В самом деле, из Ь<ва,„, следует, что (Ь вЂ” ва,)2" з .с()7 — вэ,). А тогда соз „вЂ” а.=соа,— а+я — вз,) 2 «тэ ~вз з — а+(Ь вЂ” вэ,) 2 '=(Ь+соз, — 2а) 2 з ) О, так как Ь+озз,,— — 2а) 0 в силу второго неравенства (30). Таким образом, вз, « ~а. Лалее, из первого неравенства (30) с учетом зрормул (24) получим: сзс „< Ца з < 2 зе. Отсюда и из неравенств (26), (27), (31) следует, что у(ам«) — у(озс,«)~уэ,« — уо — Вэ,«~е — Бэ,«~Бэ,' Это означает, что неравенство (28) впервые выцолннтся при номере па=а.
А тогда ва=вз,«эзввь,«)а. Полученная оценка противоречит тому, чтопо построению вз,<ва .-. 1!ш в,„=а Стедоз«оо вательно, 1зш вя=й и 1пп т)э=О. Случай оз,<й, также раса оо а со смогрен. 216 Таким образом, если функции» (и), () (и) удовлетворяют всем условиям теоремы 1 и число»т' выбрано из условия (14), то итерационный процесс (15) — (21), переходящий при ы» (()» в процесс (24) — (29), позволяет реализовать метод квазирешений (1), (2) без априорного анания множества Уа и величины ()».
Разумеется, эффективность описанного способа реализации метода квазирешений зависит от того, существуют ли достаточно простые методы минимизации функции » (и) на множествах Йя, ()э, Яа „ в соответствии с условиями (19), (20) или (26), (27). Предлагаем читателю самостоятельно исследовать возможность применения метода квазирешений к задачам из примеров 5.1 — 5.5. 4. Мы рассмотрели три метода регуляризации некорректных задач минимизации: Тихонова(стабилизации),невязкн, квазирешений.
Более удобным в приложениях является, пожалуй, метод стабилизации. Вело в том, что для реализации методов невязки и квазирешений нУжно иметь оценки величин У~», Йа», в то вРемЯ как метоД стабилизации предварительного знания таких оценок не требует. Кроме того, если в методе стабилизации нужно минимизировать функцию Т»(и) на «простом» множестве Уп, то в двух других методах минимизация проводится на более <сложном» множестве в в них наряду с и ш У нужно учитывать еще дополнительные ограничения: /ь(и) (а +у» — в методе невязки, н Й»(и) ~ Йа+т)а — в методе квазирсшейнйг. Впрочем, если эти дополнительные ограничения учесть с помощью метода штрафов или метода множителей Лагранжа, то придем к функции Ба(и) =)»а»ь(и)+оса()а (и), и гц Уп, совпадающей при за= 1 с функцией Тихонова Т» (и).
Последнее обстоятельство подчеркивает наличис тесной связи между изученнымн тремя методами регуляризацин. Строгое исследование этой связи трех методов для некоторых классов некорректных задач см., например, в (105], стр. УУ вЂ” 33. ' У п р аж н е и и я. 1. Применить метод квазирешений к задачам из упражнений 3.2 — 3.4, исследовать сходимость. 2. Выяснить возможность применения метода квазирешений к задачам из упражнений 1.3 — 1.5, взяв стабилизатор (1(и) ='„'и ~ . в 3. В задачах из примеров 1.2 — 1.4 взять стабилизатор () (и) = = '! и ', и выяснить возможность применения метода квазирешений для построения минимизирующей последовательности, регулярной в метриках С (О, 1) и Н'(О 1). 4.
Показать, что при выполнении условий 1), 2) леммы 4.1 р-регул»:рность последовательности (иг,), построснной методом квазирсшсний, и соотношение !(гп р (иа, Уй) =0 можно получить при л зал»сне условия 11гп ца=О в теореме 1 и условий 1!и»)а = * со а сю -1 (пп чя= 1пп ч»т)а =0 в теорсме 2 более слабым условием л о» ь со зп Р т(я (+ со, (пп»)ь г э О в теоРеме ! и зиР т)ь (+ сх», ! пп т!» - О, а>! а»» а '-'» ! а ь» анр ч, ~ 1; 4 (а, + П (! — .цр .„)- т„+2па» = ! О, (, Ё= 1, 2, ..., А .! а»м 1 в теореме 2, В!7 5.
Пусть У (и) — выпуклая полунспрерывная сннзу функция на выпуклом замкнутом ограннченном лшожестве // нз гильбертова пространства Н, пусть й (и) =,',' и',нл Выяснить возможность применения метода квазнрешеннй н опнсанной выше схемы численной реалнзацнн этого метода для поиска Й-нормального решения задачи минимизации а'(и) на //. 6. Описанный в и. 3 способ реализации метода квазнрешеннй обобщить на случай прнблнжепно заданных функций l(и), 0 (и), когда в (5.4), (5.5) велнчнны 6ш уа положительны [57, 2!2). $ 8. Регуляризация задач минимизации на множествах, заданных приближенно 1.
Выше были рассмотрены методы регулярнзации некорректных задач минимизации в предположении, что множество (/, на котором ищется минимум функции /(и), известно точно. Однако имеется немало прикладных задач минимизации, в которых множество (/ задается приближенно и которые относятся к некорректно поставленным задачам. Здесь мы ограничимся рассмотрением множеств (/, представимых в виде (/=-(и: и~(/„дг(и)=0, /=1, т; дг(и)=0, (=т+1, з; й,(и) =О, /=-1, 1; /т/(и) =О, /=1+1, г), — (1) где (/, — заданное множество, функции лтл (и), ..., лт,(и), /тл (и), ..., /л,(и), а также минимизируемая функция /(и) определены на (/о. Ограничения типа равенств н неравенств, задаваемые функциями дл(и), ..., д,(и), ниже будут учитываться с помощью штрафных функций, и поэтому выделены от остальных ограничений типа равенств и неравенств нз (1), Впрочем заметим, что в последующих рассмотрениях не исключаются также и случаи, когда в (!) отсутствуют какие-либо из ограничений типа равенств или неравенств, т.
е. т=О, з=т, з=О, 1=0, г =/ нли г = О. Будем предполагать, что (/ ~= //),,/е =- !п1 / (и) ) — со, чши (/„= (и: и ен (/,,/ (и) = /„) М (/). (2) Пусть вместо точных значений функций /(и), лг;(и), й/(и) наФ известны лишь их приближения /а(и), ьтга(и), /з,л(и), ил=(/е, /а=1, 2, ...; множество (/е известно точно. Тогда вместо исходной задачи минимизации /(и) на (/ 216 можно попытаться рассмотреть задачу минимизации функ- ции („(и) на множестве Ц,=(ьн и ен()„дм(и) «О, 1= ! (3) Ео(и)=0 (=лг+1 йИ(и)==О, /=1, 1; Ь,ь(и) О ( !+1 Первая неприятность, с которой мы можем при эзом столкнуться, — это то, что множество (3) может оказаться пустым, хотя исходное множество (1) непусто.
Однако пусть все-таки У, =~ ф и пусть даже удалось точно найти Л=!п(1„(и) при всех 1=1, 2, ... Можно ли тогда наи деяться хотя бы на выполнение равенства 1!н1,!с', = Ь со при условии, что погрешности ~.сь(и) — /(и)1, гпах !у;с (и) — д; (и) |, шах ; 'Йм (и) — Й; (и)! при всех и ен Уо 1сссс 0<с(с стремятся к нулю при А — ~со? Оказывается, в общем случае ответ на этот вопрос отрицательный. Нетрудно привести примеры выпуклых или даже лппейных задач минимизации, когда !!п1 .lоФ,)ч.
П р имер 1. Пусть ищется минимум функции,)(и) =и на множестве (l=(гц и а=Е', д(и)=',и — 11+:;и+1~— — 2 = О). Очевидно, У,„= (п! У (и) = — 1, и множество точек ив о минимума (у„состоит нз одной точки и, = — 1. Предположим, что функция д(и) нам точно неизвестна н задана в виде д,(н) =, а,и — 1 -1- Ь,и+1 — 2, где !пп а„= = !!ш Ьо=1. Может случиться, что а,) Ь,~О, и тогда множество Ес„=(и: иенЕ', Р„(и)=0) будет состоять цз двух точек: и=О н и=2(п,+Ь„)-', й=1, 2, ..., функция lс,(и) = и в этом случае будет достигать своей нижней грани 11=0 на У„в точке и,=О. Ясно, что 1!ш,)с —— е со = 0 Ф вЂ” 1 = У ., !(гп и„-„и и,. с со П р и мер 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
