Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 69
Текст из файла (страница 69)
Пусть выполнены соотношения (34). Возьмем произвольные х„е Х„н Л* еЛ и покажем, что (х„, Л") — седловая точка. Имеем Ча" =ф(Л*) = !п1 Х,(и, Л*) ( Х (х„Л') < вир Х,(х„, Л) = и(х„) =~,. "рха Лала По условию ф* = Х,. Поэтому предыдущие неравенства превращаются в.равенства: Х (х„Л") = !п1 Х (и, Л*) = впр Х (х„Л ) = Х,. "рха лрл, Отсюда имеем неравенства (5), т. е. (х„Л*) — седловая точка. Тем самым показано, что Х х Л* принадлежит множеству седловых точек функции Х (х, Л) на Хр х Лр. Достаточность.
Пусть(х.,Л*)ЕХрхЛр — седловая точка функции Х (х, Л ) на Х х Л,. Согласно (5) это значит, что Х (х„Л ) < Ь (х„Л'), Л ~ Л . Отсюда имеем впр Х (х„Л) = и(х„) = Х (х„Л*). Лала Кроме того, Х (х„Л*) ( Х (х, Л*), х Е Х, так что Х,(х„, Л') = ш1 Х (и, Л*) =ар(Л*), откуда и из неравенств (33) следует Х (х„, Л*) = ар(Л*) < ар* < Х, < и(х ) = Х,(х, Л'), $9.
ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 229 228 Гк 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА т. е. !р(Л*) = !р' = Х, = и(х,). Это значит, что ф* = У„Л' ЕЛ, х, е Х„, Тем самым установлено, что множество седловых точек функции Х,(х, Л) на Хь х Ль принадлежит множеству Х„х Л. Теорема 5 доказана.
С! Следствие 1. Следующие четыре утверждения равносильны: 1) (х„, Л*) е Хь х Ль — сгдловая точка функции Х (х, Л) на Хь х Л„ 2) выполняются соотношения (34); 3) существуют точки х. е Х„Л* е Ль такие, что и(х.) = ф(Л"); 4) справедливо равенство шах ш! Х,(и, Л) = ппп зпр Х (и, Л) ЛбЛо сх0 ехокьЛ (напоминагм, что когда пишут !пах или ппп, то достижение соответствующей верхней или нижней грани предполагается), Следствие 2. Если (х„Л') и (а„Ь*)еХь хЛь — сгдловыг точки функции Х (х, Л) на Х х Ль, то (х„Ь'), (а., Л') также являются св ловймйточками этой !1!ункции на Х х Ль, причем Х(х., Ь*) = Х(а„Л*) = Х (х, Л*) = Х (а„Ь*) =Х. =ф" Отсюда и из теоремы 1 вытекает, что в теоремах 2, 3, 4 можно выбрать одни и те же множители Лагранжа Л* для всех х, Е Х, сразу.
Полезно заметить, что в доказательстве теоремы 5 нигде не использовано то, что Х (х, Л) является функцией Лагранжа какой-либо задачи вида (1, 2), а множества Х, Л выпуклы — там были важны лишь функции (25~, 28), задачи (26), (29) и множества Х„Л из (27), (31), которые могут быть введены для любой функции Х (х, Л~ на любых множествах Х Это значит, что теорема 5 и следствие 1, к ней верны для произвольных функций Х (х, Л) и множеств Х„!!ь. В приводимых ниже примерах иллюстрируются различные свойства двойственной задачи.
Пример 6. Задача: Х(х)= — х-+!п1, хЕХ=(хЕЕ!: х>0, д(х)= = х' < О). Здесь Х, =О, Х, =Х =(О), Задача выпуклая. В примере 1 было замечено, что функция Лагранжа Х (х, Л) = — х+ Лх', х ~ Хь = (х ) Е >О) Л Е А = (Л > О) не имеет седловой точки. Функция ф(Л ) = !п1 Х (х, Л ) = — 4л р Л > 0 и !р(0) = — оо. Двойственная задача (30) имеет вид: !р(Л) =-4 -+зпр, Л ЕА=(Л >0).
Множество А — открытое, ф*=Х*=О, но Л =И, т. е. двойственная задача не имеет решения. Множество Х не имеет внутренних точек. ! Пример 7. В задаче из примера 2 функция !р(Л)= !п( Х (х, Л)= — 4л при Л > О, ф(0) = — со. Как видим, двойственная задача здесь полностью совпадает с такой же задачей из примера б, хотя исходные задачи разные. Здесь |и! Х ~И, !р" = 7*=0, Х, =(0), Л =И. П р и м е р 8, Рассмотрим задачу из примера 4. Здесь Х (и, Л) = —,„lщ+ + Лх, и Е Хь =Е+', Л 6 Ль = Е', Функция !р(Л) = — со при всех Л Ей, так что в двойственной задаче (30) множество Л = И. Х(х) = (с„х,) + (с„х,) !и1, х Е Х, (36) Х = (х = (х!, хт) Е Е"' х ЕГЧ х, > О, А!!х!+А!гхт Ь, гьО, Амх!+А х — Ь =О), (37) где с, е Еч, сз Е Еч, Ь, Е Е ', Ь, Е Е'ь — заданные векторы, матрицы Ав также заданы и имеют размерность гп! х и, !', т' = 1, 2. Функция Лагранжа этой задачи: Х (х, Л) = (с„х ) + (с„х ) + (Л „А их, + А„х, — Ь ) + + (Лю Ам х, + Амхз — Ь!) = (с„х!) + (сз хз) + + );Л!(А!!х!+ Амхз — Ь )! + ~ Лг(Амх, + Амх! — Ьз)!, ! ! ! 1 х = (х„хт) Е Хь = Е,~ х Е', Л = (Л „Лз) е Ль = Е+" х Е" .
Отсюда нетрудно видеть, что функция и(х) = зпр Х (х, Л), х Е Х, опреде- кгЛ, ляемая согласно (25), в случае задачи (36), (37) имеет вид: ( <с„х!>+<с!,аЬ> при хЕХ, и(х) = +ос при х Е Хь Л Х. (38) Пример 9. Задача: Х(х)=е * — !!п1, хеХ=(хеЕ!, д(х)=хе *=О). Множество Х состоит из единственной точки х =О, так что ~, = Х(0) = 1, Х„= (О).
Здесь функция Лагранжа Х (х, Л ) = е *+ Л хе *, х Е Х = Е ', Л Е ЕАь=Е; !Р(Л) = — оо при Л >О, !Р(Л)=0 при Л =О, !Р(Л)=Л ехр( — 1+ А) при Л < О. Множество А= (Л < О) замкнуто, функция !Р(Л) непрерывна на Л, Т!* = О, Л = (О). Таким образом, здесь Х. 4 И, Л ~И, но !Ь* < Х,.
Согласно теореме 5 функция Х (х, Л ) не имеет седловой точки. Не следует думать, что если (х, Л*) е Х, х Аь — седловая точка функции Х,(х, Л), то и точки (а, Ь) Е Х,х Аь, для которых Х (а, Ь) = Х (х„, Л"), также будут седловыми точками. В общем случае можно лишь утвер!кдать, что Х, С Х(Л*) =(х Е Хь: Х (х, Л') = Х (х„Л*)), Л СЛ(х,)=(Л ЕЛр. Х(х„Л)=Х,(х„Л")) (35) где множества Х„Л взяты из (27), (31). П р и м е р 10.
Функция Х (х, Л) = Лх, х Е Хь = Е', Л Е Ль = Е', имеет единственную седловую точку (х„= О, Л* =0), Х (О, 0) =О. Здесь Х(Л*) = = Е', Л(х„) = Е', и, как видим, включения (35) являются строгими. Далее, функции и(х), ф(Л) из (25), (28) соответственно равны и(х) =+со при х~ О, и(0) =О, и !Р(Л) = — со при Л фО, !р(0) =О, так что оба множества Х =Х, =(0), Л=Л =(0)- являются одноточечными. 6. Напоминаем, что в главе 3 мы уже рассматривали двойственную задачу для задачи линейного программирования, причем двойственная задача была введена по определению, без объяснения, откуда она появилась.
Убедимся, что введенная в Э 3.5 двойственная задача является частным случаем задачи (30). Рассмотрим общую задачу линейного программирования: 4 9. ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 231 230 Гл, 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Для вычисления функции !Ь(Л), определяемой по формуле (28), удобнее представить функцию Лагранжа Х, (х, Л) в следующем виде Х (х, Л)=( — Ь„Л,)+( — Ь„Л,)+(х„АТ Л,+Аз!Л,+с!)+(хз!А!~Л!+А~~лЛз+с,) = = — (Ь„Л,) — (Ь, Л~) + Х,'х!(А!!Л, + Ат Л + с )'+ + ),' х,'(Ат Л, + А~~,Л, + сз)'! х Е Хю Л Е Лх Отсюда следует, что ~Ь(Л) = ~ ! < Ь|, Л! > — < Ьм Лл > при Л еА! (39) ( — со при Л йЛл ЛА, где А=(Л (Л,Лл)ЕЕ 'хЕ '.
Л,>0, АТЛ,+А~~!Л,+с!>О, АТЛ,+ + Ат,Л, + с, = О). Из полученных выражений (38), (39) для функций и(х), !Ь(Л) следует, что задача (26); ! (х) — ! 1п1, х Е Х, равносильна исходной задаче (36), (37), а двойственная к ней задача (29): !Ь(Л) — зпр, Л е А, или (30) равносильна задаче л!4(Л) = — (Ь„Л,) — (Ь„Л,) - зпр (или ( — !Ь(Л)) - 1п1), Л Е Л. (40) Как видим, именно задача (40) в $3.5 была по определению названа двой- ственной к (36), (37) задачей. Сравнивая утверждения, доказанные в этом параграфе, с теоремами из $ 3.5, можем сделать вывод, что развитые здесь элементы теории двойственности являются прямым обобщением теории, из- ложенной в Э 3.5, на случай нелинейных задач. Можно также заметить, что не все утверждения, справедливь!е для задач линейного программирования, допуска!от обобщения на нелинейные выпуклые задачи.
Так, например, не- льзя утверждать, что задача, двойственная к двойственной задаче (29), в нелинейных задачах также может быть приведена к виду, совпадающему с исходной задачей (1), (2). Для невыпуклых задач это очевидно, так как двойственная задача всегда равносильна задаче выпуклого программирова- ния (32), и потому задача двойственная к двойственной, могла бы совпасть с исходной лишь тогда, если бы она была выпуклой. Однако требование выпуклости задачи здесь также не спасает положение, что видно из при- меров 6, 7, в которых двойственные задачи совпадают, а двойственная к последней не может совпасть с исходной задачей, так как исходные задачи в этих примерах разные. Ничего не меняет здесь и требование существова- ния седловой точки функции Лагранжа, о чем свидетельствует следующий пример. П р и м е р 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
