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