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