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