В.М. Алексеев, В.М. Тихомиров, С.В. Фомин - Оптимальное управление (1979) (1155777), страница 45
Текст из файла (страница 45)
Действительно, если ! ~ (а, надо взять в качестве х стандартный базисный вектор е,; для остальных 1 надо взять х =О. Пусть теперь вектор ~ =(а, г) = (сс, г„..., г ) Е К. Тогда для некоторого хЕ В'*, х=-(х„..., х„) такого, что х,~ О, ..., х„- 0 П некоторых ~,) О, $:» О, выполняются соотношения ~~'., сх +Ц,=я, ~ аоху — руэгг„(=1, ..., т. ~=! 1=! 271 Но зто как раз и означает, что В т Ь=(а, з)= ~ хД+~Д +с+ Х ()Д +с+с с=! с=с ху > О, р, ~) О, рс > О, Ь Есопе(~„..
„~„~Д. По лемме нз предыдущего пункта конус К замкнут. По условию теоремы задача (2) имеет допустимый эле- мент х и значение задачи а > — оо. Из определения К следует, что точка (сх, Ь), где сз=сх, принадлежит К, При зтом, очевидно, что и)й. Следовательно, множество ес=<аЕК<(а, Ь)ЕК) непусто и а=(п((сх<мб9Ц, т. е. (сс, Ь) принадлежит замыканию конуса К, а значит, и самому К.
Следовательно, существует злемент х) О, для которого Ах)Ь и сх(сх, т. е. х — решение задачи. ° Переходим к рассмотрению двойственной задачи. Теорема двойственности приобретает здесь более закон- ченный вид, чем в предыдущем пункте, поскольку ввиду специальной структуры 5-функция задачи оказывается замкнутой. В соответствии с формулами (5) и (б) п. 3.3.2 рас- ширенная функция Лагранжа имеет вид .У(х; Х) = сх+Х(Ь вЂ” Ах), хай+, А~К",; хай+", Кй+', + со, х( и". Отсюда мы находим семейство возмущений задачи (2) и двойственное семейство. Согласно (7) п.
3.3.2 7 (х; а) = ( †.2')* "' = зир (Хсс+ Я (х, Х)) = ( +, х(й"„ =~ зпр(Хсх+сх+Х(Ь вЂ” Ах), х~й", хьь сх, х) О, Ах~~Ь+сх, + со в остальных случаях. Обозначая г = Ь +сх, получаем возмущение задачи (2) сх спс, х О, Ах ) г. (3) Аналогично для определения двойственной задачи мы 272 должны вычислить й(0, Л) =( — Янь) (О, Л) = — зпр ( — Я(х, Л)) ° кЬΠ— зпр( — сх — Л(Ь вЂ” Ах)), й.:ав О, Э~ Л ( )(ще ЛЬ, Л~ ~О, ЬА ~;с, — оо в остальных случаях. Это дает задачу ЛЬ зцр; ЛА ~с, Х;:г О, (4) двойственную задаче (2). Она имеет такое же строение, как задача (2), и легко понять, что если, отправляясь от задачи (4), построить двойственную задачу по тому же правилу, по которому из задачи (2) получилась задача (4), то мы вернемся к задаче (2). Поэтому имеет смысл говорить о паре двойспменных задач линейного программирования.
Теорема двойственности. Для пары дэойст. венных задач линейного программирования справедлива следующая альтернатива: либо значения задач конечны и равны и в обеих задачах существует решение, либо в одной из задач множесп|во допустимых элеменпюв пуспю. В первом случае хЕ)4" и ХЕ и"', в том и только в том случае, будут решениями задач (2) и (4) соопиитственно, когда они допустимы в этих задачах и удовлетворяют одному из двух соотношений сх=ЛЬ, (5) Л(Ах-Ь) =(ЛА — с) х. (6) Во втором случае одна из задач несовместна, а друэав либо несовместна (т. е.
ее мнозееапво допустимых элементов пусто), либо имеет бесконечное значение, Доказательство. А) Построение Ю-функ. ц и и. Снова рассмотрим тот же конус К, что и в теореме существования. Если (а, г) е,К н ф~га, то (д, г)аК, а потому К является иэдграфиком функции 8(г) = 1п((а!(а, г) ЕК). (7) Из доказательства теоремы существования еледует, что 1п( достигается и 8(г) есть значение задачи (3) и, следовательно, формула (7) оиределяет 8-функцию задачи (2). 273 Поскольку К вЂ” выпуклый и замкнутый конус, 8-функция задачи (2) замкнута и выпукла. В) Вычислим функцию 8', сопряженнук7 с функцией 8, По определению, 8«(Л) = = зпр (Лг — 8(г)) = зпр(Лг — 1п1 (сх1х Е К"„Ах ~ гЦ = « « « =зпр (Лг — сх1хб 11"„г Е 11, г ~(Ах).
(«, «) Очевидно, что зцр(Лг~гЕ К", г(Ах) =ЛАх( ао в том и только в том случае, когда Л»0. Таким образом, ( зцр(ЛА — с) х, если Л6 К'«', 8«(Л) «ь з + сои если Л(1 К," О, если ЛА ~с, Л» О, +со в остальных случаях. Поэтом)~ 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 Лемма о сопряженном конусе. Пусть Х и У вЂ” банаховы пространства, Л: Х вЂ” У вЂ” линейный сюрвективный оператор из Х в У, х,', ..., х,"— элементы сопряженного пространства Х', и пусть К=(х)<х;, х>~0, !'=1, ..., в, Ах=01 — конус в Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
