Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 88
Текст из файла (страница 88)
° (29) Польауясь неравенством Гальдера при ьт = си а( — — (у~~' (иа))«, кь = р?«, т = р[(р — «), получаем в О ( ~Ч~~ с. (у". (и,))ч () с) (Р (иа))ч(Р, (ЗО) 6 141 митод штрлюных соункцнн 373 Отсюда и нз (29) следует О < Аор(ио) < (с((Р(но))"'г+ еь пли 0(гр~" < ~(с) А»трав+ е» (» =О, 1, ...), где г = (Лор(иг))"е. С помоЩью леммы 2,3Л1 тогда получаем »ч/р 0 <(1 Р(и ))ч)е < ((( ) 1-чра)г)(г-чг ( Р что равносильно оценке (22). Далее, из (28) с учетом (30) имеем — ) с ) (Р (и,))ьуу < л (и») — г < е», Отсюда и ив уже доказанной оценки (22] следует оценка (23).
Далее, левые неравенства (24) получаготся из (26) прн и = иь и иэ (27), правые неравенства (24) вытекают нз (13). Наконец, утверждение о том, предельная точка ое последовательности (иь) прпнадлегкит Уе, вытекает иэ оце нок (22) — (24) и доказывается также, как аналогичное утверждение в тео. реме 2. Теорема 6. Пусть задача (1), (7) имеет сильно согласованную постановку е смысле определения 3, Уе ° — оо, последовательность (иь) опРеделена УсаовиЯми (3), (6), (8), где Р = т, А» >) с( = шах ~ сг(. Тогда глгаг е» О<(у+(и»))'<Р(и») < „(,), (31) е» )с! А» )с) <г (и») ге<с О < Ф»(и») У, < е,, Ф»„= У,.
(32) (33) Коли У чь )2(, пго Уе — У» (и вн Уе' .Ф» (и) = Ф» ) (34) Коли, кроме того, Уо — замкнутое множество, функиии 7(и), уе (и) полуне+ врерывны снизу на Уо, (е»)-ьО, и ое — предельная точка (иь), то ое вн Уе. Доказательство. Из (25) при р = ч, Аз > )с) имеем Ф»(и) — г'е> ,мО, ион Уе, так что Ф» >>ле > — со, и последовательность (иь), удовлетворяющая условпям (6), при еь > 0 существует. Из (29) при р = т, Аь > )с) сразу получаем оценку (31). Из нее и нз (28) при р = ч следует оценка (32).
Иэ (13) и (25) при р = т, Аь > (с( с учетом того, что ш!и ( — свеч+ А»гт) = О, приходим к соотношениям (ЗЗ). Докажем равенств~о во (34). Нозьмем пРоизвольнУю точкУ иь ен Уь. Тогда Р (ие) = 0 и Ф» (ие) = л (иь) =ге =Ф», так что ивги У» . Следовательно, Уь сУ„. Пусть теперь и» ш У„, т. е.
Ф,(и» ) =Ф» . дто значит, что условие (6) при и» и, выполняется с е» = О. Тогда из оценки (31) при е»= 0 получаем »е Р(и» ) О, т. е. и» ем У. Отсюда, из (ЗЗ) и из того, ято г (и, )= Ф, (и» ) = Ф» — — ге следует, что и» вн Уь. Следовательно, У с У„. Равенство (34) доказано. Последнее утверждение теоремы вытекает ив оценок (31)— (33) и доказывается так же, как аналогичное утверждение в теореме 2. Из теоремы 6 следует, что случай р = т интересен тем, что при точной реализации метода штрафных функций (3), (6), (8) решение исходной задачи (1), (7) может быть получено при конечных значениях штрафного ковффицнента Ал.
374 методы минимизации ФРНКПИН мнОГИХ пеРеменных (ГП, ь Рассмотрим примеры, которые показывают, что оценки, полученные в теоремах б, 6, не могут быть существенно улучшены на классе аадач (1)> (7), имеющих сильно согласованную постановку. Пример 4. Рассмотрим задачу У(и) = — и-+шЕ, и сп (/ = (и ш Е': у(и) = и < О). Здесь с" = О, У„= (0). Функция Лагранжа Е(и, л) = — и+ ли, и ш Ус= Ел, » сиЛс = (л шЕ'.
)л ) 0) имеет седлсвую точку (из = О, Ле = 1), так что согласно (20) неравенство (21) выполнено при т = 1, сс = 1, з = 1. Возьмем штрафную функцию Рл(и) = Ал(Е+ (и) ) т = Ал(шах(и; 0)) з, р Зв 1, Ал ) ) 1, (Ал) -л сс. Тогда функция (3) будет иметь вид (и) ~ — и+ Алии, и~ )О, ( — и, и<0. Нетрудно показать, что (О, р= и=1, » д ° -л/(е-М причем нижняя грань достигается в точке и» вЂ” — 0 при р=1 и ид =* (РА») л/(в л)при р ) 1, д = О, 1, ... Последовательность (и» ]удовлет- воряет условиям (5) или (6) с ел О, причем (О, Р = 1, (О, р - 1, ~((РА ) — ™-М р > 1 (иде) е ( (РА )-Л/(В-1) р >1 Р д) Ф Сравнение атих точных равенств с оценками теорем 5, 6 при ел 0 показывает, что в случае р = 1 оценки (31), (32) точны, а в случае р ) 1 оценки (22) — (24) точны по порядку и отличаются от точных оценок лшпь константами при степени Ал.
Если ел ) О, то при р = 1 в качестве точки ил, удовлетворяющей условиям (6) и наиболее удаленной от (/е, здесь можно ваять ил= ел/(Ал — 1) (Д = О, 1,...). Тогда Р(ил) = ил= ел(Ал — !с()-', с'(ид) — У~ = — ид — — — !с ) е» (А» — ) с!) л, Ф» (и„) — У„= (Ад — 1) ид =* =ад (»=0, 1, ...), что совпадает с оценками (31) — (33). Если ел) О, р = 2, то точка ил (1/(2А»)) + (ел/Ал)п' удовлетворяет условиям (6), пРичем АдР(ид) = Адидз — — (1/(4А„))+с~+(з/Ад)л/з, У(ид) — з = — и„ Фд(ид) — с'е =ел — (1/(4А»)), что также свидетельствует о том, что оценки (22) — (24) иа классе задач с сильно согласованной постановкой ве являются грубыми.
Зтот же пример показывает, что в теореме 6 требования Ал ) )с( не может быть опущено. В самом деле, если А»( 1 = )с~, р 1, то Фд =* °и — сс) если же Ал = 1 = )с(, р 1, то Фл(и) из О, Фд — — О, Уд * Е д и нарушено равенство (34). Пример 5. Рассмотрим задачу У(и) = — и-+(п(, и си У = (и лиЕ'. д(и) = ил(0). Здесь се = О, У = У (О). Функция Лагранжа Е(и, д) = — и+ лил, иеа Е', й сн Е+~, седловой точки не имеет, но тем не менее аадача имеет сильно согласованную постановку.
В самом деле, справедливо неравенство се = 0 ~ < — и+) и) = — и+(я(и))л/з яри всех иснЕ', так что неравенство (21) выполняется при с = 1, т = 1/2. Возьмем штрафную функцию Р(и) (шах(и', 0))з = (ил)а. Если р ) 1/2 т,то функция Фл(и) — и+Ализа, Ал О, (Ал) — сс, доствгает нижней грани на //с = Е' при ид МЕТОД ШТРАФНЫХ ФУНБЦНН $14] 375 пч(2РА») 1](зр 1] (4=0, 1, ...), причем Р(и„) =(2рА,) У(и»,) — вв — и», Ф» — лв = — (2р — 1) ((2р)зРА») 1](зу 1] (Ь = О, 1, ...). Как видим, зти оценки лишь константами при степенях А» отличаются от оценок (22) — (24).
Интересно заметить, что с увеличением р оцен. ки ухудшаются. Если р = т = 1]2, А» > 1 = [с[, то Ф»(и) = — и+А»[п[, Фз — — О. Точка и» = з»(А» — 1)-' удовлетворяет условиям (6) и наиболее удалена от Ув =(О). Тогда Р(и») = [щ[ = е„(А„— 1)-', в (иь) — Ув ~ — иа, Ф»(и») — вв = ее что совпадает с оценками (31) — (33). 5. Выполнение соотношений (12) или (16), как покавывает пример 2, еще не гарантирует сходнмость последовательности (и») из (6) ко множеству У. Для такой сходимости множество должно удовлетворять некоторым дополнительным условиям. О п р е д е л е н и е 4.
Скажем, что множество (7) задано корректными ограничениями на У», если всякая последовательность (и») »н У„удовлетворяющая условиям (16), сходится ко множеству У. Примеры 2, 3 показывают, что одно и то же множество может быть задано как корректными, так и некорректными ограничениями. Как следует иа доказательства теоремы 2, ограничения из (7) будут корректными на У„ если функции у~~ (и) (] = 1,..., г), полунепрерывны сниву на замкнутом множестве У», а множество У(5), определяемое согласно (14), ограничено при некотором 6 > О.
Корректными будут также ограничения, для которых удается доказать неравенство р(п У)(Ь(у+(и) °, ув+(п))»Уп»пУе, (35) где функция ь(г) = ь(гь ..., 1,) > 0 при всех где'„, ге»0, й(0) =О, 1]шй (г) = О. Приведем важные классы множеств (7), задаваемых коррект« го ными ограничениями, длн которых неравенство (35) имеет вид р(п,у)<м] шах у]+(и))т уи»ну; м>0, у>0. (36) (1Л]кг Лемма 2. Пусть Ув — выпуклое замкнутое мпамввтво, фупкяии у,(и), ..., уп(п) выпуклы и непрерывны ка Ув, пусть существует такая точка и вн Ув, что у~(и) ( О, ..., у„,(и) ( 0; пусть мпсзггства У = (и »ь У».' у~(и) ~ О, ..., уп(и) (О) ограничено. Тогда неравенство (36) выпвлпкгтск с 7=1, М=д]ашУ7 ш1н ~[у (и)[] 1, Й]ашУ зир [и — о). ]1.]кы / чл — и доказательство. Введем функцию у(и) = шах уг(п).
В силу 1Л»лы теоремы 4,2П функция у(и) выпукла на Уь Возьмем произвольную точку пон У»»У. Тогда у(и) > О. Функция 7(Ц = у(и+ ](и — и)) переменной г непрерывна на отрезке [О, 1), 7(0) = у(и) > О, 7(1) = у(й) ( О. Следовательно, существует точка г вм (О, 1), такая что 7(1») = О. Положим и = и+ 1»(и — и); тогда га = [в — и[ [и — и~ ', 1 — гв — — [и — й[ [и — и[-'. пользуясь выпуклостью функции у(и), имеем у(в) = 7(гв) = 0 ( свд(и) + + (1 — ]») у(и) или — г»у(й)((1 — 1») у(и) или [в — и[ [у(и) [([в — и[у+(и). Отсюда с учетом й, в»нУ получаем, что р(и, У) ([и — г[(у+(и) )( )4 [и — п[(у(й))-' = Му»(п), что и требовалось. Лемма 3. Пусть У=(ишЕтч у<(и) 4ав, и) — Ьт<0, 1=1, ..., тл) ~ 8, гдг а» вн Е", Ьв внй (1= 1, ..., ш).
Тогда сграпичвкпц гадающие множество У, корректны на Е", и неравенство (36) выполккгтвп с7=1, У»=Е". Доказательство. Возьмем произвольную точку в~У. Так как У вЂ” выпуклое замкнутое множество, то согласно теореме 4.4.1 одновначно определяется проекция ш = Ро(и) точки и иа У. К задаче определения проекции; у(в) = [и — «[-».ш1, н»н У, применимы теорема 4.9.4 и лем 376 метОды минимизации ФункЦий многих переменных !Гл, в ма 4.9.2, которые гарантируют существование таких чисел Л, > О, ..., ) =и >О, что »з » в (ш)+ )' Л»г;(ш)= + )' Л໠— — О, Л»((а», ш') — Ь) =О, » л ( » =1, ..., ю, Отсюда, учитывая, что ~ ш — и! = р(и, 1)), имеел» и — ш=р(и, ()) ~ Лам 1(и)=(»(» 1<(<з», Л»>0, »ыци) <ао ш> — Ь»=О).
(3» Можно считать, что система векторов (а», (ш1(и)) линейно независима. В самом деле, если су»цествуют числа 7» ((»в1(и)), не все равные нулю, у»а О, то и — ш р(и, П) ~~ (Л» — »7»)а,, где т» =Л» — »7»> ив 1(и) ьв пи) > 0 (( ш 1(и) ) при всех», 0 < г <»„»л — достаточно малое число. Можно считать, что среди 7» (»»в1(и)), есть положительные числа, иначе изменим знаки всех 7» ((»в 1(и) ).
положим з»з»/7» ш1п а»17». т(>е,»в1(и) Тогда т» = Л» — »"(»>О ((ш1(и)), причем по крайней мере одно число т, = Л, — »7, = О. Таким образом, заменив в (37) Л» на т» и исключив ив 1(и) те номера, для которых т» = О, снова придем к равенству вида (37) с меньшим числом слагаемых. Последовательно применяя этот прием далее, за конечное число шагов придем к представлению (37), в котором система (а», (»в 1(и)) линейно независима.
Из (37) следует шах у+(и) и шах дй(ы)> шах у»(и) = плах ((ав и) — ь ) = ла»м»и (а 1(и)»=ди)»в((и) = шах (а», ы — ш)=р(и, 1)) шах,Гав ~ Л)а ~,. (38) »В1(и)»нт(и) ' в)(и) Покажем, что величину шах Га», ~ Л)а) '„где система (а», »»в1(и)) »вг(и) ' )вг(и) линейно независима, можно оценить снизу положительной величиной, не зависящей от и. С этой целью возьмем любое множество индексов 1 с (1,..., »и), таких, что векторы (а», » ш 1) линейно неаависимы, и введем множество Л =~(Л», (»в1): Л»~0, ( ~Ч~ ~Л(а» ~ 1~, ~~».1 (39) Заметим, что Л» — замкнутое ограниченное множество. В самом деле, если Ла =(Л~»»»»в11»вЛЦ Лл -лЛ, то предельным переходом в (39) легко убедиться, что Л»вй,, Следовательно, Л» замкнуто.
Покажем ограниченность Ль Допустим противное: пусть найдутся Лл»ЕЛ, (Ь =1, 2, ...), )Лл)-~со. Тогда последовательность рл=3Р/(Лл) (2=1, 2, ...) ограничена: ()»л( = 1. Выбирая при необходимости подпоследовательность, можем считать, что ()лл) -»-р, ))л! = 1. Поскольку ~ ~ Л,"а» ( = 1, то ( ~ч~', р»а» ~ *= 1/) Л ) -»-0 = ~ ре»а», где р = (ре», »»в 1)чьО. Однако зто противоречив »юг линейной невависимости (а», (»в1). Следовательно, Л, аамкнуто.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
