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