Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 92
Текст из файла (страница 92)
Для иллюстрации метода барьерных функций приведем пример. П р н и е р 1. Пусть требуется решить задачу У(и)= — и- !Ц1; иш(/=(ишЕ': у(и)=и<0). Очевидно, здесь У» = О, (/» = (О). Границей множества !/ является 7 =Гр(/=(ишЕ'. у(и) =и=О! =(0), а й7 =(ишЕ'. у(и) = и с О! = !и! (/. В качестве барьерной функции для возьмем В(и)= — 1/и (и(0). Пусть а,=й ' (/с=1, 2, ...).
Тогда функция (2) будет иметь вид Р,(и)= — и — (/ги) ' (и(0). Нетрудно видеть, что здесь Ра» = 1п! Рь(и) = 2/ 'т' й и точка и„ «<о — 1/у/г удовлетворяет условиям (4) при г»=0 (/г = 1, 2, ...). Ясно также, что 1по Р„, = 1!ш У(иа) = 0 = У, 1(п1 ид = 0 = и, А» ь» А с» В качестве барьерной функции адесь можно также ваять и В(и)= !1п( — и) !. В этом случае Р,(и) =-и+ !1п(-и) !/г ' (и(0, й = 1, 2, ...), Рг» = (1 + 1п й) й ~,а точка и„= — й ' удовлетворяет условиям (4) при е,=О. И здесь(У(и„))-эУ» = О, (иг)-~ -».и = О. Перейдем к исследованию сходимости метода барьерных функций.
Теорема 1. Пусть 7 — некоторое подмножество иг (/, Ю7чь О, и У„= У. », где У = !Е(У(и), У = !п1 У(и)) — ог. (5) и ил Пусть В(и) — какая-либо барьерная функция подмножества 7, а последовательность (и„) определена условиями (4). Тогда 1!ш Рг» = 1пп Рд (иь) = 1!ш У (ид) = У, 1!ш аьВ(иь) = О. (6) Кроме того, если множество (/ ограничено и замкнуто, а У(и)' полунепрерыена снизу на (/, то (и„! сходится к «/».
Д о к а з а т е л ь с т в о. Из определения У»», Р„», неотрицательности барьерной функции и условий (4) следует — со ( У . ( У (иь) ( Рд (иь) ( Рь» + гь ( Рь (и) + еь = = У (и) + адВ (и) + е„(7) при всех ию Ю7 (/с=1, 2, ...). Так как В(и) конечна в любой точке иш(/~7, (а„) — О, то из (7) при /г- «получим У .„, ( 1!ш Рь»(1пп Рь» ( У (и), и ее (/' 7. Переходя в этих неравенствах к нижней грани по иш й7, будем иметь У»»(С!пп Рг,(!ппР»,((У„»г т.
е, 1!ш Рь» = У»». 388 мвтоды минимизации Фтнкции многих пвгюивнных [гл. э Будем предполагать, что множество У( — 0) Бишен,: б,(и)<0, 1=1, ..., т) (10) непусто. Тогда Ю~7 = У( — 0) Ф ю. Довольно широкий класс барьерных функций для множества (9) дает следующая кон» струкция: В(и) =,.,'~ <р ( — д (и)), из= У( — 0), н=т (11) где йч(1) — неотрицательная функция переменной 1) 0 такая, что 1ппср,(1) = со при всех 1=1, ..., т. В самом деле, возьмем 1- о произвольную последовательность (г,) ~в йу, сходящуюся к некоторой точке ош7.
Согласно (9) тогда найдется номер 1 (1< ~ 1 < т), для которого д, ( з) = О. Так как я (и) пол унепрерывна снизу, а я;(и,)<0 (г=1, 2, ...), то 0= 8,.1з)((1(шд.(и„) ( в О (~11шб~(иь)(~0, т. е. Пшк. (г) = О. Это значит, что В(и,)> т со г ~ <р;(-б,(з,) ) — при г —, так что функция (11) является барьерной для множества (9). При необходимости в (11) функции ~р,(г) нетрудно выбрать так, чтобы барьерная функция В(м) обладала различными полезными свойствами, такими, как непрерывность, гладкость, вы- Отсюда и из (7) вытекает 1ипр„(ид) = 1пп Х(и„) = У .
Так как ь-~аа ь-н У = У „, то первые соотношения (6) доказаны. А тогда иэ 0 ~ ~аьВ(и.)=Вэ(и,) — У(и„)- 0 при й - получим и второе из соотношений (6) . Последнее утвержденпе о сходимостн минимизирующей последовательности (и,) к Уэ следует из теоремы 2.1.1. Полезно заметить, что при доказательстве теоремы 1 были использованы не все свойства барьерных функций: соотношение 11шВ(и„) = со, где (г,)~вй7, (з,) — иш7, нам не понадоби- У ФСО лось. Поэтому теорему 1 и ряд доказываемых ниже теорем можно использовать не только как теоремы о сходимости метода барьерных функций, но и как утверждения, выражающие собой достаточные условия устойчивости нижней грани относительно возмущений (погрешностей) минимизируемой функции и некоторых типов возмущений множества, на котором ищется минимум.
2. Рассмотрим наемся~ности построения барьерных функций для задачи (1) в случае, когда П = (и ~а У,, д,(и) < О, 1= 1, ..., и); (8) здесь У, — заданное множество нз Е", функции д, (и), ..., д„(и) определены и полунепрерывны снизу на С',. Положим 7=(иш У: я,(и)=0 хотя бы для одного 1, 1<1< т). (9) $!з! метОд влгькгных Функций пуклость, простота вычисления значения функции и нужных ее производных и т.
п., если, конечно, исходные данные в аадаче (1), (8) обладают такими свойствами. Например, взяв в (11) !р(!)=1/! или !р(!)=(шах( — 1п1; 0))е (р~ 1), получим соот- ветственно В(и) = — ~— В(и) = ~ (шах( — 1п( — 8!(и)) 0))э, иенУ( — О), !=! (12) Гри=ГрП,ОТ, (13) где у определяется условиями (9), а функции (11), (12), являющиеся барьерными функциями для подмножества (, могут и не быть таковыми хотя бы для части границы У. 3.
Отдельно остановимся на условии (5), которое было существенно использовано в теореме 1 при доказательстве сходи- мости метода барьерных функций. Нетрудно привести примеры задач (1), (8), в которых функции У(и), д,(и), ..., д (и) непрерывны, множество У замкнуто и ограничено, но условие (5) не имеет места.
Например, если У(и) = и, а множество У взято из примера 2, то Уээ =— — 1~ Хэ = — 2. Если У, выпукло, функции д!(и) (!=1, ..., т), выпуклы на У„ то множество У( — О) = У'!( выпукло и функции (12) также будут выпуклыми на У( — О),— это следует из следствий к теореме 4.2.8. Далее, функции (12) будут обладать той же гладкостью, какою обладают функции я,(и) (3=1, ..., т) — у второй функции (12) для этого нужно взять параметр р достаточно большим. Может сложиться впечатление, что если функции я,(и), ... ..., я„(и) непрерывны на У„то мноя!ество (, определяемое условиями (9), будет состоять только лишь из граничных точек множества (8).
Однако это не всегда так — множество ( может содержать и внутренние точки У. Пример 2. Пусть я(и)= ~и~ — 1 при 1и! <1, я(и) 0 при 1< 1и1<2, я(и)=!и! — 2 при !и1 >2. Тогда множество У= (и ~ Е' — У,: д(и) < О) представляет собой отрезок — 2 < и < 2 на числовой оси, а !пьУ=(и!вЕ'! — 2<и < 2). В то же время мноясество У( — О) (и~Е'. я(и)<0) (лз -1<и<1)сшСУ, но У( — 0)ФшС5!, а (=(и!и У: я(и)=0) (и: 1<!и! <2) на ряду с граничными точками и = 2 и и= — 2 содержит и внут ренине точки множества г!. Таким образом, для множества (8) не всегда выполняется равенство 390 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ >ГЛ, Ь (]с =1, 2, ...).
Заметим, что в этом примере ь7( — 0)=(аи х'+у'-«1) щ с>, но У~ — 0)чь П. (Напоминаем, что через Й мы условились обозначать эамыкание множества Я.) Приводом двс теоремы, дающие достаточяыо условии для выполкспня равенства (5). Имея в виду дальнейшие применения, утверждения сформулируем для множества У(с) = (и а Пк: и ш Уо, у«(и) < С, ! = 1... т), (14) где С вЂ” некоторая постоянная. Обозначим гв(С] = !и! У(и], Ув(С вЂ” 0) = Пш Ув(С вЂ” е), щс> з +о (15) Ув (С+ 0) = 1!ш Ув (С+ е). в +о Теорема 2. Пусть длк некоторых С, ег > 0 мкохтвство С(с — ев) квпусто и й(с — О) = с(с), (16) вдв У(с — 0) = (и ш (>о> у«(и) < С, ! = 1, ..., тл).
Пусть, кроме того, «руккчия У(и) полуквпрвръьвки сверху ка мкожввтвв У(с, Тогда (17) ) в'в(С вЂ” 0) =Уз(С) = 1п! г'(и). с!с — а> Доказательство. Прежде всего, заметны, что П(с — е) ьэ У(с — 6) ж У(с — 0) ж П(С) прн всех 0 < б < е < ев, поэтому Ув (С] < >п1 У (и) < Ув (С вЂ” 6) < Ув (С вЂ” е). щс — о> Это значит, что функция вв(С) переменной С не возрастает н существует предел 1пп Ув (С вЂ” е) = Ув (С вЂ” 0) ~) >п( Т(и) )~/в (С]. (18] е- +о с!с — о> Возьмем произвольную точку и ш С(С). В силу условия (16) найдетсн последовательность (иг) «и У(С вЂ” 0).
сходящаяся к точке и. Это значит, что ныл Уа, у«(иг) < С вЂ” еы < С (еы > О, й =1, 2, ...), где !!ш евй — — 0 й (1 =1, .. °,тк).Таким образом, иг «и У(С вЂ” е«), где е, = ппп е;„)О, (ей)-т >к>к«к -«.О, и вв (С вЂ” еа) < У(иа) (й =-1, 2, ...), Отсюда прп й-~со, учнты- Однако даже выполнение условия (13), при котором функции (11), (12) будут барьерными функциями т — части границы У, еще не гарантирует справедливость равенства (5). Пример 3.
Пусть в'(и) =е, У=(и=(х, у) виЕ'=5т,: п(и)=(х'+у' — 1) (у — 1)« <О). Тогда т =Гр 5т=(и«и 0: я(и) =0) =(и«нЕ> х'+у*=1 или у =1), У,-Е*, ГрУ.=И, тэк что условие (13) выполнено. Далее, здесь с>'«Т = !>( — 0) =!и«п виЕ'! д(и)< 0) = (и: х'+уз < 1) =>п( У, поэтомуу~~= (п(У(и)= с .т = е-> ) О. В то же время Уе = )пп У (иа) = О, где и„= (й, 1) «и У метОд БАРьеРных Функций 391 9 55! вая полувепрерыввость сверху функции У(п), получим )!ш У» (С вЂ” е) е- +е = !!ш У» (С вЂ” ен) < л' (а). В силу произвольиости а вп С(С) тогда Н-ты У» (С вЂ” 0) ~ (У» (С). Сравнивая это неравенство с (18), приходим к равен- ству (17).
Теорема 2 доказава. Таким образом, если условия теоремы 2 выполнены при С = О, то ме- тодом барьерных функций (2), (4), (8) — (11) для аадачи (1), (8) можно по- лучить последовательность (аь), обладающую свойствами (6). Аналогичное утверждение справедливо для выпуклых задач (1), (8).
Теорема 3. Пусть Ув — выпуклее множество ав Е", !дуннцаа 1(а), У~(а), ..., У,(а) выпУнлы на Уе. Товда Равенства (17) спРаведливы пРа всех С > С» = шах ш! ув (н). глзлтл Пе Д о к а з а т е л ь с т в о. Как было установлено в теореме 2, функция л» (С) переменкой С ке возрастает. Возьмем проиавольпые С, е > О, С > > С вЂ” е > С». Пусть и ш У(С), ее У(С вЂ” с). В силу выпуклости Уе тогда и» = ае+ (1 — а)и ш Уе при всех и (О < и < 1). Кроме того, иэ выпук- иости ус(п) имеем р(н„) < аус(е)+ (1 — а)р(а) <и(С вЂ” е) + (1 — и)С = С вЂ” ие (О < и<1). Это значит, что н»си С(С вЂ” ае).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
