Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 99
Текст из файла (страница 99)
(зз) Если Х, т» О, то Х, = Хь, — — (х 6 Хс. Фь(х) = Ф»,), (34) Если, кроме того, Хо — замкнутое множество, функции /(х), д;" (х) полунепрерыгны снизу на Хо, (гь) — О, й а, — предельная точка (х ), то о, 6 Х,, Доказательство. Из (25) при р=и, Аь >!с! имеем Фь(х) — /,>О, хбХо, тая что Ф»„> >/„> -со, и последовательность (хь), удовлетворяющая условиям (6), при г» > 0 существует, Йз (28) при р = и, А» > !с( сразу получаем оценку (31). Из нее и из (29) при р = и следует оценка (32).
Из (14) н (25) при р = и, Аь > !с! с учетом того, что ш!и ( — с г + Аьг") = О, *>о приходим к соотношениям (33). Докажем равенство (34). Возьмем произвольную точку х„б Х„. Тогда Р(х ) =0 и Фь(х ) =/(х ) =/„= Ф»„так что х„ц Х»м Следовательно, Х„с Х»х Пусть теперь хь„б Х „, т, е. Ф»(х»„) = Фа,. Это значит, что условие (6) при хь — — хь, выполняется с 㻠— — О/Тогда йз оценки (31) при 㻠— — 0 получаем Р(хэ,) = О, т. е. х», 6 Х. Отсюда, из (33) и из того, что /(хь,) = Ф»(хь,) =Фа, — — /„, следует, что хь, 6 Х„. Следовательно, Х, с Х,.
Равенство (34) доказано. Последнее утвервкдение теоремы вытекает из оценок (31)-(ЗЗ) и доказывается так же, как аналогичное утвер»хдение в теореме 2. Г! Из теоремы 6 следует, что случай р = и интересен тем, что при точной реализации метода штрафных функции (3), (б), (9) решение исходной задачи (1), (8) может быть получено при конечных значениях штрафного коэффициента Аь. Определение 4. Пусть А — некоторый класс задач (!). Говорят, что штрафная функция Рь(х) является точной на классе А, если существует номер го такой, что множество ешений задачи Р Ф»(х)=/(х)+Рь(х)- !п1, хбХо пРи всех й > Уо совпадает со множеством Решений пРоиэвольной задачи (1) из класса А.
Типичным примером точной штрафной функции на классе задач (!), (8), у которых функция Лагранвка имеет седловую точку, является функция Р»(х) = Аь х; двй(х), А» > (Л*) (294), в =.! Это следует иэ теоремы 6 при р = и = 1, с = Л' и леммы 1. О точных штрафных функциях см., например, [85; 266; 294; 562] Рассмотрим примеры, которые показывают, что оценки, полученные в теоремах 5, 6, не могут быть существенно улучшены на классе задач (1), (8), имеющих сильно согласованную постановку.
П р и м е р б. Рассмотрим задачу /(Х) = — Х -в !П(, Х 6 Х = (Х 6 Е'1 д(Х) = Х < 0). Здесь /в =О, Х, =(0). Функция Лагранжа Ь(х, Л) = -а+ Лх, х6Х = Е', Л 6 Лов - (Л 6 Е'. Л > 0) ймеет седловую точку (х, =О, Л' = 1), так что согласно (20) неравенство (21) выполнено при и = 1, с, = 1, г = 1. Возьмем штрафную функцию Рь(х) = А»(дт(х))г = А»(шах(х;0))г, р > 1, Аь > 1, (Аь) — в со. Тогда функция (3) будет иметь вид (О, р=и=! Фь, — — 'а! Фь(х) = в' и' — (РАь) в, Р > 1, причем нижняя грань достигается з точке хь, — — 0 при р= 1 и х, =(рА ) !в!г !! при р > 1, й = 1,2,...
Последовательность (хь) удовлетворяет условиям (5) или (6) с з„ = 0„ причем ( О, р=1, '( (РА») гв!г !1, Р>1, ь* " ( — (РА») ~/!г !1, Р>1. Сравнение этих точных равенств с оценками теорем 5, 6 при 㻠— — 0 показывает, что в случае р = 1 оценки (3! ), (32) точны, а в случае р > 1 оценки (22)-(24) точны по порядку и отличаются от точных оценок лишь константами при степени Аь.
Если гь > О, то при р = 1 в качестве точяи хь, удовлетворяющей условиям (6) и наиболее удаленной от Х„здесь можно ваять хь — — гь Г(А» — !), А=1,2,.... Тогда Р(хь)=ха —- гь(Аь — !с1), /(хь)-/в= — х»вЂ” - — !с!гь(А»вЂ” — ~с!), Фь(х») — /, = (Аь — 1)хь = г», й = 1,2,..., что совпадает с оценками (31)-(33). Если гь > О, Р = 2, то точка х = (1/(2А»)) 4(г»/Аь) /З УдовлетвоРЯет Услоаиам (6), пРичем А ар(хь) = А»хьз = (1/(4Аь)) Ч- г»+(г/А»)' х, /(х») — /, = — хь, Фь(х») — У'„= гь — (! /(4А»)), что также свидетельствует о том, что оценни (22)-(24) на классе задач с сильно согласованной постановкой не являются грубыми.
Этот же пример показывает, что в теореме 6 требование Аь > !с1 не может быть ослаблено. В самом деле, если Аь < 1 =!с), р= 1, то Ф„, = — со, если х»е А, =! =!с), р= 1, то Фь(х)шО, Фь„— — О, Х»„— — Е' и нарушено равенства (34). П р и м е р 7. Рассмотрим аадачу /(х)= — х-в!п1, хеХ=(хчЕ:д(х)=х <0).
Здесь /, = О, Х, = (О). Функция Лагранвка Ь (х Л ) = — х+ Лха, х 6 Е ', Л б Е !, седловой точки не имеет, но тем не менее задача имеет сильно согласованную постановку, В самом деле, справедливо неравенство /, = О ( -х+ (х) = — х+(д(х) ) ! /х при всех х 6 е ', так что неравенство (21) выполняется при с = 1, и = 1/2. Возьмем штрафную функцию Р(х) = (шах(хх;0))" =(хэ)", Если р > 1/2 = и, то функция Фь(х) = -х+ Аьхх", Аь > О, (Аь) -в оо, достигает нижней грани на Хо = Е ' при хь, — — (2рАь ) !/!зг !1, й = 1, 2,..., причем Р(хь ) = (2рА» ) Х Лхг /(хь ) — /„=-х»а Фь, — /„= — (2р — 1Н(2р)~гА») !/!хг О, 5 = 1,2,... Как видим эти оценки лишь коистантамй при стейенях Аь отличаются от оценок (22)-(24).
Интересно заметить, что с увеличением р оценки ухудшаются. Если р = и = 1/2, А» > 1 = !с), то Фь(х) = — х+ А .!х), Ф»„— — О. Точка х» — — гь(А» — 1) ! удовлетворяет условиям (6) и наиболее удалена от Х„=(О). Тогда Р(х ) = !хь) = г»(А„— 1) !, /(х„) — /, =-хь, Фь(х») — /, = гь, что совпадает с оценками (31)-(33).
5. Выполнение соотношений (13) или (16), как показывает пример 2, еще не гарантирует сходи масть последовательности (х» ) из (6) ко множеству Х. Для такои сходимости мновкество доля»но удовлетворять некоторым дополнительным условиям. Определение 5. Скажем, что множество (8) задано коруехтными ограничениями на Хо, если всякая последовательность (хь] 6 Хо, удовлетворяющая условиям (!6), сходится ко мйожеству Х. Примеры 2, 5 показывают, что одно и то вне множество мовхет быть задано как корректными, так и некорректными ограничениями.
Как следует иэ доказательства теоремы 2, ограяичення из (8) будут корректными на Хо, если функции д,". (х), в = 1,..., г, полунепрерывны снизу на замкнутом множестве Хо, а множества Х(б), определяемое согласно (15), ограничено при некотором б > О. Корректными будут также ограничения, для которых удается доказать неравенство р(х, Х) < Ь(д!+(х),..., д„"(х)) вх6 Хо, (35) где фУнкцин А(!)=А(з>,..о!,)>0 пРи всех !ЕЕ+, 1~0, 5(0)=0, Ош 5(!)=О. ПРиведем важные классы множеств (8), задаваемых корректными ограничениями, для которых неравенство (35) имеет вид р(х, Х)<М( шах д,+(х)) в/я 6 Хс, 34>0, г >О.
(Зб) !<»< лемма 2. пусть хо — аыпуклое замкнутое мнохсастго, функции д!(х),...,д (х) выпУклы и нгпРгдыгньв на Хо, пУсть сУЩествУет такал точка х 6 Хо, что д!(хн) < О,... ..., д, (х) < 0; пусть мнажестго Х =(х 6 Хо. д!(х) < О,..., д (х) < 0) ограничено. Тогда и нграгенстго(36) аыполняетса с т=1, М=йашХ( ш!и !д,.(х)!), йаш Х= эцр (и — о!. »!<оявп в ) ,всх 334 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 6 15. МЕТОД ШТРАФНЫХ ФУНКЦИЙ Доказательство. Введем функцию д(х)= вах д»(ж). В силу теоремы 4 2 7 функция 1 Е» е< т д(х) аыпУкла на Хо.
Возьмем пРоиэвольнУю точкУ х «Хо ЛХ. Тогда д(ж) > О. ФУнкциЯ /(З) = = д(х+ 1(х — х)) йеременной г непрерывна на отрезке [О, 1], /(0) = д(х) > О, /(1) = д(д) < О. следовательно, существует точка (о с (0,1) такая, что /(го) =О. положим п = х+ го(х — х); тогда го=]о-х]]ж — х] 1, 1 — (о=]п-х]]х-х[ '.
Пользуясь выпуклостью функции д(ж), имеем д(о)=/(эо)=0(год(х)Ч(1 — го)д(х) или -(од(х) <(! — ~)д(х) или]о-х[]д(х)]<]о-х]д "(х). Отсюда с учетом ж, и «Х получаем, что р(х, Х) < ]х — о] < д~(х)]о — х](д(ж)) 1 = Мд+(х), что и требовалось.П Лемма 3(Хоффман [796]). ЛустьХ=(х«ЕЕ: д!(х)=(аг, х)-Ь» <О, 1=1,,. ив)ф(г», где а! с Е", Ь' « В. Тогда р(ж„х) < м! !пах дг (х) чх «е", м! — — сонэ(>0, 1<»<п т.
е, неравенство (36) выполняется с 7 = 1, Хо — — Е", До к а за т ел ь с т в о. Возьмем произвольную точку х бХ, Так как Х вЂ” выпуклое замкнутое множество, то согласно теореме 4.4.1 однозначно определяется проекция ю = Рх(х) точки ж на Х. К задаче определения проекции; д(у) = [д — х]-и ш1, у «Х, применимы теорема 4.9.3 и лемма 4.9.2, которые гарантируют существование таких чисел Л( > О, .. и Л > О, что х в д(ю)+ ~, Лгд!'(ю) = ю х + Е, Л»аг =О, Л;((а», ю) — Ь!) =О, ! =1,,т. 1=1 ]ю — 4; 1 Отсюда, учитывая, что ]ю — х] = р(х, Х) > 0 имеем х-ю=р(хХ) Е; Л;аг, ! 2 Л!Е1]=1, 1(х)=((; 1 <! (в, Л» >О, (а»,ш) — Ь»=0).
(37) Ш1(п)»Е1(п) Можно считать, что система векторов (аг,! « 1(ж)) линейно независима. В самом деле, если существуют числа чг, ( с1(х), не все равные нулю, Я ч!а; =О, то ж — ю= Е 1(п) =Р(х, Х) Е (Л! — 17»)аг, где и,. = Л! — 11» ><О, ! «1(х), пРи всех 1, 0< ! < (о, (о — доста- » Е 1(п) точно малое число. Можно считать, что среди яп ! «1(х), есть положительные числа, иначе изменим знаки всех 7», ! «1(х). поло»ким ! = а,/7, = в!и а»/7» тогда и,. =л»-гч,. >О, т,>о, »е»( ) ! «1(х), причем по крайней мере одно число и, = Л, — эч, = О, Таким образом, заменив в (37) Л» на и,. и исключив из 1(х) те номера, для которых и! =О, снова придем к равенству вида (37) с меньшим числом слагаемых.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
