Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 89
Текст из файла (страница 89)
Па множестве й» рассмотрим функцию»)(Л, 1) = шах ' ав ~" Л;а;", Убедимся в том, что»)(Л, 1) > 0 при всех Лен Л», В самом деле, если су. митод штуй»оных Функции 377 й 1»1 ществует )» =(Ьд, 1»и1)»м Л», что»»(п, 1)~0, то ' а», ~ Х а 'ч ~ 0 1ыг прв всех»щ1. Умвожим эти иеравекства ка Ьв» (»ш1) и сложим; получим равенство ],Я Х»а» ~=0, противоречащее определению Л». Таким ]о 1 обРаэом, И(Ь, 1) > 0 пРи всех Х»=Ли ФУнкЦиЯ д(Х, 1) непРеРывна по Ь и ка компактном мкожестве Л» достигает своей витией грани в некоторой точке Х»еиЛдч причем д»(1) 1п1»»(Х, 1) =Н(Х», 1) >О. Поскольку Ьыйд мкожество (1] различных подмножеств 1 множества (1, .„т) для которых векторы (а», »»м1) линейно кезависимы, конечно, то Ы» =»п1И» (1) > О.
»Л Отсюда и иа (37), (38) имеем шах у+(и) вр(и, П) д()», 1(и))>р(и, П) Н», или дл»лт р(и, П) < (1)д») шах у»+ (и) (иск Еп). Таким обрааом, керавекство (36) да»л» справедливо с 7 = 1, М= 1/Ы». Лемма 3 докаэака. Л сии а 4. Пеп устое множество (7 (и»иЕ": у»(и) = (е», и) — Ь'(О, »=1, ..., т; у»(и) (а», и) — Ь' О, и = т+ 1, ..., в), (40) где а»»иЕ", Ь' »пЕ, задается корректными ограничениями ка Е" и неравекство (36) выполняется с 7 = 1 (7» = Е". Доказательство. Каждое огракичевие у»(и) = (а», и7 — Ь< =0 земским раввосильяыми ограиичевиями Ьи(и) = у»(и) (О, Ьм(и) — у»(и) (О и воспольауемся леммой 3.
Получим 1» (и, П) ~ М шах (уд+ (и), ..., у+ (и); Ьд+„+д (и), ..., Ьд, (и), Отсюда и иэ Ь+ (и) = шах(у (и); 0)(] у»(и) ] =у»+ (и), Ь+ (и) = шах ( — у» (и); 0) < ] у» (и) ] = у+» (и), » =т+1, ...,в, приходим к неравенству (36) с 7 = 1. Лемма 4 доказава. Другие классы множеств (7), заданкых корректными огравичеяиями, читатель найдет в (21]. 6.
В лемме 1 был выделен класс задач (1), (7), имеющих сильно согласоваикую постановку (см. неравенства (20), (21)). Следуя (21], приведем еще один содержательный класс таких задач. Л ем и а 5. Пусть функ»»ия 1(и) на множестве 1»е удовлетворяет уело еию Гельдера ]1(и) — 1(о)](Ь]и — о]" Ь»и, сев(7е, 5>0, 0(и~1; (41) овраничения, еадаюэ»ие множество (7), корректны на»7е и удовлетворяют неравенству (36). Говда задача (1), (7) имеет сильно ссвласованную постановку, причем неравенства (21) выиолняется при с» = ... = с, = ЬМ», = и"1. Доказательство. Возьмем произвольвую точку и»и(7с. По опретделекию р(и, П) = ш1 ] и — о( для любого е > 0 найдется такая точка емп 373 методы минимизАции ФУнкЦий мнОГих переменных (гл, в иг гн 51, Чта (и — и,( < р(и, П)+ Е.
ТОГда С УЧЕТОМ уСЛОВИй (36), (4Ц ИМЕЕМ а ЬМи ~ЧР ~(у+ (и))от+а(и) — ле) ПМ ( игах 61+ (и))"э+л (и) — У(и ) > 11вгвг > Л (р (и, П))и — 5) и — и (а) 5 (р (и, П))а — 5 (р (и, П) + е)и. Пользуясь произволом е ) О, отсюда при е~.
0 получим ьми Х (у+(и))™+л (и) — л ) О 1гиемп . 1 1 Заметим, что в общем случае пз выполнения условий леммы 5 не следует существование седловой точки функции Лагранжа задачи (1), (7) и, наоборот, существование седловой точки не гарантирует выполнение условий леммы 5. Это означает, что выделенные в леммах 1, 5 два класса задач (1), (7), имеющих сильно согласованную постановку, взаимно дополняют друг друга.
Отметим также, что атими двумя классами ие исчерпываются аадачи (1), (7) с сильно согласованной постановкой. Поясним это на примере. Пример 6. Рассмотрим задачу 7(и) = — иа- 1п(, и ш (1 = (и) О: у(и) = ив <0), (42) где а > О, 6 > О, По=(и елЕ1: и>0) =Е+~. Ясно, что П= П,„(0) у =о. Далее, имеем Т =0 = — и" +(ид)а)6 =в (и)+(у+(и))а76 7иеи П, так что неравенство (21) выполняется при г = тл =1, ст 1, т = и(3.
Следовательно, задача (42) имеет сильно согласованн1 ю постановку и к ней применимы теоремы 5, 6. Отметим, что здесь р(и, П) (и — О) = (и) = = (у+(и)) ОВ, и гн П„т. е. условие (36) выполняется с М 1, 7 = 1/6. Да. лее, при 0 < а < 1 фуннция 7(и) = — и" удовлетворяет условию Гельдерас (и" — ог( < (и — о(" (и, о ш (гг), так что в этом случае применима лемма 5.
При а > 1 условие Гельдера на Пв = П+ не выполняется и лемма 5 неприменима. Далее, функция Лаграюка Ь(и, 2) = — и"+ ЬФ (и ) О, )с ) 0) задачи (42) при и = () имеет седловую точку (и„= О, )се = 1). Кстати, седловая точна здесь не единственная: любая точка (О, »е), 3*) 1, также является седловой. Заметим также, что функция 7(и) = — ио, и ) О, выпукла лишь при 0 < и < 1, а у(и) = ие, и > О, выпукла лишь прн 6) 1.
Если а чь 6, то функция Лагранжа не имеет седловой точки. Таким образом, при и ) 1, 6 > О, а*ж 6 задача (42) не охватывается леммами 1, 5. 7. Покажем, что метод штрафных функций может быть использован для поиска седловой точки функции Лагранжа задачи (1), (7). Те ар ем а 7. Пусть (тс — выпуклое замкнутое множество иг Е"; функ ции 7(и), у,(и), ..., у~(и) выпуклы па Пг и принадлежат классу С'(Пе)1 Уг(и) = (аи иУ вЂ” Ь' (1= та+1, ..., г); пУсть Уе> — оо, П ,—ь 8 и фУнкция Лагранжа задачи (1), (7) имеет седловую точку (йе, Хе) ви По Х Ла е смысле неравенства (19). Кроме того, пусть функция Ф» (и) =у (и) + + А» ~~'~~ (уф (и))о, и ш Пс, р > 1, при каждом Ус = О, 1, ...
достигает своей 1 1 нижней гРани на Пе, в некотоРой точке ив ем Пс. Тогда если последователы ность (и») имеет хотя бы одну предельную точку, то и последовательность (»1), где )с~ = (31, ..., )ч), 2~~ = рА» ( уг+(и») '(о 1 (1= 1, ..., тЛ 2»1 нн г= РА»~ у~(и») (~ тайну (иг) (1 = ос+ 1,..., г) также будет иметь пре ЗШТОД ШТРАФНЫХ ФУНКЦИЙ 379 9 М! дельную точку, причем любая предельная точка последовательности ((иы )аь)) будет свдлоеой точкой функции Лазранзса. Доказательство. С учетом леммы 1 иа оценки (22) при еа О, ч 1, с, ~(7„»( получим (у+1(иа) (((()а» (/А )11(р 1!.
Тогда Ая) у~(иа)(р ~)2,»(Прн ВСЕХ 1= 1, ..., З, )а О, 1, ... ОтСЮда СЛЕдуЕт, Чта ~)аг ~ ~ ~ р()с» ( ($1, ..., з, Е = О, 1, ...), т. е. последовательность ().а) ограничена. Пусть о» вЂ” какая-либо предельны точка последовательности (иь), "г1 пусть (иа ! -а о». Согласно теореме 5 о» си П». Иэ (я ) выделим подпослеГ3 довательность, сходящуюся к некоторой точке д». Можем считать, что сама последовательность ()а ") сходится к !1». Так как )аз~~0 при ! = 1, ..., та то и р~~О (1=1, ..., па), так что р»шЛа.
Далее, так как Фа(и) выпукла и Фа(и) аи бч((га), то согласно теореме 4.2.3 в точке иа имеем (Фь (ь и), и — иь) > 0 Цаи ам Пе. (43) Поскольку Фа(иь) ='(иа)+ Х рйь(у'(иа) (' 'у;(иа)+ а=1 + '~~ рА (у+(и )(Р 1е!8пу (и )уг(и ) =з"'(иа)+ ~ч~~ )11~у (и1,) 1 ак+1 1 з !!ш Ф, (и ) = з'(о ) + ~ЧР ~р.у. (и ) = Ь (о, )1»). гмаа 1-1 '' Поэтому иэ (43) при 7с = Ег- оа получим (Ьч(о», р»), и — о»)»0, и ам Па. Так как )а*ам Л„то при выполнении условий теоремы функция Ь(и, Х») выпукла на Па, н последнее неравенство равносильно такому: Ь(о», р»)(Ь(и, р») тианП .
(44) Далее, если у; (о») < 0 при некотором 1 (1 < 1 < т), то иэ )! ш у1 ( и, ) г.»а у1(о») < О следует, что у (иа ) (О или у» (иа ) = 0 для всех гэ га. ьг ьг» » А тогда 2 '= 0 при всех г) г и Иш 21" = р»= О. Таким образом, р1=0 г аа для всех номеров 1 (1(1( т), для которых уь(о») (О, а для остальных » номеров 1 (1(1<в), мы имеем уг(о ) =О. следовательно, реу1(о») а аО (1=1, ..., з). Отсюда и иэ (44) с помощью леммы 4.9,2 получим, что (с», р») — седловая точна функции Лагранжа. Теорема доказана. 8.
Метод штрафных функций может быть использован и для получения условий оптимальности в задаче (1), (7), В частности, с помощью этого метода можно получить другое довольно простое доказательство правила множителей Лагранжа, правда, при несколько больших требованиях, чем и $ 4,8. Теорема 8. Пусть в задаче (1), (7) Па — выпуклое замкнутое мно- асество, функции з(и), уа(и), ..., б,(и) аи с'((га), з».м — ао, и»-ь з. если и» аи П», то существуют числа Хо Ъ О, .", ),т~ О, )ат»1, ..., )а„не все » »»» равные нулю и такие, что ()аев'(и») +)агут(и»)+ ...
+)1,уа(и,), и — и»)~ 0 )а,.у (и ) =О, 380 методы минимизАции Функции мнОГих пеРеменных [Гл. в Доказательство. Введем новую функцисо Л (и)=У(и)+[и — из [~, множество И' = У ([ о" (и ), где Ю(ио) =(оси Ьо: [и — ио(~1), и рас- смотрим вспомогательную аадачу минимизации Ео(и)-~-ш(, иш И'= (иев И'о дс(и) <О, ..., Е„(и) <О, Ео+~(и) = О, ..., Е,(и) = 0). (47) Так иак Л (и) )о (и)>У пРи всех иш[т, и и, пРичем Е (и ) =Уз, ио си И", то ясно, что и — единственное решение задачи (47). Применим и задаче (47) метоД штРафных фУикций. Введем фУнкЦию Фй(и) =Ее(и)+ +Ай ~', (Е[ (и))~ и ш)уо, р >1. Так как !т'о — компактное множество, С 1 функции ло(и), Фй(и) непрерывны на Ио, то я „=!и! г (и) ) — оо, Фй =о е ~!п(Ф (и) > — ос~ и существует точка изш Ио, для которой Ф[,(и[) ~ й е Фй .
Далее, множество Иг(6) = (иш Исо[ Гс~(и)<6, [=1, ..., з) огра иичепо при всех 6) О, таи как И'о ограничено. По теореме 2 тогда 1!ш ) ий — ио ! = О, 11ш ле (ий) = 1пк У(ий) = о'о. Применяя теорему 4.2.3 й-кю й ооо й-+аа к задаче: Фй(и)-о1в1, и си Ига имеем (Фй(ий), и — ий)~)0 чсишИ'. (48) Покажем, что зто неравенство па самом деле верно для всех и ш Вв е ли помер й достаточно большой. А именно, выберем номер йо таким, чтобы ! и„— ио !< 1/2 при всех й > йо. Возьмем произвольную точку о ш Уо, За фиксируем число а (О < а < 1), столь малым, чтобы а ( и — ио [<1/2. Тогда точка о„= ий+ а(о — иь) еи с[о и, кроме того, )ос,— ио!=)(1 — сс)(ий — и„)+ + а(о — ио) ! < (1 — сс) ! и[,— ио !+ а(и — ио [~1. Следовательно, о„см Исо, Р и в (48) можем принять и = о .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
