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