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