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