Алексеев В.М., Тихомиров В.М., Фомин С.В. - Оптимальное управление (1050536), страница 43
Текст из файла (страница 43)
что х — допустимый элемент в задаче), н, в-третьих, что ~е(х) < 1,(х) вопреки условию. ° Теорема (субдифференциальная форма теоремы Куна — Таккера). Лусть в (б) функции' ~о 1=0, 1, ..., т, непрерывны в точке хЕ А О В, доставляюи)ей абсолютный минимум в задаче. Тогда найдутся числа Х;)О такие, что ~Х;=1, ХД~(х)=О, 1)1, и с=о элемент х'Едб (А П В) (х), для которых ° О б ~,' Х; д~с (х) +х'. ' (1) Доказательс-тво.
Согласно предложению х доставляет абсолютный минимум в элементарной задаче (б'). По теореме 1 п. 3.1.1 О Е д~ (х). Функция у(х) = =гпахД,(х) — ~,(х), ~,(х) — а„.. „1„(х) — а„) выпукла и непрерывна в точке хЕА П В (т. е. принадлежащей дою 6(А (1 В) и, значит, по теореме Моро — Рокафеллара (и. 2.6.4) дг(х) = дд'(х)+дб(А() В)(х).
Наконец, по теореме Дубовицкого — Милютина (п. 2.6 4) дд(х) = = сопч(дгц (х) 0... 0д7с,(х)), где Е~ — те н только те индексы, для которых 7с (х) = д(х). Таким образом, существуют два элемента $'Еду(х) и х=Едб(А П В)(х), для которых $'+х'= О, $'Есопч(д~ч(х) 0... 0д5,(х)) ча 5* = Я 5 = Х Х; х,", х),. Е дРс, (х), Х ~с, = 1, ) ) О. Осталось положить Х, = О, Е( (Е„..., 1,). Я 262 Упражнение. Пусть В=(х(Лх=ь). Докажите, что если хеЕВ, то дд(В) (хе)=(КегЛ)х. Следствие 1 (прннцип Лагранжа для задач и выпуклого программирования,с ог р аничениями типа равенств и неравенств).
Пусть в условиях теоремы А = Х и образ Х при отображении Л замкнут в !'. Тогда найдутся такие множители Лагранжа ).оба, або ", у'Е!", что )ьг~)0, !)О, ХД(х)=0, 1:!, ш(п.У(х, у*, )., Хо) =,Я'(х, у, Х, Х,). (2) к Действительно, если 1шЛ есть собственное подпространство в 1', то можно положить г.г = ае = О, у' Е (!ш Л)~-. Если жеЛ вЂ” сюръектнвный оператор„то дбВ (х) =(КегЛ)х= =1шЛ'.
Тогда, согласно (1), ОЕд„.2'(х, у*, г., )о)= = ~~р ~);д(г(х)+1шЛ', и, значит, по определению субг=о дифференциала -~ (х> у ~ )ь, )ье) 2'(», у', а, Ло) — (О х — х))Оеа еа.зг(х у', Х. )ь,)~).2'(х, у*, )., Х,), Ух. ° 3.3.2. Метод возмущений и теорема двойственности, В предыдущем пункте задачу выпуклого програьанирования (Ь) мы рассматривали как одну индивидуальную задачу.
Со многих точек зрения оказывается естественным и плодотворным рассмотрение целых семейств задач подобного рода. Фиксирован (г, Л, ао А и Ь, включим задачу (а) в семейство ),(х) — (п1; )г(х)+а; (аг, 1= 1, ...„т, Лх+т)=Ь, хЕА. (6(а, т))). (Разумеется, можно было бы просто объявить аг и Ь переменными параметрами семейства, но, введя параметры а;, т) так, как указано выше, мы получаем более красйвые формулы.) Совокупность задач ((6(а, т())) назовем возмуи(гнием задачи (1) =-(Ь(0, 0)).
Мы уже видели в п. 3.3.1, что задача (6) сводится к элементарной. Сейчас мы проделаем то же самое для семейства 3 (се, т)), однако несколько цо-другому. А именно, аев обозначим ( г, (х), если г; (х)+а, (а„Лх+!)=Ь, х ч А, г(х; а, г!) = +ос, в остальных случаях. (1) Тогда семейство (5(а, т))) можно записать в виде элементарной задачи 1(х; а, Ч)- !п( (по х~Х). (2) В дальнейшем, говоря о задаче (в(а, и)), мы не будем различать ее исходную формулировку от (2).
Значение этой задацн, т. е. 1п1~„, прн указанных ограничениях является функцией от а= (сс„..., се„) и и, которую мы обозначим через 3, Я: К хУ' К и иногда будем называть $-функцией: 3 (а, и) = !и! Г'(х; ы, Ч) = !и! 1~(х). (3) х хел, Г,.
оо +а~ к ае лх+ч=ь Лемма. Лусть Р(х, г) — выпуклая функция на произведении линейных пространств Х и Е. Тогда функция 5 (г) = 1п1 Р (х, г) х выпукла на х. Доказательство. Пусть (г;, Г)Еер!5, 1=1, 2 и Лб<О, 11. Тогда Я(г,)(1„1=1, 2, и для любого е >О существуют (х„г,) такие, что Р(х;„г,) < г';+е,( ° 1, 2. Отсюда в силу выпуклости Р Р (Лх, + (1 — Л) х„Лг, + (1 — Л) г,) ( а~ЛР (хо г,) 1-(! — Л) Р(х„г,) ( Л(С,+з)+(! — Л)(Г,-!-в) = Л Г, + (1 — Л) Г, + а. Ввиду произвольности е > О Р (Лхг+ (1 — Л) х„Лг;+(1 — Л) г,) ( ( Л Гг+ (1 — Л) Г~ ~ Я (Лг, + (1 — Л) г,) ( (ЛГ,-(-(1 — Л) 1,=О(Лг,+(! — Л) гы Л(,+(1 — Л) 1,) Е ЕР! Я. ф Предложение 1.
Пусть Х и У вЂ” линейные пространства, А т Х вЂ” выпуклое множество, Л: Х вЂ” У вЂ” линейное отобраскение. Если функции 1,; Х вЂ” Ф, 1= О, 1, ..., т, выпуклы, то функция 1(х; а, 1!), определяемая равенством (1), выпукла на Хх К"'х У. дав Доказательство. Множества М, = — ((х, а, т), 1) )(х, 1) ~ер1 Ц, М; = ((х, а, т), 1) 11< (х) + ат . а, ), МА — — ((х, а, т<, 1)) х~А), Ма = ((х, а, т<, 1) ! Лх+ т1 = Ц выпуклы в Х х й" х 'г" х 11. Действительно (нарушая иногда для удобства порядок сомножителей): М, = ер1 (,х Й" х)", МА — — А Х К Х 1'Х й, Ма=Л '(Ь) Х К"'х й, где Л: (х, у) + т-т Лх+у — линейное отображение нз Хху в г' н М< —— =аер111< — а<)ХЙ"-'ХУХЙ, где о: (х, 1) э(х, — Г) симметрия в Ххй.
Отсюда видно, что все зтн множества выпуклы, н остается заметнть, что ер11= П М<ПМАПМл ° <та Следствие 1. Б4унк«ия задачи (й(сс, т))) выпукла на К Хт. В й 2.6 мы уже видели, что выпуклость позволяет сопоставлять различным объектам (функцням, множествам) двойственные объекты в сопряженном пространстве. То же самое справедливо н для задач выпуклого программирования. Далее мы будем предполагать, что Х н У' — локально выпуклые пространства, Х' н 'г' — нх сопряженные, Х=(Х,... к )б й ' Определение 1.
Семейство экстремальных задач у(хе;Х, т)') — зцр(по)<ЕЙ ",т)'ЕУ'). (й'(х')) где ( — 1) д(х', к, т1') =1'(х', к. т)')- преобразование Юнга — Фенхеля (и. 2.6.3) функции (х, а, т1) т-+1(х, а, т<), определяемой равенством (1), называется двойственным к семейству й(а, т))еэ(2). Задача й' = з'(О) называется дво<тсптвекной к задаче 6 =а(0, О) (относительно семейства возмущений й(а, т))). Значение задачи й'(х') обозначим Х(х') = зцр у(х', )т, т)').
<л, ч ) Поскольку функция ~' выпукла, противоположная ей функция у вогнута. Двойственные задачи можно было бы называть задачами вогнутого программирования, но мы предпочитаем обойтись без нового термина. 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 (а, Ч))), и, таким образом, задачи ($) и (й») образуют пару двойственных Друг другу задач. Теорема двойственности для задач выпуклого программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
