Ф.П. Васильев - Методы оптимизации (1125241), страница 69
Текст из файла (страница 69)
Рассмотрим задачу из примера 4. Здесь Ь(и, Л) = — ъ?ху+ + Лх, и Е Хо = Е'„Л е Л = Е'. Функция ф(Л) = — со при всех Л е Лы так что в двойственной задаче (30) множество Л = Я. ПРимеР 9. Задача: Х(х)=е * — «!и1, хЕХ=(хЕЕ«, д(х)=хе *=0) Мне«кество Х состоит из единственной точки х = О, так что Х, = Х(0) = 1, Х„= (О). Здесь функция Лагранжа Ь (х, Л) = е *+ Л хе *, х е Х = Е ', Л е Е Ло = Е'; «р(Л) = — оо при Л > О, ть(Л) =0 при Л =О, «р(Л) = Л ехр( — 1+ л ) при Л < О. Множество Л = (Л < О) замкнуто, функция ф(Л) непрерывна на Л, ф' =О, Л' = (0).
Таким образом, здесь Х„ф О, Л ф О, но ф* < Х,. Согласно теореме 5 функция Ь(х, Л) не имеет седловой точки. Не следует думать, что если (х, Л') е Хо х Ло — седловая точка функции Ь(х, Л), то и точки (а, Ь) е Хо х Ао, для которых Ь(а, 6) = Х (х„, Л*), также будут седловыми точками. В общем случае можно лишь утверждать, что Х„! — Х(Л*) = (х е Хо! Ь (х, Л*) = Ь(х„, Л )), Л* ~ Л(х,) =(Л ЕЛо! Х (х„, Л) = Ь(х„Л")) (35) где множества Х„Л* взяты из (27), (31). П р и м е р 10. Функция Ь(х, Л) = Лх, х е Хо = Е', Л е Ло = Е', имеет единственную седловую точку (х„= О, Л* = 0), Х (О, 0) = О, Здесь Х(Л*) = = Е', Л(х,) = Е', и, как видим, включения (35) являются строгими. Далее, функции и(х), «р(Л) из (25), (28) соответственно равны и(х) =+ос при х фО, и(0) = О, и ч>(Л) = — оо при Л ф О, у«(0) = О, так что оба множества Х = Х, = (0), Л = Л' = (О) являются одноточечными, 6.
Напоминаем, что в главе 3 мы уже рассматривали двойственную задачу для задачи линейного программирования, причем двойственная задача была введена по определению, без объяснения, откуда она появилась. Убедимся, что введенная в $ 3.5 двойственная задача является частным случаем задачи (30). Рассмотрим общую задачу линейного программирования; Х(х) = (с„х,) + (с, х ) !и1, х Е Х, (36) Х = (х = (х! «х>) е .Е ' х Ь'": х, > О, А ! ! х! + А от хо — Ь! < О, Аз! х! + Амоо — Ьз — — О), (3?) где с, Е Е", с, Е Е", Ь, Е Е"", Ь, е Е ' — заданные векторы, матрицы Ае также заданы и име!от размерность гп! х пз 4, у' = 1, 2.
Функция Лагранжа этой задачи: (х«) (с! «х!) + (сз«х>) + (Л«, А,«х, + Амх — Ь ) -1- +(ЛхАмх«+Аззх> — Ь)=(с,х)+(с х)» «П« + Х, 'Л,(Анх, + А„, — Ь,)'+ 5~ Л,'(Ахх, + А„, Ь,)! «=! «=! = (хн х>) Е Хо =Е~> х Е , Л = (Л!« Лз) Е Ло =Е х Ь' Отсюда нетрудно видеть, что функция и(х) = зпр Ь(х, Л), х е Хо, опредеЛох, ляемая согласно (25), в случае задачи (36), (37) имеет вид: < с„х! > + < сз, хз > при х е Х, +со пРи х Е Хо '1 Х. 4 Э. ТЕОЕЕМА КУНА — ТАККИ А.
ДВОйетВЕННАЯ ЗАДАЧА 231 230 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Для вычисления функции гЬ(Л), определяемой по формуле (28), удобнее представить функцию Лагранжа 5 (х, Л) в следующем виде Ь(х, Л)=( — Ь„Л,)+( — Ьг Лг)+(х!,А!!Л!+Аг!Лг+с!)+(хг,А!гЛ!+Аг~гЛг+сг) = (Ь! Л ) (Ьг Лг) + 2" х,'(Ат Л, + Ат!Лг+ с,)'+ + ~ , 'х,'(А"„Л, + Аг~гЛг + сг)! ! х Е Хю Л Е Лх Отсюда следует, что (' — < Ь„Л, > — < Ь„Л, > при Л е Л, где Л = (Л = (Л, Л ) Е Е' "~ х л!"'. Л, > О, А т Л, + Агт! Л, + с, > О, А т Л, + + А,",Лг+ сг = О). Йз полученных выражений (38), (39) для функций и(х), ф(Л) следует, что задача (26): и(х) — ! !п(, х Е Х, равносильна исходной задаче (36), (37), а двойственная к ней задача (29): ф(Л) — зпр, Л е Л„ или (30) равносильна задаче 4(Л) = †(Ь„ Л,) — (Ь„ Л,) - зпр (или ( †!г(Л)) - ш1), Л Е Л.
(40) Как видим, именно задача (40) в $3.5 была по определению названа двой- ственной к (36), (37) задачей. Сравнивая утверждения, доказанные в этом параграфе, с теоремами из 9 3.5,можем сделать вывод, что развитые здесь элементы теории двойственности явля!отся прямым обобщением теории, из- ложенной в э 3.5, на случай нелинейных задач. Можно также заметить, что не все утверждения, справедливые для задач линейного программирования, допускают обобщения на нелинейные выпуклые задачи. Так, например, не- льзя утверждать, что задача, двойственная к двойственной задаче (29), в нелинейных задачах также может быть приведена к виду, совпадающему с исходной задачей (1), (2).
Для невыпуклых задач это очевидно, так как двойственная задача всегда равносильна задаче выпуклого программирова- ния (32), и потому задача двойственная к двойственной, могла бы совпасть с исходной лишь тогда, если бы она была выпуклой. Однако требование выпуклости задачи здесь также не спасает положение, что видно из при- меров 6, 7, в которых двойственные задачи совпадают, а двойственная к последней не может совпасть с исходной задачей, так как исходные задачи в этих примерах разные, Ничего не меняет здесь и требование существова- ния седловой точки функции Лагранжа, о чем свидетельствует следующий пример.
Пример 11. Задача: 7(х)=)х)г- !и1, хеХ=(хеЛ": д(х)=(х!г— — 1 < 0). Здесь Х,=Л", 7; =О, х, =О, Л,= ~А ЕЕ: Л >О). Функция Ла- гранжа 7 (х, Л ) = )х!~+ Л ()х!' — 1) = (1+ Л ) ~х( — Л, х Е Хю Л Е Лю Ясно, что г!!(Л) = !п1 5(х, Л) = — Л при всех Л Е Лх Таким образом, двойственная мчв" задача имеет вид гЬ(Л) = — Л вЂ” зцр, Л е Л =Л,. Эта задача линейного про- граммирования, Двойственная к ней задача также будет задачей линейного программирования и не может совпасть с исходной. Остается заметить, рас- сматриваемая задача выпукла, и функция Лагранжа в ней имеет седловую точку (х, = О, Л* = 0). Заметим, что теорема 3.5.2 об одновременной разрешимости исходной и двойственной задач также специфична для задач линейного программиро- вания и не может быть обобщена на нелинейные задачи даже при условии их выпуклости — см.
примеры б — 8, 7. Кратко остановимся еще на одном интересном классе задач, называемых задачами геометрического программирования, в которых переход к двойственной задаче весьма плодотворен. Речь идет о задачах минимизации следующего вида: (40) д(х) = 2; с,.х,"'... х„" — !!и1; х Е Х =!и! Е", !=! где с! >О, а! — заданные числа, !и! Л'=(х=(х„.. Функция д(х) из (40) называется позиномом. Для исследования задачи (40) удобнее перейти к =(и„..., и„„) по формулам ., х,): х, > О,..., х„>0). новым переменным и = (41) и переписать ее в эквивалентном виде: гЬ(Л) = !п1 5(и, Л) = (Л! — Л! 1пЛ, — Л!Ь!), Л ЕЕ„", 2 авЛ! =О, у'=1,..., г, ! ! в г=! =! — оо при других Л.
Поэтому двойственная задача (30) здесь будет иметь вид гЬ(Л) = 2;(Л,. — Л! 1и Л, — Л.Ь.) — зпр; Л еЛ, Л=)Л=(Л„...,Л„)ЕЕ,: ',г а„Л,=О, 7'=1,...,г). !=! Если здесь верхняя грань достигается в точке Л" ф О, то задачу (43) можно записать в более простой форме.
А именно, учитывая, что любую точку Л = 7'(и) = 2 е" " — ! !и1; иЕ(7=(иЕБ"!": 2 а„и,— ив! — Ьг=О, г=1,...,и(. г=! Отметим, что функция 7(и) выпукла на Е" +", (7 — многогранное множество, и поэтому к задаче (42) применима теорема 3. Составим функцию Лагранжа (3) для этой задачи: 7 (и, Л)= 2 е""'+ 2„Лг~2 аьиз — и„, — Ь,.) = ~=! гг=! l Г ! Н ~еч' — Л,и,„! — Л,Ь,.)+~ ( 2; аиЛ)ит, и Е Е'+"=Гую Л Е Я"='Лц, =! г=! ! ! С помощью классического метода (9 1.2) нетрудно показать, что нижняя грань функции р(г) = е' — Л!г — Л!Ь! переменной г на числовой'оси равна !р, = Л! — Лг!и Л! — Л,.Ьг, причем при Л! > 0 она достигается в точке г, = = — 1и Л,.; функция Л,.!й Л! при Л, =0 здесь считается доопределенной по непрерывности нулем.
Отсюда, опираясь на линейность функции 5 (и, Л) по переменным и„...,и„ получаем $9. ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 233 232 Гл, 4, ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА = (Л„..., Л„) фО можно представить в виде Л = сги, где сх = 2, Лг, и = г=! = (и„ ...,и„), и! = Л,/гх, и, + ...
+ и„ = 1, задачу (43) перепишем сначала в терминах переменных (сг, и): т]>>(сз, и) = т]>(сги) = 2 ст(и! — иг!и сти! — ь! 5!) = *'=! в = сз [1 — 1и сз + А т, '(и! 1и с, — и! 1п и;)] — зцр; *'= ! (сг> и) ЕА! — — ][(сг! и): сг > О, ! 6 В~, ~ иг=], ~ цпи,=О, у' = 1,..., г) '=! '= ! с!' ... с„"" т>>з(и) = и .„з"Р] и>'... и„" (44) Лз=]и=(и„...,и)ЕЛ,: А из=1, А аииг=О,у=[,...,т),Если и*= г=! г=! =(и,",..., и,*) Е !и! Ж" — решение задачи (44), то, полагая Л* = ах*и*, где с!* = П ( — *, ], и„,, = Л;, з = 1,..., п, из системы линейных алгебраичег=! ских уравнений (41) можно получить ы>„,..., и„„откуда имеем решение х„=(хы сх с",..., х = е"-) исходной задачи (40).
Задача (44) часто бывает проще задачи (40). ]з[ереход к двойственной задаче особенно эффективным оказывается тогда, когда множество А, в задаче (44) состоит из единственной точки и*, которая и будет решением этой задачи. Аналогично может быть исследована и более общая задача геометрического программирования д(х)- !и[; ха Х =(хЕ]п( Л'. д(х)(1,...,д (х) (1]> где до(х),..., д (г) — позиномы. Подробнее о геометрическом программировайии, его пр™иложениях см., например, в ]204; 260; 541], Читателей, желающих подробнее ознакомиться с красивой и богатой результатами теорией двойственности, с различными ее приложениями, отсылаем к [6; 7; 14; 40; 44; 49; 52; 83; 84; 209; 225; 233; 234; 278; 297; 314; 358; 366; 373; 434; 465; 584; 604; 605; 613; 617; 670; 683; 687].
Заметим также, что в последнее время растет интерес к задачам, в которых нарушены соотношения двойственности (34), такие задачи возникают при исследовании объектов, описываемых противоречивыми системами ограничений, и имеют интересные приложения ]297; 298; 644]. Далее, пользуясь классическим методом ($ 1.2), убеждаемся, что точка сг*= П ( — '„] > 0 (здесь принято Оа=1) доставляет функции ф>(ст, и) и' *=! максимальное значение по ст > 0 при фиксированном и е Е", причем ю( ", )=й( —;) Тогда двойственная задача (43) перепишется в следующем виде: Упражнении 1. Сформулировать аналоги теорем Куна — Таккера для задачи максимизации: д(т) -> зар, х е Х, где множество Х определено посредством (2), Указание: рассмотреть задачу; 7(т) = — д(х) >о1, т е Х, и воспользоваться теоремами 2-4, 2.
С помощью теорем Куна — Таккера исследовать задачу: >(т) = 2; ]л! — а; !-> !а1, х е Х, где Х=(теЕ ! ]х]<1) или Х=(хеЕ"! т -1-...+т"=0), или Х=Е~ь! а>,...,а„— заданные числа. 3. Применить теорему Куна — Таккера к задаче квадратичного программирования: 7(х) = =(х') +...+п(х ) — >!и1, хЕХ, где Х=(хЕЬьк! т'+...+х"=1), или Х=(хЕЬв: т'+... + т" < 1), или Х = (т е Е": — 1 < т! +... + х < 1), или Х является пересечением предыдущих множеств с Е". 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
