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