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