Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 104
Текст из файла (страница 104)
Вспомним, что (х, ) — «О, (Л, ) — «Л еЛ(0). К последовательности подпространств Пэ, применим лемму 1. Согласно этой лемме существует надпространство Пс Ев Пз,, б!ш П) гпах(п-[1(0)[; О). Возьмем произвольную точку Ьо Е П. ь ю П!, — -П, г)(р = (Ь, «)) е Е" х Е: (-ыд — е-, Р) =О, ! е 1(0) !«1,(л,)). С учетом оценки (31) имеем б!ш П!, ) и+1 — 1(0), Чл, 0 < л < еа.
Далее, из включения (32) следует П), с 1«ег О,'(л,) П(р: ( — 'л — ' —, р) =О, ! «1(0) ) 1;(л,)) = =(р =(Ь, и) «Е" х Е: ( — "— Л-, р) = (д! (х,), Ь) — д. (ей)9 =0, ««1(0)) дд (л) б!ш Пе, > шах(⫠— [1(0)[; 0), О < е ( за, Пз, с)гегО'(л,)=(Ь ЕЕ"; (д,'(х,), Ь) =О, в Е1(0)), 0< а < за '41 . ,г[ :-] (34) По определению Ел Пз, точка Ьо является предельной для некоторой последовательности з (Ьь), Ь, «Пз, .
Без умаления общности можем считать, что сама последовательность (Ьь) сходится к Ьа. Тогда из (38) при з = ез, Ь = йь и й — «со имеем (д (0), Ьа) = О, Ч( Е 1(0), т. е. Ьо е (гег ьв'(О). Следовательно, П с 1«ег св'(0). Наконец, учитывая, что да,л(х) = Уз(х)+ +4]х[э1 +8ххт+4[х — лЬ[з1 +8(х — лй)(х — зй)т из (39) при л=л„й= Ь ЕП и й — аа в полУчим ((ЛаУл(0)+ 2 Л,.двл(0)йо,йо) РО, т. е. (Е„(О,Л)Ь,Ь) >О Чй«П. Это значит, что '=! подпространство П обладает свойствами (!4) — (16) и является сопровождающим падпростран- ством для точки Л. Следовательно, Л = Л(й) ЕЛ,(0). Тем самым показано, что любая отличная от нуля предельная точка семейства конусов (Л (л,), л >О) при л — «О принадлежит Л„(0). Теперь мы можем доказать утверждение (18). С этой целью воспользуемся равенством (30).
Напомним, чта аадачу (24), (25) мы рзссматрйваем при произвольном фиксированном Ь уз О, Ь Е К(а) Гг(й е Е"! ()(а), Ь) < 0), где конус К(а) определен согласно (19); а =О, 1(0) = («; « = 1,..., л). Тогда да(ей) = да(0) + (да (0), ей) + 2 (дал(0)лЬ зй) Ч- а(ез) = = 7"(0) + з() '(О), Ь) -1- †(ул(0)й, й) -1- а(лз) ( — лз(ул(0)Ь, Ь) -1- а(ля), д(лй)=дз(0)+(д,'(О), лй)+2е (дл(0)зЬ, ей)+а(с ) < 2е (д "(0)Ь, Ц+а(з ), ««1(0), Подставим эти неравенства в (30). Учитывая, что Лм > О, в = О, .. ч т, Ч«'(Х,) > О, получим Лав[2з (1 (0)Ь, Ь) ! а(л )]+ 1 Л, [2з (д«(0)Ь Ь)+а(л )]> в ) Ло да(лй)+ х Л вд«(зй) = Ла ф (Хв) р О. Отсюда, разделив на лз > О, имеем Лав(1 (0)Ь, Ь) -! Е Лзв(д! (0)й, Ь)+2Лов з + 2,' 2Л„~з ) О.
г=! л Перейдем в этом неравенстве к пределу при л= ля -«О. Учитывая, что Л, -«Л = Л(й) ЕЛ„(0), получим ((ЛоУл(0) + 2 Лзд;л(0))Ь, Ь) = (Е„,(0« Л(й))Ь, й) ) О. «=! Так как Л (0) конус, то ГЛ.(Ь)- ЕЛ (0). Следовательно, шах (Сю(а Л)й, й) > (С (а, Лел.(а),!11=! — [ — ]- ) й, Ь) > О. Неравенство (18) и, следовательно, теорема 2 доказаны в предположении, [Л(Ь)]1 ' что в точке а локального минимума задачи (1З.А) все ограничения дз(х) < О, « =1,..., и«, активны. Рассмотрим общий случай, когда среди этих ограничений имеются неактивные, т. е.
д! (а) < 0 для некоторых номеров «, 1 < в < гп (возможность, когда все такие ограничения неактивны, здесь не исключается). Так как функции дг(х) непрерывны, то число Т в задаче (19.А) можно считать столь малым, что дг(х) < 0 Чх, [х — а[ < т, «(е 1(0). Рассмотрим задачу; до(х)-«!п(, хЕИг! — — (хеЕ": [х-а[< Г, д;(х) <О, ! «1(а)г)(1 < «< т), дв(х)=0, «=т+1,...,в), (40) полученную из задачи (19.А) исключением неактивных ограничений.
Заметим, что Иг! с И", так как если х Е И'), то дз(х) < 0 Ч! 9 1(а) в силу выбора 7 и поэтому х Е И'. Отсюда, учитывая, что а Е рв), имеем 'ш! 1(х) > !пГ 1(х) =1(а) > !п( 1(х). Это значит, что 'ш! 1(х) = вен«лен« вен« е к'« !и( 1(х)=1(а), т, е. точка а — решение задачи (40). Однако в задаче (40) все ограничения вен д,. (х) < 0 в точке а активны, и, следовательно, к этой задаче применима уже доказанная часть теоремы. Поэтому конус Лагранжа Л(а) и конус Арутюнова Л„(а) задачи (40) непусты, и для функции Лагранжа С(х, Л) = 2„ Л,.дз(х) этой задачи справедливо неравенство ' е г(а) * !пах (С (а, Л)Ь, Ь) > 0 Чй Е К(а) г«(1'(а), Ь < О). (41) Л Е Л„(в), (Л ! = ! $17.
МЕТОД БАРЬЕРНЫХ ФУНКЦИЙ 349 348 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЪ|Х Каждой точке Л = (Ло, Л«, > е Х(е)) поставим в соответствие точку Л = (Ло, ., ч Л,) по правилу Ло — — Ло, Л; = Лг, «е Г(е), Лг =-О, «4 Г(е). Образуем множества Л(е), Л„(е), состоящие из всех тех точек Л, которые получены с помощью указанного правила из точек Л множеств Л(е), Л,(е) соответственно, Нетрудно убедиться, что так построенное множество Л(е) явлрется койусом Лагранжа задачи (1З.А) в точке е, а множество Л,(е) — конусом Арутюнов»и причем для каждой точки Л е Л,(е) а качестве сопровождающего подпространства П(Л ) меж>!о взять подпространство П(Л) для соответствующей точки Л еЛ (е). Неравенство (18) является следствием неравенства (41) и равенства Е,(е, Л) = Е, (е, Л) для л>обых соответству>ощих точек Л е Л(е) и Л е Л(е).
Теорема 2 доказана. ь> Тем самым доказаны и теоремы 2.4.2 и 2.4,3. Упражнения 1. Пусть Я = (Оо,..., О,), где Я« — симметричная матрица их и, > =О,..., з, К =(и еЕ": (Огх> к) <О, « = 1,..., т; (О«х, х) =О, > = т+ 1,..., «), Пусть Л„(0, Я) — конус Арут>окова задачи У(х) = (Оож к) — »пй ее К в точке е =О. Доказать, что многозначное отображение Л, Я вЂ” > П(Е'«>) замкнуто (полунепрерывно сверху). 2. Пусть е — точка локального минимума задачи: >"(х) -> 1п|, х е Х = (а е Е": д,.(е) < <О, « = 1,..., т; дг(я) =О, « = т 1-1,..., «), где д (е) = (а«, Е(е)), Е: Е" >Е' — заданное отображение, а>,..., о, — заданные векторы из Е . Доказать, что тогда конус Л„(е) мох«но "у заменить на другой конус Л (е), в котором коразмерность сопровождающих подпространств П а т не превышает г, т. е.
шщ и) щах(п — г;О). Указание. заметить, что ду(к) =(Р'(е)) а«, и, следовательно, (д,.'(е), Л) = 0 >>Л е 'кегР'(к) (подробности см.[44!). 9 17. Метод барьерных функций 1. Идеи метода штрафных функций могут быть использованы для постро ения минимизирующих последовательностей задачи У(х) †>!и[, х е Х, которые обладают какими-либо дополнительными свойствами. Скажем, можно строить последовательность (х„), каждый член которой принадлежит множеству Х, но находится вне некоторого заданного «запрещенного» подмножества у с Х. В качестве «запрещенного» множества 7 может служить, например, граница Гр Х множества Х или какая-либо часть границы. Дело в том, что прн применении того или иного метода решения задачи (1) при Х ф Е" может случиться, что каждое получаемое приближение хь будет принадлежать Гр Х.
Однако если структура границы множества слишком сложна, то реализация такого метода может потребовать большого объема вычислительной работы и, кроме того, сходимость метода может оказаться очень медленной. В таких случаях можно попробовать как-то построить «барьер» вблизи всей границы 7 = Гр Х или какои-либо ее части 7 (или какого-либо другого заданного подмножества 7 с Х), который исключал бы возможность попадания очередного приближения х, на "г. 0 п р е дел е н не !.
Пусть у — некоторое подмножество множества Х. Функцию В(х) назовем барьером или барьерной функцией подмножества Т, если В(х) определена, конечна и неотрицательна во всех точках х Е е Х ), Т, причем !!ш В(н,) = со для всех последовательностей (е„) е Х ( у, которые сходятся к какой-либо точке е Е у. Заметим, что в определении 1 подразумевается, что Х |у ~ И.
Это значит, что если 7 = Гр Х, то !и! Х = Х >> ч ф И. Заметим также, что в точках х е 7 ба ьерная функция В(х) не определена (можно принять В(х) = оо,х е у). ользуясь теми же конструкциями, которые использовались при построении штрафных функций, нетрудно выписать барьерные функции для множеств у, задаваемых ограничениями типа равенств или неравенств. Например, если у=(х ЕЕ": хЕХ д(х)=0), где д(х) непрерывна на Х, Х1 у ~И, то в качестве барьерной функции здесь можно взять В(х) = [д(х)[ ', или В(х) = [д(х)! ', или В(х) = и|ах( — !п[д(х)[;О). Если же у = (хе Е": х Е Е Х д(х) < 0), где Х 1, 7 ф И, д(х) непрерывна на Х, то можно принять В х) = (д(х))», р > О, или В(х) = [!и д(х)[, х Е Х 1 у и т.
п. ерейдем к описанию метода барьерных функций для решения задачи (1), предполагая, что подмножество у С Х и некоторая его барьерная функция уже заданы. Введем функции Рь(х) =у(х)+а„В(х), х6Х ( у, )с =1,2,..., (2) где (а ) — положительная последовательность, сходящаяся к нулю. Величины (аь) из (2) называются барьерными коэффиг(иенлгами. Рассмотрим последовательность задач Рь(х) †+ !и[; х е Х Л у, )с = 1, 2,... (3) Обозначим Р„, = !и! Ргг(х), )с = 1, 2,... Будем предполагать, что в исходной х|« задаче (1) ~„= !и[ у(х) > — оо.
Так как Рь(х) > у(х) при всех х Е Х Л у, то х Рь > У, > — оо. Тогда УсловиЯ хь Е Х >1 -~, Рь(хь) ( Р„„+ кь, й = 1, 2,... (4) определяют последовательность (х„), где зь > О, !пп кь =0; если окажется, что Рь(хь) = Раю то в (4) допускается кь = О. Поскольку, как обычно, мы подразумеваем, что функция У(х) конечна во всех точках х е Х, то согласно определению 1 для любой последовательности (и,) Е Х >г у, (е„) — > и е 7 справедливо равенство !!ш Р (и„) = со при каждом фиксированном )с = 1, 2,... Таким образом, функция Р„(х) неограниченно возрастает вблизи 7. Поэтому следует ожидать, что при фиксированном й функция Рь(х) вблизи 7 не может принимать значения, близкие к Рь„ и точка х,, определяемая условиями (4), не будет расположена на слишком близком расстоянии от у.
В то же время благодаря тому, что барьерные коэффициенты (а„) — > О, не исключается возможность того, что с увеличением номера )с точки х»л постепенно «преодолевая барьер», будут приближаться к у. Для приближенного решения задачи (3) при фиксированном й и определения точки х„, удовлетворяющей условиям (4), могут быть использованы различные методы минимизации. В частности, если Т = Гр Х и Х Л 7 = !и! Х ФИ, то для решения задачи (3) может быть применен, например, градиентный метод (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
