Алексеев В.М., Тихомиров В.М., Фомин С.В. - Оптимальное управление (1050536), страница 45
Текст из файла (страница 45)
Поэтом)~ 8" (г) = зир (Лг ~ ЛА ~( с, Л '= О). (8) В частности, отсюда видно, что 8" (Ь) — значение двойственной задачи (4). В) Завершение доказательства. Функция 8 не может равняться тождественно +со, ибо 8(0)(0, так как нуль — допустимый элемент в задаче сх — 1п1, Ах(0, х»0; следовательно, дош8ФЯ. Возможно одно из двух: 1) 8(г) > — ао, Уг или 2) существует г, для которого 8(г) = — со. Случай 1) в свою очередь распадается на два: 1а) ЬЕ4от8 и 1б) Ь(догп8. В случае 1а) 8 — собственная функция и значение задачи конечно. Вследствие замкнутости 8 по теореме Фенхеля — Моро (п. 2.6.3) 8" (Ь)=8(Ь) и теперь из (6) видно, что двойственная задача (4) имеет то же значение, что и прямая (2) и, и частности, совместна. В силу теоремы существования решение существует в обеих задачах.
В случае 1б) 8 (Ь) = + оо, т. е. задача (2) не совместна. Снова из теоремы Фенхеля — Моро получаем, что 8" (Ь)=8(Ь) и, значит, задача (4) совместна, но ее значение бесконечно. В случае 2) 8 (г) = — оо для всех г ~ дою 8 (см. упражнение 8 п. 2.6.2). По определению 8'(Л)ам-)-со и 274 Вее(г) — оо. В частности, В" (Ь) = — со, т.
е. задача (4) несовместна. Если ЬЕбошЗ, то задача (2) совместна и ее значение бесконечно: В(Ь) = — вп. Если же 5(дошЯ, то 3(Ь)=+оп задача (2) несовместна. Альтернатива полностью обоснована. Вернемся теперь к случаю 1а). Там, как было доказано, существуют решения задач (2) и (4). Сбозначим их х и Л соответственно. Доказано, что значения задач равны: сх=ЛЬ, т. е, выполнено (5) и, значит, Л (Ах — Ь) = ЛАх — ЛЬ = ЛАх — сх = (ЛА — с) х, т. е. выполнено (6).
Далее, если х и Л вЂ” допустимые элементы (т. е. х>0, Л~О, ЛА (с, Ах>Ь), то сх> ЛАх> ЛЬ. Поэтому, если сх=ЛЬ, то х н Л вЂ” решения задач. Далее, если Л(Ах — Ь)=(ЛА — с)х, то сх=ЛЬ, т. е. х и Л вЂ” решения задачи. Таким образом, если х и Л вЂ решен, то выполнены и (5) и (6); если х и Л допустимы и выполнено либо (5), либо (6), то х и Л вЂ решен задач. Теорема полностью доказана.
ф у и р а вс н е н и е. Во что превращается в рассмвтриваемоа ситуации теорема о минимаксе (следствне 3 и. 3.3.2)? 3.3.4. Теорема двойственности для задачи о кратчайшем расстоянии. Лемма Хоффмана и лемма о мииимаксе. Пусть 1' — нормированное пространство, В ~=' 'г' — непустое подмножество К. Величина Зв(т))=р(т), В) = !п(фу — т)9 (1) а а в называется расстоянием от точки т( до множества В. Исследование функции Вв (т)) является одной из основных в теории приближений (см. 1841). Если  — выпуклое множество, мы получаем задачу выпуклого программирования.
Доказываемая ниже теорема двойственности имеет в анализе многочисленные приложения. Итак, пусть  — выпуклое множество, (Далее оно фиксировано, и мы опускаем индекс В в обозначении функции В.) Тогда функция т(в~В(т() является 8-функцией такой задачи: 1~г~! — 1п1; у — г=г), уЕВ. 42) Приведем (2) к стандартному виду задачи выпуклого программирования (см. (4) в п. 3.3.1). Для этого поло- жни Х=УХУ, х=(у, г), Ях) (г1„'Лх=г — у, Л: Х .1', А =(х=(у, г) ~у 6 В) и тогда задача (2) примет вид 7,(х) 1п1; Лх+т1=0, хЕА. (3) Из сказанного вытекает выпуклость функции Я (следствие 1 и.' 3.3.2). В дальнейшем нам понадобится следующее важное геометрическое понятие. О п р е д е л е н и е.
Опорной функцией множества В ~ У называется функция вВ: )" — й, определяемая равенством вВ(у)= "р<у' у> уев Теорема двойственности для задачи о кратчайшем расстоянии. Величина 5(г)) допускает следующее двойственное представление: Я(ц)=р(Чэ В)=зцр(<у'з у> — вВ(у')$~у'~1~~1).
(4) Доказательство. Очевидно,. что Б(т)))О, т'т). С другой стороны, Я(п) ~!)у,— т)1, где у,— любая точка из В. Значит, 5 — ограничена сверху и снизу и, следовательно, непрерывнд всюду на 1' (предложение 3 и, 2.6.2). Теперь можно применить теорему двойственности из п. 3.3.2, Поскольку в (2) неравенства .отсутствуют, функция Лагранжа имеет вид .У(х, у', 1) =1г(+ <у', г — у>. Из формулы (1.1) п.
3.3.2 получаем В (Ч) = зцР (<У' т)>+ 1п1 (~!г1+<У'* г — У>)) = у ~ уев учу взцр((<у', г1> — вар<у', у>) — зир(< — у', г> — ))г1)~ =* Ф 1~ уев / ее у = зцр (<у, 1> — вВ (у') — 1У'( — у')) уФ где У(г)=1г~), а У'(г) =О при 1г'~ '1 и +со при ~(г'(! > 1. (Предложение 3 п. 2.6.3.) Отсюда следует (4).
° В дальнейшем понадобится следующее обобщенйе следствия 2 и, 2.6.4. 276 Лемма о сопряженном конусе. Пусть Х и У вЂ” банаховы пространства, Л: Х вЂ” У вЂ” линейный сюрвективный оператор из Х в )', х,', ..., х,'— элемента! сопряженного пространства Х', и пусть К=(х)<х;, х>~О, !'=1, ..., з, Ля=01 — конус в Х. Тогда всякий элемент х," из сопряженного конуса К =(х" (<х', х>~вО, х~К) допускает представление в виде — 4 = ~ Лр,"+Л у" !=! для некоторых Л!) 0 и у*а)". Доказательство. А) Обозначим Е= () Кегх,', !=о х = КегЛ/Е, и пусть и: КегЛ- Š— естественная проекция, отображающая х Е Кег Л в класс и (х) ~ Л, его содержащий. Покажем, что п(гп 2 (3+ 1.
Действительно, пусть г„..., г,о,— произвольные элементы из Л, г, = п(х,). Однородная линейная система з+1 уравнений а+! 5+1 ,~ Я<х'„х >Л~ — — (х,"! ~~.'~ ~Затхл )=О, !=0, 1, ..., з, !=о р=о с (в+2) неизвестным имеет ненулевое решение Л„..., Л,+!.
Тогда !+1 х=,~ЯХ~х~ЕКегх,, ! сО, ..., в,=ох~Е=ФО=п(х) о !=о о+! $л! = Х Л/п(хл) =Х Луг!. !=о !=о Следовательно, любые в+2 элементов из Я линейно за! и й=й(юг~в+1. Б) Выбрав в 2 некоторый базис Г„..., Г', установим стандартный 'изоморфизм между Я и Йл н между ,Е' и 11в' =,Х, ио-к„"., ~,), л <го г> „ь,"о' <ге !=! =ог' (~! ~л) =(<г' !о!» ° <г * !ол>). Ж7 Далее, определим функционалы гс" ЕЯ', с=О, 1, ..., з, равенствами <гс, п(х)> = <х,", х> и рассмотрим в Я' выпуклый конус К=соне(г,', ..., г,') = г'~ ~~'.с Хсг,*, Хс)~0 ~Г=1 Поскольку Я' конечиомерно, а конус К конечно порожден, то по лемме нз п.
3.3.3 он и замкнут. Предположим, что — г,'(К. Тогда по второй теореме отделимости (и. 2,!А) существует линейный функционал 1~(Я')', строго разделяющий ( — г;) и К: <1, — г,'> ) зцр (<1, г'> ~ г' ~ К)=зцр ~ Хс <1, г;> ()сс)0 . с,с=! Но тогда обязательно <1, гс>(0 (иначе зцр=+ оо), 0 = зцр (<1, г'> ~ г' Е К) и <1, го > < О. Теперь заметим, что 1, как и всякий линейный функционал на конечномерном пространстве г,', задается линейной формой и <1, г*>= ~~Р ~асс= ~ а;<г',1с>=(г', ~ ас1с~=<г', а>. с=! с ! с=! 4 Выбрав в классе а= ~~~~ ~асс!ЕЛ= КегЛ/С представителя с=! х,ЕКегЛ, а=а(х,) имеем, с одной стороны, <хс, х,>=<г,', п(х,)>=<г;, а>=<1, гс>(0 и, следовательно, х, ЕКегЛ() () (х(<х,', х>(0)=К.
с=! С другой стороны, <х,', х,>=<г'„п(х,)>=<г,', а>= <1, г,> с. 0 и, следовательно, х',(К' вопреки условию леммы. Таким образом, предположение — г,'(К приводит 5 к противоречию, и потому — г,'= ~~р ~Хсгс' для некоторых с 278 В) Для любого хЕ КегЛ (х',+ ~ Х;х,", х)=(г,"+ ~ Х;г,', п(х))=0. если Б);ЕО, у*6)". х'= Х д;х~+Л'у, с=~ Поэтому х",+ Х ачх',Е(КегЛ)1., и по лемме об ядре рес гулярного оператора (п.
2.1.7) х,"+,3 дгх~ — — Л'( — у") к=1 для некоторого у' Е 1". ° Лемма Хоффмана. Пусть выполнены те же условия, что и в лемме о сопряженном конусе. Топ)а для функции расапояния от точки х до К справедливо неравенство р(х, К) ч С ~в~~ (хч", х>~+1Лх1, (5) еде <х,", х>+ равно <х;, х>, если <х;. х>»0, и нулю в ос- тальных случаях, а константа С не зависит от х.
Доказательство. Множество К, являющееся пересечением конечного числа полупространств н под- пространства,— выпуклый конус в Х. Вычислим его опорную функцию вК. Пусть х'ЕХ'. Возможно одно из двуж либо найдется такой элемент х, б К, что (х', х,> ) О, либо <х', х>(О, УхЕК.
В первом случае вК(х')» »1(х*, х> У1~ Й+ и, значит, вК(х')=-)- оо. Во втором случае ( — 1) х' принадлежит сопряженному конусу конуса К и, значит, по предыдущей лемме х'= ~ч1, 'Х,х,'+Л'у*, Л,»0, у'~У'. Итак, С=1 еК(х') = ° ° + оо в остальных случаях. Применив теперь формулу (4) (теорему двойственно- сти) к нашей задаче, получаем р(х, К)= =зцР(<х",х>~х =ХХ,х,'+Л'у, Л;»0,1х ~1~1). (Е) Подпространство Е= Нп(х,', ..., х,')-~-1ш Л' является суммой замкнутого подпространства 1., =1ш Л* (нбо 279 1ш Л' (КегЛ)~, а аннулятор всегда замкнут) и конечномерного подпространства Е, = (х!", ..., хД.
Поэтому Ь замкнуто в Х (докажите)) и, следовательно, банахово. Оператор Ле! й'х)" — Е, Л;(Л, у)='~,'Л!х,'+Л'у' ли!=! неен, непрерывен и отображает 11';<У' на баиахово пространство Е. По лемме о правом обратном отображении (и. 2.1.5) существует отображение М,: Е- й'х У' такое, что ЛеоМ!=7м !!М,х'1(С!!х'!!. Тогда, если !!х'!!а 1, то !!М!х')!» кг = ~ ! Л! !+)!у'!! (С. Таким образом, в вы!=! ражении (6) можно считать, что О -Л,(С, !!у'!!~С, откуда и получаем Б(х)=р(х, К)( ь < Р((вх<~-Аи, ))о<к,.<с. !д !<е)< (С Х <хо х>++!!Лх!! .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
