В.М. Алексеев, В.М. Тихомиров, С.В. Фомин - Оптимальное управление (1979) (1155777), страница 44
Текст из файла (страница 44)
265 Определение 2. Функцией Лагранжа пары семейств д(а, р) и а»(х') нлн расишренной функцией Лагранжа задачн(а) называется функцня.У: Х>(11 ')<г»- К, определяемая соотношеннямн а 1, (х) + Х 1( й (х) — а,) + < Ч', Лх — ()>, .У (х; )(, Ч') = х Е А, ~ Е К»', — оо, х Е А, )( ( К7», -1- оо, х(А. (3) Прн фиксированных (Х, Ч") эта функция выпукла по х, а прн фиксированном х выпукла по (Ц Ч') протнвоположная функция †.У. Заметим, что р'(х; )(,-Ч)=,у(х, Ч', Х, 1), ХЕА, ХЕКА', (6) где Я вЂ” функция Лагранжа задачи (а), определенная в и.
3,3.1. Предложение 2, Пара двойственных семейств а (и, Ч) и а»(х') однозначно определяется их функцией Лагранжа, поскольку цх; а, Ч) =( —.У)'"), д(х; )(, Ч') = —.У»(к) (7) где «(1) и «(2) обозначают преобразования Юнга — Фенхеля по аргументам х и (Х, Ч') соответственно. Доказательство. Поопределеннк)'преобразовання Юнга — Фенхеля — й( ', )( Ч') = 1'( ', Д, Ч') =- = зпр (<х, х>+Ьх+<Ч, Ч> — 1(х; Л, Ч)) = (к, а, »а з"р (<х х>+)«х+ <Ч* Ч> — Р» (х)) к«л, лк»ч ь )((к)»а(к а; зпр~ <х', х> — 1, (х) —,)р Х( (1) (х) — а)) — <Ч', Лх — Ь> к»л( с=) = 7,Е~«,» +со,)» К ' =.2"(к)(х', 1(, Ч'), чем доказано второе нз равенств (7). Попутно мы полу- 266 чили полезное соотношение 1п1(,.У(х; Л, Ч') — <х', х>), ЛЕ 11+', й(х;Л,Ч)= " (8) — о, Л(11 С другой стороны'), ( — У)'"' = зпр Р +<Ч', Ч>+У(х; Л, Ч')) Й пп + оо, х(А, з"Р (Лтх+ <Ч' Ч>+т'е (х) + — ( ьво,п' + ХЛ;Дт(х) — а;)+<Ч',Лх — Ь>) т т +оо, если х ( А или Лх — (т чь — Ч или )т (х) — а; ) — се для некоторого т', ), (х) в остальных случаях =Г(х; а, т)).
° Следствие 2. Сопряженная фпнкция к Б-трункцми задачи й(а, Ч) имеет вид ( — (п1 .У (х, Ч', Л, 1), Л Е 11+*, ~'(Л* Ч')= — а(0; Л, Ч')=~ + со, Л( К~м'. (9) Доказательство. По определению о'(Л, Ч")=вар (Ьх+<Ч*, Ч> — 1п11(х; сс, Ч)) = иь ч> зпр (Лсс+<Ч', т)> — ) (х; сс, т))) = — д(0; Л, т)'), иь ч.
ю после чего (9) следует из (6) и (8). Таким образом, двойственная к задаче 6 =8(0, О) задача й' = й" (О) может быть сформулирована также и так: — Яе(Л, Ч')=(п(.У(х, Че, Л, 1) — зир; ЛЕ Й"' Ч'Е'т". ( О) 3 а м е ч а н и е. Определение двойственной задачи зависит, вообще говоря, от того, в какое семейство т) Как и в и. 2,6.3, вычисляя сопряженную к функции, определеняой на сопряженном пространстве (в нашем случае на имаму ), мы считаем результат функцией на исходном пространстве, а не на втором сопряженном, 267 возмущений мы включим исходную задачу (6). Равенства (6) и (6), определяющие расширенную функцию Лагранжа и равенства (7), показывают тем не менее, что семейства ((й (сс, т)))) и ((й» (х»))) в некотором смысле естественно соответствуют задаче (д) и, таким образом, задача (й»), эквивалентная (10), в том же смысле является ее естественной двойственной, Упражнение.
Покажите, что если функпин П и множество А выпуклы и замкнуты и если /»(х) не обращается в — се нз множестве допустимыд х задачи (3), то двойственное (с учетом сноски кдоказательству предзоження «) к семейству (($»(х»))) семейство совпадает с ((3 (а, Ч))), и, таким образом, задачи ($) и (й») образуют пару двойственных Друг другу задач. Теорема двойственности для задач выпуклого программирования. Предположим, что Я-Функция семейства ((й(гх, т)))) непрерывное точке (О, 0).
Тогда: для любых (а, т)) Е !п1(бош 3) Я(сс, т))= зпр (Лсс+<т)', т)>+!п1Я(х, т)»,Л,!)). (11). хз- з, ч»ау' «ел Значения задачи (й) и двойственной ей задачи (й') равны между собой )пЕ 7з(х)=8(0, 0)=Х(0)= «ел л =ь О г«) < ас т= ), „„„ = зцр 'п( 1»(х) + ~Л, (~, (х) а,) (.<т)» Лх, ь> Ох) (12) Д ок а ватель ство. По следствию 1 функция 3 выпукла, а из непрерывности ее в одной точке вытекает (предложение 3 и. 2.6.2) непрерывность и равенство 3(а, т))=(сопело) (сс, т)) для всех (а, х))6!п1(осппо), По теореме Фенхеля — Моро (и. 2.6.3) и следствию 2 3(са, т)) =3'*(сс, т)) = зцр (Л)х+<т)', т)> — 3'(Л, т)')) = )а ч') = зцр (Лсс+<т)', т)>+ )п1 Я(х, т)', Л, 1)), азе хел Ч»е У» чем доказано (11).
Подставляя сс *О, т) О, получаем (12). ° 666 С л е д с т в и е 3 (т е о р е м а о и и н и м а к с е). В условиях теоремы двойственности справедливо соотношение зпр Ы Я(х, т1', Х, 1)= 1п1 зпр Я(х, т1', й,1). (13) амо ел ел ело ч ег" а~е Г~ Доказательство. Левая часть (13) равна Х(0) и в силу (!2) совпадает с Я(0, 0). Что же касается правой части, то !п1 зпр 2'(х, т)', й, 1)= 1пЕ зпр .У(х; Х, т(')= хел хм с ел аччч ° гч = !п! (( —,У)™(х; О, О)) = 1П1 У(х; О, О) сел сел согласно (7) и также совпадает с 5(0, 0).
3.3.3, Линейное программирование: теорема существования и теорема двойственности. Пусть Х вЂ” линейное пространство, Х' — алгебраически сопряженное с ним (т. е. совокупность всех линейных функционалов на Х), К вЂ” некоторый полнэдральный конус (т. е. пересечение конечного числа полупростраиств Н, =(<х~, х> (О, х,' ~ Х', 1=1, ..., з) — иногда, впрочем, от условия йолиэдральности отказываются).
Экстремальные задачи вида <хе, х> — !п1; гт(х) = <х,', х>~Ьт, ! =1, ..., т, х~К, (1) составляют отдельный класс задач линейного программирования. В этом пункте будет рассмотрен нонечномерный случай, когда Х=)тч Х'=йче К=1!+. В этом случаезадачу (1) можно переписать так'): сх'- (п1; Ах'-" Ь, х О, (2) где с Е 1!"*, А =(ап), 1 = 1, ..., и, ! = 1, ..., т,— матрица, задающая линейный оператор из 1!" в мт, Ь~ к'". Символ ге~г для конечиомерных векторов г' и г означает, что все координаты вектора не превосходят соответствующих, координат вектора г'. Задачу (2) назовем конечномерной задачей линейного программирования. Эта т) Напомннм, что дхя конечномернмк пространств мм нмеем дав обоаначенна: л <с, х> = ох = ~ с,хо с Е и"', х Ч й", т-т задача — частный случай общей задачи выпуклого программирования.
Однако в ней имеется еще более специальная структура: все функции здесь линейны и конус поливдрален. Как н обычно, условимся, что если задача (2) несовместна, т. е. не имеет допустимых злементов, то ее значение считается равным +оо. Теорема существования. Если множество допустимых значений конечномерной задачи линейного программирования (2) испусти и ее значение конечно, то задача имеет решение. Доказательство теоремы 1 опирается на один простой факт конечномерной геометрии. Напомннм, что коническая оболочка сопе С некоторого множества С~Х определяется равенством 9 сапе С = х Е Х х = Х Л х„Л! =! О, х, Е С ! и является выпуклым множеством (н. 2.6.1). Мы будем говорить, что конус соне С порожден множеством С. А) Лемма о замкнутости конечнопорожденного конуса в конечномерном пространстве.
Всякий конус в конечномерном пространстве, по рожденный конечном множеством точек, замкнут. Д о к а з а т е л ь с т в о. Пусть К = соне С!= 11'ч, С = = (г„..., гл), г, Е Й'~ Доказательство проведем по индукции. 1) А=1. Тогда К=сопе(г,) =(х(х=Л!г„Л!)О)— полупрлмая, т. е. замкнутое множество. 2) Допустим теперь, что лемма верна для й =з — 1. Докажем ее для й= з. Возможны два случая: а) конус К содержит векторы — г„..., — г,. Тогда К есть подпространство конечномерного пространства н, следовательно, замкнутое подмножество; б) хотя бы один нз векторов ( — г,), ! = 1, ..., з, например ( — г,) не прннадяежнт конусу К.
Обозначим через К, = сопе (г„..., г, !). По индуктивному предположенню конус К, замкнут. Пусть вектор г принадлежит замыканию конуса К, т. е. г = 1(щ $„; $„ЕК, и) 1. По опрео делению $„б К = сапе (г„..., г,) ФФ Ч„= ~~'~ Л,„г, = Ь„-1- Л,„г„ !=! где ь„чК, н Л,„~ )О. кто Если допустить, что ˄— оо при и — оо, то — г,=1пп "~ "— — 1пп — '" ЕКг Л Ф Ф .ЮИ П ~Ф Ю6 (напомним, что $,— г, и потому $„(Л,„— О, а ~„~Л,„ЕК, вместе с ь„), т.
е. — г,ЕК, вследствйе.замкнутости К„ что противоречит допущению. Значит, Л,„не стремится к бесконечности и можно выбрать подпоследовательность Л,„, сходящуюся к некоторому числу Л, ) О. В этом случае 1 Ф=$.» — Л»аг -г — Л"г =-г В силу замкнутости К, вектор гЕК, и, следовательно, г=г+Л.г.ЕК И Б) Докажем теперь теорему существования. Рассмотрим в пространстве 11"+' множество К, образованное такими векторами (и, г), и Е )с, г Е )с'", для каждога из которых найдется хотя бы один вектор хЕ 11"„. такой, что сха а, Ах) г.
Множество К вЂ” это конус, ибо если (а, г) Е К, то для некоторого хЕ й~, сх -а, Ах) г. Но тогда для любого 1)0, 1хЕ)с"„с(1х)<(а, А(1х)>(г, т. е. 1(а, г)ЕК. Покажем, что конус К порожден конечным множеством векторов в 11 +'. =(с„асо ..., а„,), ~,=(с„а„, ..., а,), ..., ~„= =-(с„, а»а ..., а „), ь„+, = (1, О, ..., 0), »„+,=(О, — 1, О..., 0), . = (О, ..., О, — 1). Прежде всего ~;ЕК, так что сапе Д„..., ~„„„1) ~ К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
