Ф.П. Васильев - Методы оптимизации (1125241), страница 99
Текст из файла (страница 99)
Рассмотрим задачу /(х) = — х -«!о(, х 6 Х = (х 6 Е: д(х) = х < 0). Здесь /, = О, Х, = (О). Функция Лагранжа б (х Л ) = -х Ч Л«э, х и Е ', Л 6 Е ', седловой точки не имеет, но тем не менее задача имеет сильно согласованную постановку. В самом деле, спра- ведливо неравенство /„=0< -х+>х~ = — х+(д(х)) * при всех х 6 Е, так что неравенство (21) >/2 > выполняется при с = 1, и = 1/2. Воаьмем штрафную функцию Р(х) = (шах(хз; 0))" = (хз)".
Если р > 1/2 = и, то функция Фь(х) = — х+ Аьхз", Аь > О, (Аь) — ~ со, достигает нижней грани на Хо— - Е' при хь,— — (2РА,) >/(2" », й =1,2,..., причем Р(хь ) =(2РАь) эг/12" '>, /(хь«) / = — хь Фь -/ = — (2р — 1)((2р)~гАь) /(~г ' ~> й =! 2, Как видим эти оценки лишь константамй при стейенях Аь отличасотся от оценок (22)-(24).
Интересно заметить, что с увеличением р оценки ухудша>отея. Если р= и = 1/2, Аь > 1= >с), то Ф„(х) = — х -ь А !х), Фь, — — О. Точна хь — — еь(Аь — 1) ' удовлетворяет условиям (6) и наиболее удалена от Х„=(0). Тогда Р(хг) = ~хь/ = гь(Аь — 1), /(хг) — /, = — хь, Фь(хь) — /, = гь, что совпадает с оцен- ками (31)-(33). 5. Выполнение соотношений (13) или (16), квк показывает пример 2, еще не гарантирует сходнмость последовательности (хь) из (6) ко множеству Х.
Для такои сходимости множество должно удовлетворять некоторым дополнительным условиям, Определение 5. Скажем, что множ~ство (8) задано корректными ограничениями на Хо, если всякая последовательность (хь) 6 Хо, удовлетворяющая условиям (! 6), сходится ко мйо>кеству Х. Примеры 2, 5 показывают, что одно и то же множество может быть задано как корректными, так и некорректными ограничениями. Как следует из доказательства теоремы 2, ограничения из (8) будут корректными на Хо, если фушгции д," (х), «' = 1,..., г, полунепрерывны снизу на замкнутом множестве Хо, а множество Х(б), определяемое согласно (15), ограничено при некотором Б > О.
Корректными будут также ограничения, для которых удается доказать неравенство р(х, Х) < Ь(д> (х),..., д„(х)) >Сх 6 ХО, (35) где функция Ь(С) = й(С„ ..., С,) > 0 при всех С и Е+, С ф О, й(0) = О, !пп Ь(С) = О. При- ведем важные классы множеств (8), задаваемых корректными ограничениями, для которых неравенство (35) имеет вид р(ж Х) < М( шах д+(х)) Чх и Хс! М > О, г > О.
(36) ><г<в Лем ма 2. Пусть Хо — еьтуклое замкнутое множество, функции д>(х),...,д (х) еыаУклы и непРеРыены на хо, пУсть сди>естедет такаа точка х 6 хо, что д>(х) < О,... ...,д (х) <0; пусть множество Х = (х 6 Хо. д>(х) <О,..., д (х) <О) ограничена. Тогда ч — > неравенство (36) выполняется с 7=1, М=4!аш Х ! ш!и >дс(х)>~>, 4!аш Х= эцр >и — е!. (><!<а ь, сх $15. МЕТОД ШТРАФНЫХ ФУНКЕВ4Й 334 Гл.
5. МЕТОДЫ МИНИМИЗАПИИ ФУНК1!ИЙ МНОГИХ ПЕРЕМЕННЫХ 333 Доказательство. Введем функцию у(х)= шах дг(х), В силу теоремы 4,2.7 функция 1<1(о У(х) выпУкла на Хо. Возьмем пРоизвольнУю точкУ х б Хо) Х. Тогда д(х) >О. ФУнкциЯ /(1) = = д(х+ 1(х — х)) переменной 1 непрерывна нз отрезке [О, 1[, /(О) = д(х) > О, /(1) = д(х) < О, следовательно, существует точка Го б (О, 1) такая, что /(Го) = О.
положим о = х+ Го(д — х); тогда зо — — )о-х[[х — х[, 1 — Го-[а-х[[б — х[ '. пользуясь выпуклостью функции д(х), имеем д(о) = /(Го) = 0 ( Год(х)+(1 — Га)д(х) или — Год(х) < (1- Го)д(х) или [а- х[[д(д)[ < [е — а[де(х). Отсюда с учетом х,о б Х получаем, что р(х, Х) < [х — о[ < у"(х)[о — х[(у(х)) = Му (х) что и требовалось.
Г) лемма 3 [хоффман [798[). пусть х=(хбе»; д (х)=(аг, х)-61<0, 1=1,, гп)ЕГ)д, где аг б Е", Ь' б )й, Тогда р(х, Х) < М) тах дй(х) тх б Е", М) = сост > О, 1Е 'Е» т, е, неравенство (Зб) зьтолняется с? = 1, Ха- — Е". До к а з а т ел ь с т во. Возьмем произвольнуго точку ай Х. Так как Х вЂ” выпуклое замкнутое множество, то согласно теореме 4 4 1 однозначно определяется проекция в = Рх (х) точки х на Х, К зшлаче определения проекции: д(у) = [у — х[-»)п1, у б Х, применимы теорема 4.9.3 и лемма 4.9.2, хоторые гарантируют существование таких чисел Л! > О, .. » Л > О, что » » д (в)+ Е„ЛГУГ~(в) = 1 — — 1 + ~, Лгаг =О, Л;((аг, в) — Ьг)=0, 1 =1,..., Гп. 1=! 1=1 Отсюда, учитывая, что [в — х[ = р(х, Х) > 0 имеем х — в=р(хХ) Я Л;аг, ~ д,' Лгаг[=1, 1(х)=[1: 1<1 <т, Лг>0, (аг,в)-61=0), (37) ЕГ(») ГЕГ(») Можно считать, что система векторов (ац Г Е Е(х)) линейно независима.
В самом деле, если существуют числа ?1, е б1(х), не все равные нулю, гх .Г,аг =О, то х — в= 1 Е Г(») = р(х„Х) Л, (Лг — 611)а,, где 11 =Лà — е?1 >О, ! 01(х), прн всех Г, 0<1 ( Го, зо — доста- 1ЕГ( ) точно малое число. Можно считать, что среди 7, 1 б 1(х), есть пололкительные числа, иначе изменим знаки всех ЧГ, !б1(х), Пололкнм !=а,/7,= ш)п аг/71 Тогда и! = Л,-Г?1 >О, т,. > о, ге!(*) 4 б 1(х), причем по крайней мере одно число и, = Л, — 67, = О, Таким образом, заменив в (37) л, на иг и исключив из 1(х) те номера, для которых иг =О, снова придем к равенству виде (37) с меньшим числом слагаемых.
Последовательно применяя этот прием далее, за конечное чйсло шагов придем к представлению (37), в котором система (аг, ! б 1(х)) линейно независима. Из (37) следует шах дч (х) > тах др(х) > шах д;(х) = шах ((а;, х) — ьг) = 1<ГЕ» Гег(») 1ЕГ(») геЦ») — Гпах (аг, х — в) = р(х Х) шех (а, ~ ~Л а ). (38) 1ЕГ( ) ГЕЦ») ГЕЦ ) Покажем, что величину шах (аг, 2; Л а.), где система (аг, ! б1(х)) линейно независима, 1ЕГ! ) ' Г.ЕГ(,) можно оценить снизу положительной величиной, не зависящей от х. С этой целью возьмем любое множество индексов 1 С (1,, га) таких, по векторы [аг, 4 б1) линейно независимы, и введем мнолкество ЛГ=((Л1, !б1): Л,.>0, [Л, Лгаг)=1).
1Е1 Заметим, что Л вЂ” замкнутое ограниченное множество. В самом деле, если Л =(Лг, 1 б ь ь б1) бЛГ, Л » Л, то предельным переходом в (39) легко убедиться, чта Л бЛ . Следовательно, ЛГ замкнуто. Покажем ограниченность Л, Допустим противное; пусть найдутся Л" ц Л, й = =1,2,., » [Л" [-»ао. Тогда последовательность Гль =Л" /[Ль[, й= 1,2,..., ограничена: [р [= 1. Выбирая при необходимости подпоследовательность, можем считать, что [р") » ГГ, [)1) = 1. поскол ьку ) е, л аг ! = 1, то ( л; р, аг ) = 1/[ л " ) -» О = е; р; аг, где р = (ро, ! и 1) т О, Однако 1ЕГ зто противоречит линейной независимости (аг, ! б 1).
Следовательно, ЛГ ограничено. е Отсюда и из Ь1", (х) = гпах (де(х); О) < [уг (х)) = дй (х), Ьз (х)=шах(-д;(х);0) < )УГ(х))=дг+(х), 1= гп 41,..., г, приходим к неравенству (41). Лемме 4 доказана.П Другие классы множеств (8), заданных корректными ограничениями, читатель найдет в [84; 527; б70!. б. В лемме 1 был выделен класс задач (1), (8), имеющих сильно согласованную поста. новку (см. неравенства (20), (21)), Следуя [б70[, приведем еще один содержательный класс таких задач. Л е м м а 5. Пусть функция /(х) на множестве Хо удоелетгоряет условию Гегьдера )/(х) — /(у)[ < 5)х — у[ Чх, у б ХО, б > О, 0 < а < 1; (42) ограничения, задающие множество (8), корректнь1 на Хо и удовлетворяют нераеенст- еу (Зб).
Тогда задача (1), (8) имеет сильно согласованную постановку, причем неравен- ство (21) гыполняется при с, =... =с, = ЬМ, и = ау. Доказательство. Возьмем пройзвольную точку х б Х, По определению р(х, Х) = = )п! )х — о[ для любого г > 0 найдется такая точка х, б Х, что [х — х,[ < р(х, Х)+ г. Тогда с учетом условий (Зб),(42) имеем ЬМ ~ х(д,.~(х)) а+/(х) — /, > ЬМ ( шах ур(х)) +/(х) — /(х,) > 1=1 * 1<!С» ' > 5(р(х, Х)) — й)х — х,[ > 5(р(щ Х))" — 5(р(х, Х) + е)а.
Пользуясь произволом г > О, отсюда при з -» 0 получим ем д; (д,+(х))»т+/(х) — /, >0 лги б ха. 1=1 'ГСЬ *'';1 Лемма 5 доказана. Г) !з Не множестве ЛГ рассмотрим функцию д(Л, 1) = шах(аг, 2; Л а ). Убедимся в том, геГ что д(Л,1) >О при всех Л б ЛГ. В самом деле, если существует Л =(Ло, у б1) б Л, что д(л,1) (О, то (аг, я л.а.) (О при всех 4 б1. умножим эти неравенства на ла, 1 ц 1, и Г' Е Г сложим; получим равенство [ Е Лга;[=О, противоречащее определению Л .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
