Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 40
Текст из файла (страница 40)
Ограничения типа равенств н неравенств, задаваемые функциями дл(и), ..., д,(и), ниже будут учитываться с помощью штрафных функций, и поэтому выделены от остальных ограничений типа равенств и неравенств нз (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. Гслн в предыдущем примере взять У = = (ш и я Е', д(и) (О, У„=(и: ие Е', гсо(и) ~0), то также нез гарантий того, что 1пп,)! = /„„ В самом деле, может оказаться, что а„) Ьс,)0, и тогда У» — — (и: 0( ( и ( 2 (аа+ Ь|)-с).
ФУнюгин У„(и) = / (и) = и достигает 2!9 нижней грани на (/» при и»=0, и снова !!ш Л=О~ У», 1!ш и»~и,. Пример 3. Пусть l(и)= — х — у, (/=(и=(х, у) ~ яЕ', О==.х~1, д4(и)=х — уаО, у»(и)=у — хаО). Очевидно, что У„= !п( У(и) = — 2 достигается в единствени ной точке и = (1, 1). Предположим, что,/„(и) == l (и), а множество (/ точно неизвестно и задано приближенно в виде (/»=)и=(х, у): О.=х(1, д»»(и).=(1+ )х— 1 '~ — у(0, да„(и)=у — (1 — »)х=='0~, й=!, 2, ...
По- 1! скольку (/» состоит всего из одной точки и„=(0, 0), то /'," = /(О) =О и 1!п1,Ц=-О~,/, = — 2, !пп и»~и, Заме» с» » 4О 1! ! тим также, что если д4»(и)=(1+ )х — у+-, д»»(и) = 1! 1 = 4/ — (1 — -~х+, то множества (/»=(и=(х, у): О.=- "= х(1, д,»(и) О, дз„(и)~0) будут пустыми прн всех 44=-1, 2, ... Пример 4. Пусть ищется минимум функции /(и) = и иа множестве (/= (и: и с=Е', д(и) =и»(1+и!)-'(0). Так как 1/ состоит из одной точки и„=О, то /,=l(0)=0.
Допустим, что функция у(и) задана приближенно в виде 1 д»(и) =д(и) — †. Тогда нижняя грань функции,/„(и) =и на множестве (/» = (и: и ~ Е', у» (и) ( О) равна /» = — со при каждом /4~ 1. Таким образом, !пп Д= — по~О = =- /„, хотя в рассматриваемом случае )и(и) — у, (и), ==,, ! (,/»(и) — l(и))=0, й=!, 2, ..., и погрешности стремятся к нулю равномерно на Е'. Заметим, что если д»(и) =у(и)-)-1//4, то множества (/»=(и: и енЕ4, д»(и)( -=.0), /4=1, 2, ..., будут пустыми. Эти примеры показывают, что при сколь угодно малой погрешности в задании множества (!) нижняя грань функции на возмущенном множестве (3) может значительно отличаться от нижней грани этой функции на исходном точно заданном множестве.
Иначе говоря, погрешности в задании множества (1) могут привести к неустойчивости даже задач первого типа (см. задачу (1.2)), когда ищут значение l» не интересуясь точками, в которых может достигаться нижняя грань. Таким образом, широкие к~ассы задач, когда миннмизнртсзшя функция l (и) н множество У известны лишь прн::лнженно, относятся к некорректным задачам. Для рс:пенни таких задач мы снова воспользуемся методами рсгуляризации. При этом часть ограничений из (1) учтем с помощью штрафных функций, а множество, задаваемое оста чьными ограничениями, будем несколько расширять с учетом погрешности задания исходных данных.
Использование штрафных функций и расширений множеств избавит нас от неооходимости рассматривать такой непростой вопрос, как выяснение пустоты илн непустоты множества (3), а методы регуляризации укажут пути такого согласования величин погрешностей задания исходных данных, точности решения вспомогателю:ых задач, штрафных коэффициентов, параметров регулярнзацип и расширения множеств, чтобы получаемые последовательное~и (иь) АУ, были минпмизирующиьш н регулярными в трсбуе:,юй метрике [58, 61, 211).
2. Итак, пусть на множестве У„введена некоторая метрика и пусть для задачи минимизации функции /(и) на множестве У требуется построить минимизирующую последовательность, регулярную в этой метряке. Так как множество У, определяемое условнямн (1), известно лишь приближенно, то нахождение хотя бы одной точки, принадлежащей У, или даже пооверка включения и ен У для какой-нибудь точки и из У, может вызвать затруднения.
Поэтому здесь нам придется отказаться от требования, чтобы минимизирующая последовательность непременно принадлежала множеству У, и несколько обобщить это понятие. О п р е д е л е н и е 1. Скажем, что последовательность (ив) минимизирует функцию ! (и) на множестве У, определяемом условиями (1), если и, е- =У„й = 1, 2, ..., 1! ш У (и„) = У„= !п(,) (и). Ф со иапо Определения 1.1, 1.2, 4.1 р-регулярных последовательностей, р-корректных и некорректных задач минимизации оставим прежними, но встречающееся в них понятие минимизирующей последовательности будем понимать в смысле нового определения 1. Далее, при построении р-регулярных минимизирующих последовательностей по- прежнему важную роль будет играть понятие стабилизатора.
Однако в связи с введением определения 1 нам 221 придется теперь несколько видоизменить и это понятие, заменив в определениях 2.1 и 2.2 условие Уо ~ У, где Уо — область определения стабилизатора 11 (и), условием Уо — — У„сохранив все остальные пункты в этих определениях.
Ограничения типа равенств и неравенств из (1), задаваемые функциями рй(и) или их приближениями дм(и), будем учитывать с помощью штрафных функций. Мы здесь ограничимся рассмотрением штрафных функпий шах (О; д; (и)), 1= 1, пп ~В(и)!, (=и+1, з, (5) (6) Выбором параметра Рза( в (4) можно управлять гладкостью штрафных функций, согласовывая при необходимости их гладкость с гладкостью исходных данных. Очевидно, что Р (и) = 0 при и ен (7. Заметим, что Р, (и) определена даже в том случае, когда множество (3) пусто. Пусть 11 (и) — некоторый стабилизатор задачи минимизации У (и) на множестве (1).
Как и выше, будем считать, что погрешности в задании исходных данных согласованы с выбранным стабилизатором (з(и). А именно, пусть в каждой точке и ~Уо имеют место неравенства ! у (и) — у„(и) ! ( 6, (1+ Й (и)), / Р (и) — Р„(и) ~ (6„(1+ й (и)), шах ! йт (и) — Йг„(и) ! — 6„(1+ й (и)), 1</<г Рь (и) '= О, ! й (и) — й„(и) ~ ( тд (1+ () (и)), (7) (6) (9) (10) где (6„), (т~) — неотрицательные последовательности, стремящиеся к нулю, т,(1, й = 1, 2, ... Введем множество Ж'ь=(и; и~Ба, й;~(и)(0„(1+Р~(и)), )=-1, У, /10„(и)!--Оа(1 )-!)„(и)), 1=1+1, г), (11) 222 5 Р(и) =- ~ (д,'(и) (я, г=! где р)1 и д,'(и) = дЙ(и) = Р,(и) =~ /64 (и) /г, и е=(7ш (4) гпах (О; дм (и)), 1 = 1, гп, ~а, (и)~, (=т+1, з.
представляющее собой некоторое расширение множества Тк'» = (и: и ~ У и, й~» (и) «О, ! = 1, 0 й„(и)=0, /=1-+1, г); здесь (8») — положительная последовательность, стремящаяся к нулю. Заметим, что в отличие от множества Ф», которое может быть и пустым, множество !»'» заведомо непусто, если параметр расширения 8„согласован с характеристиками погрешности Бм т» из (7) — (10) в смысле следующего неравенства; 8»)Б»(1 — т») ', й=1, 2, (12) Покажем это. Перепишем неравенство (10) в виде (1 — ч») 12 (и) — ч» «'»»»(и) « «(1+т»)1»(и)+т», иеи()п, й=1, 2, ...
(!3) Возьмем произвольную точку и ~ Уп П У. С учетом неравенств (9), (13) имеем йт» (и) «йт (и) + Б» (1 -)-1» (и)) « =-Б»(1+(1»»(и)+ч») (1 — т») '1=5»(1 — т») '(!+ У»(и)) « -=8 (1+(1»(и)) при 7=1, 1, и аналогично ~й7»(и)~« « ~й~(и),'+ Б»(1-1-1»(и)) «Б»(1 — ч»)-'(1+1»»(и)) «8» х х (1+1»»(и)) при /=1-1-1, г, и ~Оп.
Тем самым показано, что если выполнены неравенства (12), то (7п ПУ~ ~ !Р'» при всех й = 1, 2, ... Однако по определению стабилизатора (/о П (7 Ф 6, так что р» Ф ф. Перейдем к описанию метода Тихонова (стабилизации). Для этого введем тихоиовскую функцию Т, (и) = У» (и) -1- А,Р„(и) + аЯ» (и), (14) определенную на множестве (/о, где а» ) О, А») О, !нп ໠— — !пп А»'=-О, и рассмотрим задачу минимизации » сс» аэ этой функции на множестве %'» как задачу первого типа.
А именно, при каждом й=!, 2, ... определим точку и„, удовлетворяющую условиям Т»= 1п( Т,(и)«Т»(и»)«Т»+е», и»еп%'», (15) иеУ» где е»)0, !11п е,=О (если нижняя грань Т,(и) на К» достигается хотя бы в одной точке и» ~)»'», то в (15) можно допустить е„= О). Поскольку дальнейшее изложе- 823 ние не зависит от способа получения точки и„то здесь мы можем ограничиться предположением, что при каждом й=-1, 2, ... имеется достаточно эффективный метод получения такой точки. Заметим лишь, что трудоемкость задачи определения и» из (15) может существенно зависеть от того, какие из ограничений типа равенств или неравенств включены в штрафную функцию и какие — в определение множества Ж'». При этом важно позаботиться о том, чтобы множество )1«» имело структуру, облегчающую применение выбранного метода минимизации (например, если для решения задачи (15) используется метод проекции градиента, то проектирование иа множестве Ф'» не должно вызывать затруднений).
Укажем на крайние случаи: 1) все ограничения типа равенств и неравенств из (1) учитываются с помощью штрафных функций — тогда множество (й'» имеет наиболее «простой» вид; йГ» = ((ь (этот случай соответствует г= О, й((и) =— й(»(и) =О, и необходимость в выборе параметра 8» здесь отпадает); подробнее этот случай рассмотрен ниже, в п.
5; 2) все упомянутые ограничения учитываются прн составлении множества («'» согласно (!1) — тогда тихоновская функция имеет наиболее «простой» вид: Т» (и) = (» (и)+аФ» (и) а множество (й'» будег задаваться максимальным числом ограничений типа равенств и неравенств (этот случай соответствует з = О, Р (и) = Р» (и) = О; необходимость в выборе штрафных коэффициентов А„здесь отпадает). Кстати, если с=в=О, т. е. ((=((ь, то излагаемый здесь вариант метода стабилизации переходит в метод, исследованный выше в ~ 5. 3. Как и в з 5, нетрудно понять, что для того, чтосы последовательность (и,), удовлетворяющая условиям (!5), существовала, была минимизирующей и р-регулярной, нужно обеспечить согласованное изменение величин б», а», А», е„из (7) — (15).
Прежде чем переходить к строгой формулировке условий согласования этих величин и условий сходимости метода стабилизации, сначала докажем две леммы, обобщающие основные леммы 4.1, 4.2 о регуляризации. Л е м м а 1. Пусть выполнены следующие условия: 1) ((» — множество с заданной на нем ме»припой р; функции ((и), рд (и), (= 1, т, !дг (и) /, (= тт1, з, й~(и), (=— = 1, (, ~й((и) ~, (=(+1, в определены и р-полунепрерывны снизу ни с(ь; имею(п место условия (2); 224 2) функция й (и) определена на множестве Уп ~У, и является р-стабилизатором задачи минимизации 7(и) на множестве (1); 3) последовательность (и») такова, что и,си У„г(и»)(у„+р», (»=1, 2, ..., (!6) й(и») (йв+у„, я=!, 2, ..., (17) !!гп Р(и,) =О, (18) 1!т)»;(и»)~0, !'=1, 1; 1!щй~(и»)=0, 1=1+1, г, (10) где й,= !и! й(и), р»~0, юг=1, 2, ..., 1!щ р»=0, веоа » сс зцр!у»!< »~1 Тогда последовательность (и») минимизирует функцию г (и) на У, р-регулярна и !!в р (и», Ус!) = О, Уа = Уа () У,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
