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