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