Ф.П. Васильев - Методы оптимизации (1125241), страница 97
Текст из файла (страница 97)
Ото!ода получаем При й — «оо будем иметь и — и, = (1, 1), Фй(и ф~~ 3. Нетрудно видеть, что и„— решение исходной задачи. В самом деле, ~'(и,) = (3; 3), (У'(и,), и— — и ) = 3(х-1)+ 3(д — 1) =0 для всех и Е Х. В силу выпуклости множества Х и функции 1'(и), согласно теореме 4.2.3, тогда и„— точка минимума !'(и) на Х, причем 1'(и,) =1;=3= 1пп Фй(и„). Таким образом, в рассмотренном примере метод штрафных функций сходится. Пример 2. Пусть у(х) = е * — «1п1; хйХ =(хЕ Е': д(х)=хе *=О). Здесь Х = (0) = Х„, Г". = 1.
Возьмем штрафную функцию Р„(х) = йд'(х) = = йх'е '* и положим Фй(х) = е + йхйе 2*, х Е Х = Е!. Так как Ф (х) > 0 при всех х ЕЕ', 1!т Ф (х)=0, то Ф,.=!п1фй(х)=0. В качестве точки х, й * х»» * в удовлетворяющей условиям (6) при г =- е '+ й'с '", здесь можно взять х = й, й=1, 2,... П лучим !!п! Х(хй)=0<Х,=1, !!т р(х„Х )=ос. Таким й й х» й»» образом, выясняется, что метод штрафных функций не всегда сходится. Пример 3, Задача: ~(и)=(х — 1) — у — «!п1, иеХ=(и=(х,у,г)е Е Хв = Ев д (и) = дй < О, дй(и) = — х ( О, дз(и) = х' — дг ( О).
Здесь у; = 1, Х„= Х = (и = (О, О, г) Чг > 0). Возьмем штрафную функцию такую: Фй (х) = $15. МЕТОД ШГРАФНЫХ ФУНКЦИЙ 327 =( 1) 'у+ йд + й(п!ах( — в; 0)) + й(«пах(х~ — дг 0))2 и Е Х Ей й =1, 2,... Очевидно, Фй(и) > тт ( — у+1у') = — 4— „«уи Е Е~, причем в точке 1 улв' ий =(1, —,2й) значение Фй(и„) = — 4, Следовательно, Фй„= — 4 > — оо, й = 1,2,..., и точка и, удовлетворяет условийо (6) при г. =О. Однако, 1!т 2"(ий) = !!т 4й — — 0 < Л = 1, р(и„Х„) = !п1(1+( — „) +(2й — х)') >1, й = 1, 2,..., и 1пп р(ий, Х,) = 1, т. е.
метод штрафов не сходится. В этой задаче функции г'(и), д,(и), д (и), д,(и) являются полиномами, мнойкество Х выпукло и имеет внутренние точки, нижняя грань Фй, достигается. Приведем пример задачи, в которой Ф„„ = — оо, й = 1, 2,... Пример 4. Задача: Г(х)хх — х'- !п1, хяХ=(хяХв — — Е'! д(х)=!х~< < 0). Здесь |, = О, Х„= Х = (0). Возьмем штрафную функцию Фй(х) = — х + + й!х!.
Ясно, что ф„, = 1п1 Ф,(х) = — оо, й = 1, 2,..., и условие (6) теряет ххл' смысл. В то же время, если в этой задаче мы выберем другую штрафную функцию, как, например, Фй(х) = — х2 ! (й + 1)х' или Ф (х) = — х'+ йх', то получим Фй, =0 > — со, причем нижняя грань достигается в точке хй =О, й=1,2,... 3 а м е ч а н и е 1. Напомним, что неравенство (6) написано в предположении, что выполнено условие (4). Если у'., = !п! Г"(х) > — оо, то из (3) и х х Х» из Рй(х) > 0 тх е Хь следует, что Фй„> — со, й = 1, 2,..., при любом выборе штрафной функции.
Отметим, что в примерах 1, 2 выполняется условие Г"„, > — оо, в примерах 3, 4 — Г'„, = — оо. Для конкретных классов штрафных функций можно указать другие достаточные условия для выполнения (4). Так, например, если функция Р(х) взята из (9) или (9 ), то Ф(х, А) = Г(х)+ АР(х) < Ф(х, В) = =,г(х)+ ВР(х) ЧА < В, Чх Е Хй, Поэтому Ф,(А) = !п1 Ф(х, А) < Ф,(В) х й Хр ЧА < В, т. е.
функция Ф„(А) монотонно растет (точнее, не убывает). Отсюда следует, что если Ф,(А) > — оо при некотором А, то ф„. = Ф„(А) > — оо для всех й, для которых Ай > А. Перейдем к исследованию вопросов сходимости метода штрафных функций для задачи (1), (8). Для определенности все формулировки и доказательства теорем проведем для штрафной функции (9), хотя некоторые из нижеследующих утверждений будут справедливы и для более широкого класса штрафных функций. Теорема 1.
Пусть функции 1(х),д,(х), 2 =1,..., в, определены на множестве Х, а последовательность (хй) определена условиями (3), (4), (6), (9). 7огда ! пп у(хй) < 1пп Фй(х, ) = 1пп Фй < у', Если, кроме того, Г"„= !п1Г'(х) > — оо, то * Х Р(хй) = 'й '(д,. '(х ))" = 0(Ай '), й = 1, 2,..., «=! йт д(хй) <О, 2 =1,...«т; 1пп д(х )=О, 2=уп+!,...,в.
(13) 329 $15. метОд штРАФных ФункциИ 328 Гк З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Д о к а з а т е л ь с т в о. Так как Р(х) > О, то из (3), (6), (9) имеем, 7'(х, ) < 7( х„) + А„Р( хь ) = Ф, (х„) < Ф, + е„< < Фь(х) + е„=у(х) + АьР(х)+ е„Чх Е Хо«й = 1,2, Отсюда, переходя к нижней грани по х Е Х и учитывая, что Р(х) = О, х Е Х, получим Г(х„) < Ф,(х.) < Ф„„+ е„< ~, + е, й = 1, 2,... (14) При й «оо из (14) вытекает (11).
Пусть теперь 7"„> — со, Так как 7, > 7"„„, то 7. > — со, а из (3), Р„(х) > 0 следует (4) (см. замечание 1). С учетом (14) имеем О < А, Р (х, ) = Фь (хо ) — Т(хь ) < 7, + е„— 1".„, й = 1, 2,... или ограничено хотя бы при одном значении 6 > О, то для последовательности (х„) выполняются равенства (7), Доказательство. При сделанных предположениях для последовательности (х,) соотношения (11)-(13) сохраняют силу. Пусть ««, — какая- либо предельйая точка последовательности (х,), пусть (х„) - о,. Заметим, что о„Е Хо в силу замкнутости Х . Тогда с учетом полунепрерывности снизу указанных в условии теоремы функций из соотношений (13) получим д«(о„) < 1!ш д,.(х, ) < !пп д,.(х.) <О, !д(х)/ < 1пп !д(х„)/ = !пп !д(х„)) =О, о=1,,т, Г = го + 1,..., г.
Следовательно, о. Е Х. Тогда с учетом (11) имеем 7", < 7(о,) < !пп 7(х„) < < !!гп ! (х ) < 7„, т. е. !пп ! (хь ) = 7(о«„) = 1, или о„Е Х, Наконец, пусть множество (15) ограничено при некоторых 6 > О. Из соотношений (13) следует, что х,) Е Х, для всех й > йо. Это означает, что (х„) имеет хотя бы одну предельную точку. Тогда, как было выше показано, 0<Р(х„)<(7„+апре,— ~„)А,', й=1,2,... ььо Оценка (12) доказана. Из нее следует, что Нгп Р(х,) =0 или !1гп д,'(х,)= = О, 1 = 1,..., з.
Вспоминая определение (10) для д,. (х), отсюда получим соотношения (13). П Примеры 2, 3 показывают, что в общем случае неравенства в (11) могут быть строгими. Приведем достаточные условия, когда справедливы равенства (7). Т е о р е м а 2. Пусть Хо — замкнутое множество из Л", функции ,Г(х), д,(х),..., д„(х), !д„~ «(х)),..., !д,(х)! полунепрерь1вньг снизу на Х,, 7,„= !п1 Г(х) > — со. Пусть последовательность (х,), определяемая усло«« виями (3),(6),(9), имеет хотя бы одну предельную точку. Тогда все предельные точки (х ) принадлежат множеству Х„точек минимума задачи (1), (8). Если, кроме того, множество Х, =(х: х ЕХо, д,'(х) < 6, 1=1,..., г) (15) все предельные точки (х„) принадлежат Х„.
Следовательно, !!ш р(х„Х,) = = О. Из тех же рассуждений и неравенств (11) вытекает первое равенство 7). Теорема 2 доказана. П я иллюстрации теоремы 2 рассмотрим Пример 5. Пусть ,!(х)=е "' — «!и1; хеХ=(хек: д(х)=я=О). Здесь 7", = 1, Х = (0), Функции 7(х), д(х) непрерывны на замкнутом множестве Х, = Е, 1'„„= 1п1 е *=О, множество Х, =(х Е.Е'. (х) < 6) огранив« чено при любом 6 > О. Таким образом, все условия теоремы 2 выполнены. Возьмем штрафную функцию Р(х) =(д(х)) = хз и положим Ф„(х)=е '+йхз, хеЕ', й=1,2, Нетрудно видеть, что Ф„(х) сильно выпукла на Л ', поэтому Ф,, = !п1 Ф„(х) > з! > — со.
Пусть (е„) — произвольная неотрицательная последовательность, стремящаяся к нулю. Определим точку х, из условия Фь(х,) < Ф „+е„, й = = 1, 2,... Для получаемой таким образом последовательности (х )* согласно теореме 2 имеют место равенства (7). 3. Нетрудно видеть, что рассмотренные в примерах 2 и 5 задачи по существу одинаковые: минимизируется одна и та же функция е-* на одном и том же множестве Х = (0), и отличие лишь в том, что в примере 2 множество Х задается ограничениями д(х) = хе-" =О, а в примере 5 — д(х) =- х = О.
Тем не менее, в примере 2 метод штрафных функций расходится, в примере 5 сходится. Отсюда заключаем, что для сходимости метода штрафной функции важное значение имеет способ задания множества Х: ограничения, задающие множество Х и штрафные функции этого множества должны быть как-то согласованы с минимизируемой функцией 7(х).
О п р е д е л е н и е 2. Скажем, что задача (1), (8) имеет согласованную постановку на множестве Х,, если для любой последовательности (х„) е Е Хо, для которой !пп дТ(хь) =О, 1=1,,е, (16) имеет место соотношение 1пп 7'(х„) > ~, = ш1 Г(х). (17) Отметим, что в п(1имере 5 задача имеет согласованную постановку на Ж«, а в примере 2 такои согласованности нет. Теорема 3. Пусть Ф (х) =7(х)+ А,Р(х), где Р(х) определена формулой (9), пусть Фь„=!и!Фь(х), й =1, 2,... Тогда для того чтобы !!ш Фы=~;, (18) необходимо, чтобы задача (1), (8) имела согласованную постановку на множестве Х,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
