Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 93
Текст из файла (страница 93)
Тогда с учетом выпуклости функции У(а) получим л"» (С) < ш! л (а) < У» (С вЂ” ие) ~ тес-е) 4 т(па) » (и т (в) + (1 — и) л'(а) для всех а ш У(С), е ш У(С вЂ” е). Следова- тельно, л» (С) < !и! л (и) < л (С вЂ” ие) (ил (С вЂ” е) + (! — и) у (С) я; п(с-о! <У»(С)+и[У»(С вЂ” е) — У (С)] для всех и (0<и<1, 0<с<э < < С вЂ” С»).
Отсюда при а -«+ 0 с учетом ыовотояяости л'» (С) получаем ра- вевства (17), что и требовалось. 4. Пусть множество (т задается условиями П = (а ш Е": нем Уе, уд(а) < О, ! = 1...,, вц ут(а) О, ! = та+ 1, ..., в). (19) Если это множество ке имеет ввутреввих точек, то реалиаация рида мето- дов мивимиаации (вапрпмер, методов из 1 3 — 3, 1! и др.) иа У может стать аатрудвительпой или даже невозможной. В то же время при приме- вевии методов 1 13, 14 к задаче (1), (19) могут получиться такие после- довательвости (нь), которые ке принадлежат множеству У и нарушают ка- кие-либо из огравичеиий р(и) <О, у;(и) 0 яа кедопустимо большую ве. личину, В таких свучаях может оказаться целесообразвым использование метода барьерных фувкций. Заметим, что этот метод выше изложен для задачи (1), (3) в пред- положевии, что множество У( — 0), определяемое условиями (10), непусто.
Однако такое предположение для множества (19) при тп < в ке имеет смы- сла. Поэтому описанный выше метод барьерных функций к задаче (1), (19) иепосредственяо непримеяим и требует модификации, обобщения. Опи- шем один иа возможных здесь подходов [178), Введем последовательность расширенных множеств Уь = (а си Пе: у;(а) < О», ! = 1, ..., иц [р (а)( ~< Оь, ! = тл + 1, ..., в), (20) где Оь>0 (й=1, 2, ...), !!ю йд — — О.
Так как Ушу» (3=1, 2,,), то и» из У чь !а следует !'» Ф Я (й = 1, 2, ...). Предполагая, что функция У(а) » определена на множестве () уд,рассмотрим последовательность аадач а=х (21) 7(а)-«!п1; аж Уа» й = 1, 2, 392 МЕТОДЫ МИНИМИЗАПИИ ФУНКПИЙ МНОГИХ ПЕРЕМЕННЫХ !ГЛ, З Для решения аадач (21) могут быть использованы различные методы минимизации, Мы адесь остановимся лишь на методе барьерных функций. Обозначим т» = (и»и У» и выполняется хотя бы одно из равенств уг(и) = 6», ! = 1, ..., ац уг(и) = О», уг(и) = — 6», у = т + 1, ..., з).
(22) Поскольку В с 1'», В П 1» = !2!, то В<= У»»»1» чм ютг! (« = 1, 2, ...). В ка честве барьерной функции В»(и) подыволсества 1» возьмем г г В„(и) = ~яр~, р („— у (и))+ ~р ~р;(В„+у (и)), иену,у, (28) г-»! и+1 где функция юг(г) определена, конечна, неотрнцательва и не возрастает пРи г ) О, 1»ш гуг(г) = со (г =1...„г). НапРимеР, в качестве Рг(г) можг- +о но взять грг(г) = г-', чг(г) = (шах( — 1пг; 0))о (р ) 1). Далее, составим функцию Р»(и) = г(и) + о»В»(и), и ги У»'»1», (24) где (а») — барьерные коэффициенты: а» ) 0 (« = 1, 2, ° ..), (а») -»0.
В отличие от рассмотренного выше варианта метода барьерных функций, здесь мы будем требовать, чтобы барьерные коэффициенты (а») и параметры (О») стремились к нулю согласованно в следующем смысле: 1!ш а рг (9„) = О, ! = 1, ..., з. (25) «гг Предположи»т, что г«в = »п1 у (и) ) — со (!с =1, 2, ...). Так как В»(и) ) '« ~0, а») О, то Р»(и) )!(и) при всех иге У»»,т», и поэтому Р« »п1 Р,(и) )г«в) — со (к =1, 2, ...).
С помощью какоголибо У«чт« метода минимиаации определим точку и», удовлетворяющую условиям и«»ЕУ« 'у«Р«(Р«(и«)я,Р«в+с«, «=1,2, ... (26) где (е») — некоторая положительная последовательность, сходящаяся к нул»о; если Р«(и ) Р«, то в (26) допускается е» = О. Метод барьерных функций для аадачи (1), (19) описан. Теорема 4. Пусть функции Р»(и), В»(и), множества У», ц» определены соотношениями (20), (22) — (24), выполняются равенства (25) и, кроме тово, 11ш л« = г ) — оо, г«в = 1п1 г" (и), гв =1п1 Т (и).
(27) «ы Г«О Тогда для последовател»ности (и»), определяемой условиями (26), справедливы соотношения 1!ш Р = 11ш Р„(и«) = 1!ш г (и«) = гв, 1пп а В«(и ) = О. (28) ««-»ы «-«ы «-» Если, кроме того, множество В(б) =(иш Вв'. уг(и) (б, »=1, ..., и; (уг(и)) (б, ! = т+1, ..., г) (29) компактно при некотором б ) О, множество Пс замкнуто, а функции 61(и), ..., у (и), )у т~(и) ), ..., )уг(и) ~ полукепрерыекы снизу на В(6), то (и«)-» Пв — множество решений задачи (1), (19).
5 ш) метОд ВАРЪИРных ФункциЙ 393 Д о к а з а т е л ь с т в о. Нз определения УХ,Ра»,неотрицательности Ва(и] и условий (26) имеем со < г"а < г (иа) я, Ра + за я, (~Та(и)+ел=У(и)+ааВ (и]+е,, ижр ьу„3=1,2,... (30) Так как функции срс (») из (23) не возрастают при» ~ О, то срс (Оь — Юс(и)) < < р (Оа) (»=1, ..., ); р (О л-у (и)) = р,(О,) (»=' +1, ...
) для всех и аи П, Поэтому в силу условия (25) а 0<а В„(и) < 2аа ~~~ ср<(О,).+О, л-+о», и»и (Г. (31) с 1 Тогда при й-с-со из (30) с учетом условия (27) получим а» в~ 11ш т'а < 1пв ать ~г'(и) при всех и»п(т. д — ь у (и»)< 1!ш у»(иа)( 1!ш О„=О, » 1, ...,ш, т с» (у»(и ) ~~1!ш ~у»(иа )~я 1!ш Оа=О т сс у (и ) = О, » = + 1, ..., Таким образом, и»<и (с. Отсюда с учетом полунепрерывности снизу г(и) на У(6) получим г»< г (и») ~ 1»ш г (иа» 1»ш г (иа) =У», т. е. г (и»)= — тг =г» или и» ви (с». Тем самым показано, что любая предельная точка последовательности (иа) принадлежит П».
Отсюда следует, что 4иа) -с- П», Теорема 4 докааана. При некоторых более жестких ограничениях на данные задачи (1), (19) можно получить оценки погрешности метода (20) — (26). Теор ем а 5. Пусть длл вада»и (1), (19) сараввдливо нвравснство — оо < г'»4,7 (и) + ~~~~~ с<(у~+ (и)) суиав П с с<~»Ос и) О (32) » 1 (см. онрсдсланив 14.3 и леммы 14.1, 14.5). Тогда посл»до»отак»ность (иь), Переходя к нижней грани по и ж П, отсюда имеем 1!ш са» = г».
Тогда а-с»с иа (30) следует 1!ш с"'а(ид) = Пш г'(иа) = г'». Наконец, 0 < а»В»(иа) = а-сс» а-с ю = Ра(ил) — У(иь) — 0 при »с-т со. Равенства (28) доказаны. Пусть теперь выполнены все условия теоремы. Так как (Оь)-»0, то У»с: П(б) при всех д )»сг. А тогда и» <и В(б), »с ) да. В силу компактности П(6) последовательность (иа) имеет хотя бы одну предельную точку.
Пусть и» вЂ” произвольная предельная точка (иа), пусть подпоследовательность(иа -ьи». В силу аамкнутости Па тогда й»евП.Далее, из полунеатс о' прерывности снизу функций ж(и), ..., 3»(и), (у»+»(и) )с ° ° с (уа(и)! " ус ловия иь»н Уа следует, что 394 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 1ГЛ, З определяемая условиями (20) — (26), существует и справедливы оценки з — )с( 01~(» (иа) — г' ° <Рз(из) — у~<<2аз ~~0~ фв(Вз)+ез,, (ЗЗ) 1 1 О~ааВА(2аз ~ фг(01)+ее+)с) 0", у=1,2, ..., (34) 1 1 ° дв (с) ~ (св(. Если, кроме того, множество (29) компактно при не 1=1 котором б ) О, Пз замкнуто, а функции 7(и), у~(и), ..., у»(и), )у» ы(и) ) ..., ) у, (и) ) полукепрерывны снизу на П(6), то (иа) -~- (7».
Докавательство. Ив определения (20) множества Уь и условия (32) следует со < з (з (и) + ~ с (ут (и))»к,з'(и) +) с) В»(РА(и) +(с) В» (35) при всех и гн У1171. Отсюда имеем Рг, (и) > л» вЂ” ) с)10~1) — оо, и гн Уз'~уа, или Ра») з» вЂ” ) с) 0»а) — оо (й =1, 2, ...). Таким образом, последовательность (иь), удовлетворяюгцая условияи (26), существует.
Далее иа (31) следует 0 в аьВа (и,) < 2оз ~в~~ фг(ВА), и ш П» с Пс Пз'~уз, й = 1, 2, . Поэтому с учетом неравенств (26), (35) имеем з»(з(и,)+(с) 0»~Р,(из)+)с( 0",(Р +е,+)с) О»( 5 ~рз(и )+ее+)с)10»(7~+ 2аь ~~ фе(Вь)+ее+(с) О», й=1,2,. Отсюда получаем оценку (33). Далее, из соотношений 0(адВд(иь) =(Рз(из) — з») — (з" (а ) — з ) и уже доказанной оценки (33) вытекает оценка (34). Последнее утвержде« кис доказывается так же, как аналогичное утверждение теоремы 4. 5. Отдельно остановимся на условии (27), которое существенно использовалось при доказательстве равенств (28). Нетрудно привести примеры задач (1), (19), когда зто условие ве выполняется. Пример 4.
Пусть 1(и) = е ", П= (игнЕ' Пы у(и) = (из — 1))4 у( (1+ иг)-' (0). Ясно, что и = (и гп е1: ) и)(1), з = 1п1з (и) = е и Возьмем Уь = (и ш Ег. у(и) ( Вь = 1)йг). Так как и, = т гы Уь при т > > й, то Пш з (и,) = 0 = з'а (й = 1, 2, ...). Таким образом, здесь Пш за»= ° -~ г й-та» 0(е = з» вЂ” условие (27) не выполняется.
Заметим, что в рассмот— 1 ревком примере множество П(6) = (игнЕьг у(и) (6) не является компактным ни при каком 6 ) О. Приведем две теоремы, дающие достаточные условия для выполнения условия (27). Теорема 6. Пусть множество Пз замкнуто, функции 7(и), у~(и), . ° ° » ум(и),!зы+1(и) ),. ° ., )уг(и) ) определены и полунепрерывныснизу на Ёз, МЕТОД БАРЬЕРНЫХ ФУНКЦИЙ 395 Кроме того, пусть множество (У(С) = (исмйн: иги(Уе, дге(и) ~(С, 1=1, ...,в) непусто, а множество (У(С+ сс) ограничено и вамкнуто при некотором е, ) О.
Тогда (см. обогначенин (15)) 1пп г'» (С+ е) = г» (С+ 0) = в (С). (36) в +о Доказательство. Так как (у(С) <:-(у(С+6) ш(у(С+в) при любых 0 < 6 < с< ее, то .У (С+ с) < г»(С+6)<д»(С). Такиы обРазом, ункция г» (С) переменной С не возрастает и существует предел (ш г» (С+ с) = г' ° (С+ 0) < г» (С). Возьмем проиавольную последовав +в тельность (ев), 0 < сь < сг, сходящуюся к нулю. При сделанных предположениях множества (У(С+ сь) ел (У(С+ ес) при каждом й = 1, 2, ... ограничены и замкнуты.
Согласно теореме 2ЛА тогда существует точка иъш(У(С+ег) такая, что д(гоа) = г»(С+су) (й=1,2, ...). Поскольку (У(С+ с,) — компактное множество и уел ш (У(С+ еь) ш (У(С+ сг), то последовательность (шь) имеет хотя бы одяу предельную точку. Пусть ю»вЂ” какая-либо предельная точка (юг). Не умаляя общности, можем считать, что сама последовательность (юа)-» ю». По построению говги(у(С+еь), т. е. уог гн ууг, уг~ (уса) ~( с+ е» (у = 1, ..., г).
используя аамкнутость множества Вн полунепрерывность рассматриваемых функций, отсюда при й-» -» оо получаем ю» сн (У (С). А тогда .У» (С) ~< в' (го») < 1(ш У(юа) а с» = 1(шв»(С+са) й у» (С+О). Сравнивая с ранее установленным вера. а св венством г'» (С+ 0) < г» (С), получаем равенство (36).
Нетрудно видеть, что при С = 0 из (36) вытекает условие (27). 6. Метод барьерных функций на практике иногда используют в сочетании с методом штрафных функций. Предположим, что множество (У аадаетси в виде (у = (и ев (ус. 'дг (и) < О, у = 1, ..., гН лг (и) = О, у = ю + 1, ..., г; Ьу(и) < О, у = 1, ..., У; Ьу(и) = О, у = У + 1, ..., т), где (Ус — гаданное множество иг Е", функции рг(и), Ьу(и), а также минимизирующая функция у(и) определены на Ои Ограничения, аадаваемые функциями яг(и), будем учитывать с помощью штрафных функций Р (и) = ~ч", (шах (дг (и); 07)Р+ ~~~~ ) дг (и) )Р, и вн (Ув, р)~ 1. г-1 г=т»-~.1 Введем множества И'ь = (и ш (у~ й,(и) < Оь, у = 1...,, у; )йу(и)( < Оь, у = у + 1, ..., т), Тв = (и ш 1угк выполняется хотя бы одно ив равенств йу(и) = Ом у = 1,..., т; йу(и) = — Ог,у = У + 1,..., т), й = 1, 2, ...
В качестве барьерной функции подмножества Тг воаьмем Ва (и) = ~ Фу(01,— Ь (и))+ ~в гуу(Ой+ Ьг (и)), и ш И'у,' Та, у-т у=у+в где функция сру(г) определена, неотрицательна и не воарастает при г ) О, 11ш ф (г) = оо (у = 1, ..., т). Рассмотрим последовательность аадач г- +в Гь(и) = 7(и) + Аьр(и) + агВ»(и) -»1п(; и»и Ига туг, 396 мктоды минимизации югнкции многих пвгкмкнных !гл.
з считаа, что (Аа г), (ал), (Оз) — положительные последовательности, схо. дящнеся к нулю. Пусть Еа = !о1 Еа (в) ) — ос (й = 1, 2, ...). Опрежа ' те делим точку вз из условий одеи И'а~, ув, )за(ид)()за +е, (37) где еь) 0 (в=1, 2, ...), Вше„=О (если Е (иа) =Еле, то в (37) а.~ю допускается аз = 0). Предлагаем самостоятельно сформулировать и доказать для метода (37) теоремы, объединяющие теоремы 4 и 14.2, 5 и 14.5, 14.6. Различные аспекты метода барьерных функций исследованы в (8, И1, 159, 178, 307, 330, 338). Упражнения. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
