Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 106
Текст из файла (страница 106)
Пусть для некоторых С, го >0 множество Х(С вЂ” го) непусто и Х(С вЂ” О) = (и Е Х>. д(и) < С', о = 1,, тп) Пусть, кроме того, функция 7(х) полунепрврывна сверху на множестве Х(С). Тогда Яс — О) = 7"„(С) = <и( 7" (х). (17) «<с-о> Доказательство. Прежде всего, заметим, что Х(С вЂ” г) 9 Х(С вЂ” 6) 9 Х(С вЂ” 0) С Х(С) при всех 0 < 6 < е » <го, поэтому )'„(С) < !п1 7"(х) (7"„(С вЂ” 6) (>о(С вЂ” е).
«<с-о> Это значит, что функция 7'„(С) переменной С не возрастает и существует предел 1нп 7",(С вЂ” г) = 7",(С вЂ” 0) > <п! 7"(х) > 7",(С). (18) о .Ю * «(С вЂ” О) Возьмем произвольную точку х е Х(С). В силу условия (16) найдется последовательность (ха) е Х(С вЂ” 0), сходящаяся к точке х. Это значит, что хь е Х, д (хь) < С вЂ” е ь < С, г ь >О, й = = <,2, ..
о где 1пп го,— — О, <=1,..., т.Таким образом, хьеХ(С вЂ” г ), где в = ш(й в >О, Ь оо (гь) оО, и )о(С вЂ” еь) < )'(хь), й =1, 2,... Отсюда при й о оо, учитывая полунепрерывность свеРхУ фУнкции 7(х), полУчим 1!ш 7",(С-г) = йш 7",(С вЂ” гь) <7(х). В силУ пРоизвольности о-Ю * ь хе Х(С) тогда )"„(С вЂ” 0) < >о(С).
Сравнивая это неравенство с (18), приходим к равенству (17). Тео емв 2 доказана. П аким образом, если условия теоремы 2 выполнены при С = О, то методам баоьеоных функций (2), (4), (8)-(11) для задачи (1), (8) можно получить последовательность (хь), облацающую свойствами (6). Аналогичное утверждение справедливо для выпуклых задач (1), (8). Теорема 3. Пусть Хо — выпуклое множество на ао, функции 7(х), д<(х),..., д (х) вьгпукльь на Хо. Тогда равенства (17) справедливы при всех С > С„= шах (п1д<(х). ! « < оо «о Доказательство. Как было установлено в теореме 2, функция 7",(С) переменной С не возрастает. Возьмем произвольные С, г>0, С>С вЂ” г>С,.
Пусть хеХ(С), уеХ(С вЂ” г). В силу выпуклости Хо тогда х = ау+ (1 — а)х е Хо при всех а, 0 < а < 1. Кроме того, из выпуклости д (х) имеем д (х ) ( ад (у) ! (! — а)д (х) < а(С вЂ” в) ц-(1 — т)С = С вЂ” аг, 0 < а < 1. Это значит, что х е Л(С вЂ” ав). Тогда с учетом выпуклости функции 7(х) получим 7"„(С) < !и! 7(х)(у,(С вЂ” аг) <7(х )< а>(у)+(1 — а)7(х) для всех хеХ(С), уеХ(С— «<с-о> — г). Следовательно, 7(С) ( <п< 7(х) < 7",(С вЂ” аг) < ау(С вЂ” г)+ (1 — а)7" (С) < 7",(С)+ «<с-о) + а[7"„(С вЂ” го) — >о(С)] длЯ всех и, 0 < а ( 1, 0 < г < го < С вЂ” С,.
Отсгода пРи а -о+О с Учетом монотонности уо(С) получаем равенства (17), что и требовалось.П 4. Пусть множество Х задается условиями Х=(хеН": хеХо, д (х)(0, (=1, от; д (х)=0, ! — т!.1 г) Если это мнох(ество не имеет внутренних точек, то реализация ряда методов минимизации (напримео, методов иэ $3-5, 11 и др.) на Х может стать затруднительной или даже невозможной. н то же время при применении методов $14, !5 к задаче (1),(19) могут получиться такие последовательности (хь), которые не принадлежат множеству Х и нарушают какие- либо иа ограничений д<(х) (О, д (х) = 0 на недопустима большую величину. В таких случаях может оказаться целесообразным использование метода барьерных функций, Заметим, что этот метод выше изложен для задачи (1), (8) в предположении, что множество Х(-0), определяемое условиями (10), непусто.
Однако такое предположение для множества (19) при тп < в не имеет смысла, Поэтому описанный выше метод барьерных фуниций к задаче (1), (19) непосредственно неприменим и требует модификации, обобщения, Опишем один из возможных здесь подходов 1390]. $ ! 7. МЕТОД БАРЬЕРНЫХ ФУНКЦИЙ 355 (23) !2 354 Гл, 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Введем теперь последовательность расширенных множеств 'ой =(х и Хо уг(х) < дй ! =1, ..оса; (дй(х)! < Вй с — — го+1,, г), (20) где д > О, й = 1, 2, .. о Пш 0 = О.
Так как Х с \ ю й = 1, 2,, . о то из Х ф !Зу следует гй ф !Зг, й» й й й оо й =1,2,, Предполагая, что функция 2"(х) определена на множестве (2 Уй, рассмотрим последовательность задач У(х) -в !и!! х н Ъ~, й = 1, 2,... (21) Для решения задач (21)могут быть использованы различные методы минимизации.Мы здесь остановимся лишь на методе барьерных функций. Обозначим уй — — (Х П 1гй И ВЫПОЛНяЕтСя ХОтя бЫ ОДНО ИЗ раВЕНСтВ ув(Х) = Вй, В = 1,,,о т; д (х) = Вю ду(х) =-Вй, У =т+ 1, .. о г). (22) поскольку х с 1'й, х О.уй — — !д, то х с 1'й'! уй ай!, й =1, 2,... В качестве барьерной функции Вй(х) подмножества уй возьмем в в Вй(х)= 2: р(д,-д(*))+ Т: р(дй+д(х)), хбуй17й, в=! в=о О! где функция чвг(1) определена, конечна, неотрицательна н не возрастает при ! > О, Пш !ов(г) = со, в = 1,,,о г.
Например, в качестве уй(!) можно взять чвй(!) = з , Чв(!) = — ! ча =(шах(-1п т; 0))г, р>1, Далее, составим функцию Гй(х) =7(х)+айВй(х), хб 1гй 'у уй, (24) где (а ) — барьерные коэффициенты;а > О, й = 1,2,..о (а ) — О. В отличие от рассмотрен- ного выше варианта метода барьерных функций, здесь мы будем требовать, чтобы барьерные й коэффициенты (ай) и параметры (Вй) стремились к нулю согласованно в следующем смысле: Пт а чв! (Вй ) = О, в = 1, ..
о г. (25) й в' ус Предположим, что уй — — ги1 2(х) > -со, й = 1, 2,... Так как Вй(х) ) О, ай > О, то Рй(х) ) у(х) йв и при всех х6 У '!7, и поэтому Рй = !и! Г (х) >уй >-со, й = 1,2,... С помощью какогой й йв й в тв либо метода минимизации определим точку хй, удовлетворяющую условиям хй 6 Уй ~ уй, Рй, < Гй (хй) < Гй, + гй, й = 1, 2, ..о (26) где (а ) — некоторая положительная последовательность, сходящаяся к нулю; если Рй(хй) = й йв' = Рчч то в (26) допускается ай = О. Метод барьерных функций для задачи (1), (19) списан. Теорема 4. Пусть функции Рй(х), Вй(х), множество Ъ~, Тй определены соотноше- ниями (20), (22)-(24), выполняются равенства (25) и, кроме того, Пш Уй„= У, >-со, Уй, =1п(у(*), У = !и! У(*).
(27) Тогда длл последовательности (х ), апргдглягмой условиями (20), справедливы соотно- шения !пп Рй, = Пщ Рй(хй)= Пш 2(хй) = у"„1пп айВй(хй)=0. (28) й оо й оо й со й со Если, кроме того, множество Х(6) =(хб Хо. дг(х) ч 6, в =1, ..от; !Вй(х))ч 6, в' =та+1,.. о г) (29) компактно при некотором 6 > О, множество Хо замкнуто, а функции д!(х), ..
о д (х), !у „!(хи,., о (д,(х)! полунелрерасаны снизу на Х(6), то(хй)- Մ— множество решений за им дачи (!),(19). Доказательство. Из определения уй„рй„неотрицательности Вй(х) и условий (26) еем -со<гав(«2 (хй)<Гйв+гй<Рй(х)+гй — — 2(х)+айВй(х)+ай, хбЪ~, Уу 7й, й=1,2, в (30) Так как фУнкции Ч т(т) из (23) не возРастают пРи ! > О, то !о,, (Вй — Уг(х)) < Уй(дй), в = 1, .. о пв; йвв(дй х у;(х)) = Чвт(дй), в = ив+ 1, ..
о а, для всех х 6 Х. Поэтому в силу, условия (25) 0<айВй(х)<2ай Я хг(дй) — вО, й — оо, вухпХ, (31) ! Тогда при й -в со из (30) с учетом условия (27) получим у;< Пш Г,< Пш Рй,<2(х) при всех хбХ. й со й Переходи к нижней грани по х 6 Х, отсюда имеем Пт Рй, — — ~;. Тогда из (30) следует й оо !пи Гй (хй ) = Пш 2(хй) = ув. Наконец, 0 «(ай Вй (хй ) = Гй (хй) — у(хй) -в 0 при й -в оо.
Равенства (28) доказаны. Пусть теперь выполнены все условия теоремы. Так как (Вй) †в, то ввй С Х(6) при всех й ) йо. Тогда хй П Х(6), й > 212. В силУ компактности Х(6) йоследовательность (хй) имеет хотя бы одну предельную тачку. Пусть х, — произвольная предельная точка (хй), пусть подпоследовательность (хй ) -вх,.
В силу замкнутости хо тогда х„ 6 хо. иа полунепрерывности снизУ фУнкций д!(х),,,о У„,(х), !д„, !(х)(, о !У,(х)! и Условна ху, 6 угй следУет, что у,(х,)< Пш дг(хй)< !ии В.=О, в=1,..от, (дв(х,)!< Пш !0,(хй)(< Пш Вй — — 0 со й со или у;(х)=0, в=т+1,..ок Таким образом, х, 6 Х.
Отсюда с учетом полунепрерывности снизу 2(х) на Х(6) получим 7, < 7(х,) < !ип 7(хй ) = !пп 7(хй) = 7„ т. е. 7(х,) = 2, или х, 6 Х,. Тем самым показано, что любая предельная точка последовательности (хй) принадлежит Х,. Отсюда следует, что (х ) Х,. Теорема 4 доказана. Су При некоторых более жестких ограничениях на данные задачи (1), (19) можно получить оценки погрешности метода (20)-(26). Теорема 5. Пусть длл задачи (1), (19) справедливо нгразенстзо ~<Л«<у(х)+ Х.
сг(у,+(х))" ИхбХО, ст>0, и)О (32) в=! (см, определение 15.3 и леммь! 15.1, 15.5). Тогда последовательность (хй), определяемая, условиями (20)-(26), сущастгуат и справедливы оценка в -/с!!Вй < 2'(хй) — ув < Рй(хй) — У, «<2ай ~: Чв,(дй) Ч- гй, (ЗЗ) в=! в О ( ай Вй (хй) < 2ай ~; Чв! (Вй )+ ай + (с(! Вй", й = 1, 2, .. ч (34) в=! гдг !с!! — — 2 !св!. Если, кроме того, множество (29) компактно лри некотором 6 >О, Хо ! ! замкнуто, а функции у(х), д!(х),,. о у (х), )у в !(х)), .. о )д,(хИ аолунепрерызны снизу на Х(6), то (хй) — в Х„.
Доказательство. Из определения (20) множества 1й и условия (32) следует -со <ус («2(х)+ в' с(дв (х))" <«2(х)+/с!!Вй «(Рй(х)+!с!!Вй (35) в' = ! пРи всех х 6 угй 1 Уй. Отсюда имеем Гй(х) ) ув — )с(! Вй" > -сю, х 6 (уййтй, или Рй„) У"„-!с(! В" > > -оо, й = 1, 2,... Таким образом, последовательность (хй), удовлетворяющая условиям (26), существует. Далее из (3!) следует в 0< айВй(х ) «<2ай ~ увг(дй)в хо 6Хв С Х сХй вутй, й = 1,2,...
в=! Поэтому с учетом неравенств (26), (35) имеем 2„(2(хй) +/с!!Вй" ( Рй(хй) + !с(!да ( Рй, + ей ч- !с/!Ву," ( (Гй(хв)+ ей+/с!!Вйо «(2, +2ай 2 су (Вй)-Ь ай+!с!!Вйов й = 1,2, в=! Отсюда получаем оценку (33). 356 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Далее, из соотношений 0 <а Вй(хй)= (Ей(хй) — Л) — (у(хй) — 7,) и уже доказанной оценки (ЗЗ) вытекает оценка (34).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
