В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров, Сборник задач по оптимизации (теория, примеры, задачи) (1155771), страница 13
Текст из файла (страница 13)
Пусть в (з) Х и У вЂ” бпнаховы пространства, ~, ы БР(х), Г ы ЯР(х, У) и 1ш Г(х) — замкнутое подпространство. Тогда, если х~1осш|пз, то существует ненулевой множитель Лагранжа Х = (х, у*) еэ В +' Х У~ такой, что выполнены: а) условие стационарности Ы (х, Х) =0; б) условие дополняющей нежесткости а,Цх) = О, в) условие неотрицательности а, >О, 1Р-'О. 0 Положим Г'(х) = Л, ~~(х) = х;, т)0. Не ограничивая обшности, можно считать, что ~,(х) =О, 1~0. Действительно, если ~,(х) Ф О, то слелует рассмотреть функцию К(х) =),(х) — т,(х), а если ~;,(х) ~0, то это ограничение можно отбросить, ибо если х ы 1ос ш1п з, то очевидно, что хев 1осш(пз„где (,-е ограничение отброшано.
Таким образом, можно считать, что условие дополняюшей нежесткости выполнено (следует положить Х~ 0 для тех 1 ~ 1, для которых ~,(х) чь 0). А) Вырожденный случа й. 1шА есть собственное подпространство У. Тогда по лемме о нетривиаль- 74 ности аннулятора найдется у* ~ 0 такой, что (у~, Лх) 0 ~г'х с=в- Л~у~ = 0 с=~.2':,(х, Х) = О, где л, (О, у*). Б) Пусть Л отображает Х на У. Рассмотрим вспомогательную задачу гпах (х;, х) -э. 1пг; Лх = О. о<~~ти (з') Д е и ма. О ~ аЬз ппп з'. О<~ Пусть 0 Ф аЬз ппп з'. Это означает, что имеется элсмент х, для которого (х;.
х) ~0, Лх= О. Но тогда по теореме Люстерника найдется функция г( ): ( — Х„ т.о) - Х такая, что !!гав)!1Iй- 0 при 8- 0 и Г(х+~х+ + гИ)) 0; значит, Ь(х+ 8х+ г(й)) = й(х,*.,х)+о(й) ~0, ~=вО, для достаточно малых 1, что противоречит условию, согласно которому х ~ 1ос гп1п з. И> В) Результат теоремы следует из цепочки равенств, являющихся следствием теорем выпуклого анализа и леммы об аннуляторе ядра регулярного оператора: 0 я= аЬз гп1 и з' ~=~ 0 ~ д (1пак (х;, х) + 6 К ег Л) = = дгпах (х,, т) +дб Кег Л=-сопч~хо,..., х„1+(КегЛ) -е=~- т т с=~ Зу*~в У*, а о— = В++',"~~я; = 1,,~~а;х;+Л*у~ = О.
~> 1=о 1-о С л е д с т в и е. Пусть при условиях гладкости теоремы оператор Е'(х) сюръективен. Тогда множество мнот жителей Лагранжа Л = ~Х =- (я, у*) ~ ао— : В~+',,~~ а, =1, ~-о ~и 2~~ аА'(х) + (Г'(х))~ у~ = 0 является непустым выпук- 1 — — о лым компактом. 1 з Непустота следует из п. В) доказательства теоремы Расшотрим симплекс В-~а ~ В~~') В а~-1~ и отображение у:,~~-э. Х~, задаваемое формулой у(а) = = .'Еос,х~~, По определению, (а, у~) =адов Л ~с" фа) + + Л*у* О. В силу замкнутости ?пт Л* и равенства КегЛ" = (0) (й* е- =Кег Лв =~ (Л* Ь*, х,' = 0 Ух =:» (Ь*, Лх> =0 Ч х=~й* = 0).
применима теорема Банаха. По теореме Банаха отображение Л*: У*- ?гпЛ* имеет обратное, значит, подмножество Л* 'ер(г.) компактно, а значит, компактно и множество ((а, у*) ез Л) = ((а, — Л*ер '(а)))а~ Х). Выпуклость Л очевидна. И> 4.4.2. Теорема двойственности в задаче о кратчайшем расстоянии. Пусть Х вЂ” нормированное пространство, А с= Х вЂ” непустое выпуклое множество.
Величина рА (х) = 1п? (Пх — Ъ|!1$ еБ А) называется расстоянием от точки х до множества А. '? е о р е м а. Величина рА(х) допускает следующее двойственное представление: рА(х) = зпр ((х*, х> — гА (х*)! ~! х*~~ = 1). ~ Из определения конволюпии сразу следует, что рА(х) (Х 9 6А)(х), У(х) = 1~х~!. Применяя теорему Лежандра — Юнга — Фенхеля о преобразовании копволюции и формулу (Ю=оВ*, где В* — шар сопряженного пространства, получаем, что 1р = оВ*+ гА. Вследствие того, что рА ограничена сверху и снизу (О~рА(х) ~ «!!х — ф,~~, где ф, — произвольная точка из А), функция рА непрерывна всюду на Х, и, значит, по теореме Фенхеля — Моро йм (рА)(х) =(Ир)(х) = гпр ((хв, х> — гА(хв) !х* ее В*).
4.4.3. Лемма о сопряженном конусе и лемма Хоффмана. Л е и ма. Пусть Х и У вЂ” банаховы пространства, Л: Х- У вЂ” линейный сюръективный оператор из Х в У, х1, . „,, х, — элементы сопряженного пространства Х* и Зхе= КегЛ, (х,, х> (О Ч( (условие Слейтера). Пусть Тогда К* =- х" е:— Хв ) х" +,~~а,э, + Л*у* = О, а, )О, у*е=-У~ . 1 1 76 ~ Ооозначим П,=(х~ (х;, х~~::О).
Тогда 1п1 П,'Ф'Ф и К = Д П~ Ц КегЛ. Применив теорему о конусе, сопряженном к пересечению конусов, и лемму об аннуляторе ядра регулярного оператора, получим о П П; й КегЛ = ~оП;+ о(КегЛ) ~-1 $-1 = — (сопч ~х,...., х„') + 1ш Л*), ~> Замечание. Утверждение леммы верно и без условия Слейтера (см. АТФ, с. 277).
Лемма Хоффмана. Пусть выполнены те же условия, что и в лемме о сопряженном конусе. Тогда для функиии расстояния от точки х до К справедливо неравенство в рК(х) < С,~ (х,, х)~ + ~~Лх~~ ° с=1 < Применив формулу об опорной функции пересечения, формулы гП =6сопех, и формулу конволюции индикаторных функций, получим гК=г Д П; Й КегЛ = 9 гП; ®гКегЛ= 1=1 г=г $ * = ® 6 ( соне х Д В 6 1ш Л~ = = 6(х'"~х" н=-сопелях~„,,х,) + 1шЛ~), Следовательно, по теореме двойственности для рК по- лучим рК (х) = зпр (х~, х) ~ х* = Хи,х~ + Л*у*, а~ ) О, ~х*~~<1 . Подпространство Ь = 1(п ~х,, ..., х, ) + 1ш Л~ замкнуто как сумма конечномерного пространства и замкнутого, 1ш Л~ (Кег Л)~, аннулятор всегда замкнут, Значит, Ь банахово.
Оператор Л~: В ХУ*-+ 1, Л,(~х, у~) = — у = .~ х,х~ + Л у, линеен, непрерывен и сюръективен, ~ — 1 отображает К" Х 1'* на Е,, По лемме о правом обратном сугцествует М,.' Ь вЂ” В' Х У* такое, что Л~ М~ 1., 77 !!ЗХ,ХВ!! <С!!ХВ!!.
ТОГДа, ЕСЛИ !!ХВ!! ~ $, тО ~!ЛХ1Х*~кв,д,в в = Д ~ сс;1+ !~ у*~! --- С. Таким образом, в выражении для »=1 р можно считать, что 0 ~ а» ~ С, !!уЧ ( С, откуда рК»х)(хар( ~ах, »- Л"у",х) 0(а,(СДу"$$(С)( »=1 в ( С У~ (х;, х)+ + ~! Лх !! . ~> » 1 4.4.4. Лемма о минимаксе. Пусть Х и У вЂ” банаховы в пространства, Л: Х вЂ” У вЂ” сюръективный оператор, х; е= и= Ха, ~ = 1...,, г, ан= Й'. Определим функцию Я: В'Х Х У вЂ” В равенством Я(а, у) = 1п1 п1ах (а» + (х», х)). (1) Лх-!-г=О 1~» ~в Лемма. Если шах (х;,х)~)0 для любого х~КегЛ, 1~»<в то величина Яа, у) допускает следующее двойственное представление; 5 (а, у) = гЛ (а, у) = зпр ~ а»а; + (у*, у) 1(я, у*) я= Л, »х«1 гдв Л-!»«, у*»ш»»~» т" ) ат»».'„Д а,= », Д ах~ » а'ух = В~.
»=1 При этом 1Ы в И) достпгается на некоторол» (быть может, не единственном) х = х(а, у) и существует такое С) 0 (не зависящее от а, у), что при подходящем выборе х(а, у) !!х(а, у)!! < С(!а! + !'у!!). Первая часть легко слелует из теорем выпуклого анализа, О второй части см. АТФ, с. 280. 4.4.5. Необходимые условия высших порядков и достаточные условия в задаче с неравенствами. Здесь продолжается исследование задачи и. 4.4.1. При этом далее используются обозначения, введенные ранее: х;, Л, Л. Т е о р е м а (Левитин — Милютин — Осмоловский).
Пусть в задаче (з) п. 4.4.$ Х и У вЂ” банаховы пространства, ~»ез.01(%), Ря.О'(Я, У) и 1п»Г'(х) = У. 78 Необходимое условие минимума. Если х~ оа1осш(пз, то для любого вектора Ьвгь К (х~ (хг,х).::О, г = О, 1, ..., т, Лх = 0) выполнено условие неотриг(ательности игах У,,(х, Х) (Ь, Ь) в О. хгзл Д о с т а т о ч н о е у с л о в и е м и н и м у м а. Если Л Ф ~ь 8 и выполнено условие положительности с некоторым а>О: пгах.У„,(х, Х) (Ь, Ь)~~а)11г~~' уЬ~К, хел то хое1оспг1пз.
Непустота гиножества Л, а также его компактность и выпуклость были доказаны в п. 4.4Л. < Необходимость, Снова считая, что 1(х) О, г ~ О, рассмотрим задачу 1(х) пгах (1,(х),, 1 (х)) - 1пг, Г(х) О. (з,) Л е и м а. Если х ез 1ос шгп з, то х ~ 1ос пг1п з,. <)< Если х Ф1ос гшп зо то ага) О Зхе: 1хе — х ~~ (е т (хе)= О, 1, (хе) ~ О, г)~О=-,~'х ф 1ос пггп 3. 1> ! ' Пусть Ьо= К. Положим а, — 1; (х) 1Й, 1г), у = - Г" (х) [Й, Й1, Ч" (Й) -игах 2' (х, Х) (Ь,1г1.
2 г."=л Рассмотрим задачу игах ((х";, х) + а;) — ~1п1; Лх (- у = О, (з,) Вследствие сюръективности оператора Л и леммы из доказательства теоремы и. 4.4.1 пгах (х„х)' 0 ух~ КегЛ, о<Ыт т. е. к задаче (з,) применима лемма о минимаксе. По лемме о минимаксе найдется элемент $ =$(Ь), обладающий свойствами игах ((хг, $) + а;) = Ч" (1е).
о~мт По формуле Тейлора в силу соотношений ЛЬ О, Л$+ + у О получаем при г ~ 0 Г(х (- гй -(- г2$) = Г(х)+ $Г'(х)Ь+ РГ'(х) $-(- ~2 + — Г" (х) [Ь, Ь) + о (г2) = о (Р), Согласно теореме Люстерника сушествует отображе- ние ф: У- Х окрестности точки х такое, что Г(х+ + ф(х)) 0 и, кроме- того, !~ф(х) ~~ ~ К!~Г(х) ~~. Полагая г(Г) ф(х+ гй+ г2$), получим: Г(х+ гй+ ~'$+ г(г)) = О, Ж)!! - К~~Г(х+ гй+ ЮЬ = о(Р). Тогда, применив формулу Тейлора к ~~ и используя (1), получаем (вспомнив, что (х;, Ь) а О, ~ Ъ 0) г'(х + гй + г2$ + г(г)) = шах (г (х~, Ь)+Р((х~, $)+а;)+ о~~< в + о (Р) а: 'Р гпах ((х~, $) + аД + о(г2) = г2Ч'(Ь) + о (Р) (0 О а1~ж при малых Е, если допустить, что Чг(Ь) (О в противоре- чии с леммой.
Необходимость доказана. Достаточность. Покажем, что существует 6~0 такое, что условия )',(х+й) ~0, 1~0, Г(х+й) =0 (2) противоречивы при !1й~! (6, ЬФО. Из этого сразу будет следовать, что хе1осгп1п з. Итак, пусть вектор Ь удов- летворяет условиям (2) и 1~Я к 6,. Тогда по формуле Тейлора ~~(х + Ь) = (хай) + — г (х) (Уг, Ь) + г. (Ь), е~~ О, Г(х + й) = Лй+ 2 Г" (х) (Ь М + г (Ь) и, полагая аг 2 ~~ (х) (Ь, Ь| + г1 (Ь), 1 ~~ О, .у — Г" (х) (Ь, Ц+ гЯ, получим (х~,й) + а~ =~~(х+ Ь)(0, ~) О, Лй+ у = 0; (3) при этом 80 !а~! ~ С,1!ЬР, !!у!! ~ С,!!ЬР. (4) Рассмотрим задачу гпах ((х,, х) + а~)-~-1п1; Лх+ у = О. (зз) Оа 1<В Из равенства,~~ и;(х„х) !-(Л*у*, х) = О, а~ В:О, 1=О т т 2~ а; = 1 вытекает, что Д и; (х,",х) = 0 ухе= КегЛ. 1 О 1=О Отсюда шах (хьх) «~О ух~ КегЛ, и, значит, к зада0~1Кт че .(з,) можно применить лемму о минимаксе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
