Ф.П. Васильев - Методы оптимизации (1125241), страница 66
Текст из файла (страница 66)
(4) Определение 1. Точку(х„Л*)ЕХ кЛо называют сгдловойточкой функции Лагранжа, (3), если, Ь(х„, Л) <Ь(х„Л") < Х(х, Л')! Чх Е Хы Л ЕЛо. (5) Прежде чем переходить и выяснению связи между, седловой точкой функ- ции. Лагранжа и решением задачи (1), (2), дадим другую равносильную (5)! формулировку определения еедловой! гочки, Л е м м а 1. Для того чтобы точка (х„Л*) Е Х х Л, была седловой точкой функции Лагранжа, необходимо и достапгочног чтобы вотолня- лись следуюи(иг условия: Ь(х„Л') < Ь(х! Л*). Чх Е Хо. (6) дг(х,)'=О, г'= 1',, т х ЕХ (7) Подчеркнем, что в лемме 1 от множеств Х, и; функций «(х), дг(х), г = = 1,..., г, не требуется ни выпуклость, ии какая-либо гладкость — здесь важно го! что Хо ф И и функции «(х), дс(х)', г',= 1,..., г, определены, и конечны на Хо. Доказательство.
Необходимость,. П!Усть(х„Л*)!ЕХохЛ— седловая точка. Тогда условие (б) представляет собой правое неравенство~(Ь). Остается получить условия (7), Для! этого перепишем левое неравенство (5) с учетом, конкретного вида:(3), функции Лагранжа: «(х„)+ 2, Лгд!(х,) <«(х„)+. 2„Л,,*.дг(х,) УЛ Е Ло. (8) =! г=! Отсюда имеем с„(Л!' — Л!)дг(х„) ~ ~0 ЧЛ е Ло. (9) != !. Покажем, что х„Е Х. Возьмем точку Л =(Л,, Л: ), где Лг = Л;+ 1 некотором у'„1' <,«< гп, и Л, = Л,* при всех остальных г = 1,..., в (г г4 7').
Из определения (4) множества Ло и из того, что Л* е Л, следует, что выбранная точка Л Е Ло. Из (9) при таком Л поггучим, (! — 1)д,.(х,)> 0; т. е. д)(х,) < 0 при всех « = 1,..., гп. Далее, пусть Л = (Л „...,, Л,) — точка! с координатами Л, = Л,*. + д.(х,) при некотором у,', т+ 1 < «< в, и Л, = Л,* при всех г = 1,..., в, г ф «. йсно, что Л е Л,. Поэтому из (9) имеем — )д1(х,))х> О, т. е, д,(х„) =0 при всех « = пг + 1',,..., в. Таким образом, доказано, что х„Е Х. Возьмем точку Л = (Л„..., Л,) с коврди!гатамй Лг = О, при некотором, гг 1 < «< гп, и Л! = Л; при всех остальных г = 1,..., в, г' ~«. Такая точка принаплежит Ло, поэтому нз, (9) получим 0 < Л,*,дг(х.).
Но Л,,* > О, д, (х„) < < 0 при д', = 1,...,.,пг, поэтому последнее неравенство возможно лишь при Л;д,(х,) = 0; «! = 1,..., гп. Все соотношения (6), (7) получены. Е 9. ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 219 усть для некоторой точки (х„Л") е Хо хЛ, выпол). Покажем, что тогда !(х„Л*) — седловая точка. авенство (5). Остается доказать левое неравенх„Е Х, т. е. д, (х,,) < О, г = 1,..., гп, д, (х,) = О, Достаточность. П иены соотношения (6), (7 Из (6) следует правое нер ство (5), По условию (7) г = т+1,..., г.
Тогда (с,(х, ! *), х — х„) = («':(х )+ 2 Л;д,'(х„), х — х,) > 0 !7х Е Хо (11) =! Л д(о )=0 г=1 пг х ЕХ (12) Д о:к а з а т е л ь,ств о. При сделанных предположениях функция Лагранжа (3) выпукла и дифференцируема в точке х,,е Хо при каждом Л е Ло. Поэтому условие (6) согласно теореме 2,3 равносильно условию (11).
Условия (7) и (12),совпадают. П Теперь выясним, как связаны между собой седловая гочка функции Лагранжа и решение задачи (1), (2). Т е о р е м а 1. Пусть!(х., Л*) е Х, хЛ вЂ” сгдловая.точка функции.Лагранжа. Тогда х, е Х„, «„= Ь(х„Л"') = «(х,), т. г. х. является решением задачи (1), (2). * Д о к.а.з а т,е л ь!с т в о. Из условия (7) имеем х е Х и Ь (х, Л") = «(х ).
Тогда неравенство (6) перепишется в виде «(х.) < То(х, Л*) =«(х)+ 2; Л,*.д!(х), х ЕХо. ( 1'3) г= ! ю В частности, (13) верно и для всех х ЕХ. 'Но 2' ,Л,".д,(х) < 0 при хе Х, так как тогда дг(х) «О и 'Л,">О при г'=1,..., гп и дг(х)=0 при г=гп+1,..., ю Поэтому из (13) следует, что «(х,)<г. (х, Л*)<«(х) при,всех х Е Х, т, е. х,ЕХ..П Заметим, что теорема 1, как и лемма 1,,доказаны без каких-либо ограничений на функции «(х), д«(х), г' = 1,,..., в, и на множество Х„в частности, никакие предположения о выпуклости, сделанные выше при формулировке задачи (1), (2), мы пока не использовали. 2. Возникает воцрогл во всякой ли задаче вида !(1), (2) функция Лагранжа имеет седловую точку? Ответ здесь, конечно, отрицательный; если в зада- (Л,* — Лг)д,(х,) = 0 (10) при всех г = т + 1,..., в и всех тех г, 1 < г < т, для которых д,.(х„) = О.
Если д,(х,) < 0 при некотором г, 1 < г < пг, то из равенства (7) следует,, что Л,*. =О. Поэтому (Л;.— Л!)дг(х.) = — Л!д,,<(х„) > 0 для всех Л! >'0„1 < г < т, для которвгх дг(х„) < О. Складывая получейные .неравенства с (10), будем иметь 2,',(Л,*.— Л )д(х)>0 для всех Л ЕЛ . Отсюда 2 Л д (х) < 2; Л;.д(х) при ;=-! всех Л Е Л,. Добавляя,к обеим частям этого неравенства «(х ), придем к не авенсгву (8), представляющему собой левое неравенство (5). П сли сделать, дополнительные предполохгения о выпуклости и гладкости задачи (1), (2), то лемму 1 можно переформулировать в следую!цей так называемой дифференциальной форме. Лемма,2. Пусть !(1),!(2) представляет собой задачу выпуклого программирования и функции «(х)! д,(х),..., д„(х) диффергнцируемы в тонче х, е Х,.
Тогда для того чтобы точка (х„Л') е Хо х Л, была свдловой точкой функции, Лагранжа, необходимо и достаточно, чтобы 220 Гк 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 4 9. ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 221 че (1), (2) Х, = !21, то, как следует из теоремы 1, функция Лагранжа такой задачи не может иметь седловую точку. Более того, даже в выпуклых задачах с Х„40 в общем случае нельзя ожидать, что функция Лагранжа будет иметь седловую точку.
Пример 1. Рассмотрим задачу из примера 8.1: 7(х)= — х- !и1, хЕ Е Х=(х ЕХ: д(х)=хо<0), где Хо=(х ЕЕ'! 0< х< а), 0< а<со. Здесь множество 7ьо выпукло, функции Т(х), д(х) выпуклы на Х,. Множество Х состоит из одной точки х = О, так что 7", = 7'(0) = О, Х, = (0). Функция Лагранжа 5(х,Л)= — х+Лхз! 0<х<а, Л >О, рассматриваемои задачи не имеет седловои точки. Таким образом, для существования седловой точки на задачу (1), (2), кроме условий выпуклости, должны быть наложены какие-то дополнительные ограничения. Начнем с рассмотрения случая, когда в (2) ограничения типа равенств отсутствуют (гп = г), т.
е. множество Х имеет вид Х = (х Е Хо. д!(х) < О, 4 = 1,..., тп). ( ) Предположим, что выполнено условие Слейтера, т. е. существует точка х Е Х такая, что д,(х) <О, ..., д (х) <О. (15) Напомним, что условием (15) мы уже пользовались в 9 8. Если Х вЂ” выпуклое множество, функции до(х) выпуклы на Х„то вместо (15) достаточно потребовать !ьзя каждого 4 существования точки х, е Х такой, что до(х!) < О, 4 = 1,..., гп. Тогда в качестве х из (15) можно взять х= 2; а!хо, а! >О, а, +а +...+а =1, поскольку хЕХо и в силу неравенства (22) дз (х) < ~; а! дз (х! ) < а! д (х, ) < О, д = 1,..., т. ' =- ! Не следует думать, что если множество (14) выпукло и имеет внутренние точки, то условие Слейтера непременно выполняется.
П р и м е р 2. Задача: ]'(х) = х — ! !и1, х Е Х = (х Е Е': д(х) < О), где ] х' при х<0, ], 0 при х>0. Очевидно, функции 3'(х), д(х) выпуклы (и даже дифференцируемы) на Хо = = Е ', так что задача выпукла. Здесь Х = Е ', Х, = (О), 7", = О. Как видим, все точки х > 0 являются внутренними для мйожества Х, но д(х) аз О Чх > О, и условие (15) заведомо не может выполняться, Убедимся, что функция Лагранжа Е (х, Л ) = х + Лд(х), х Е Хо = Е', Л Е Ло = Е„' этой задачи не имеет седловой точки. Согласно теореме 1 седловыми могут быть лишь точки вида (х„=О, Л > 0).
Однако неоавенство Е(0, Л) =0= 7", < 5(х, Л) не может выполняться при всех х Е Е ни при каком Л > О. В самом деле, если Л =О, то Е(х, Л) = х < 0 Чх < 0; если Л > О, то 5(х, Л) = х+ Лхз < 0 при всех х, — Л < х < О, Те о р е м а 2 (Кун — Таккер). Пусть множество Х, выпукло, функции 7'(х), до(х), 4 = 1, тп, вьипуклы на Х и выполнено условие (15). Пусть множество Х, точек минимума функции !'(х) на множестве (14) непусто, Тогда для каждой точки х„е Х, необходимо суи4гствуют множители Лагранжа Л*=(Л;,..., Л,*„)ЕЛ =(Л ЕЕ: Л, >О,..., Л >0) такие, что пара (х„, Л*) образует седловую точку функции Лагранжа на множест- ве.Х, х Ло.
До к а з а т е л ь с т в о. В пространстве Е" э' переменных а= (а, а„... ..., а ) введем множества А=(а=(а, а„..., а ) ЕЕ о!! ао > 7(х), а, > д (х),...,а > д (х), хЕХо), В=(Ь=(Ьо, Ь„...,Ь )ЕЕ "'. Ьо<э„Ь! <О!...! Ь <О). Покажем, что А и В не имеют общих точек. В самом деле, пусть а Е А. Тогда найдется точка х Е Хо такая, что ао > 7(х), а, > д,(х),..., а > д (х). Возможно, что х Е Х. Тогда а > 7'(х) > 7', и заведомо аЕ В, Если же х Е Е Х ~ Х, то найдется номер 4, 1 < 4 < гп, такой, что д!(х) > О.
Тогда а! > > д,(х) > 0 и снова а ф В. Итак, А Г! В = !2!. Далее, нетрудно видеть, что А и  — выпуклые множества. Покажем, например, что А выпукло. Пусть а, с — две произвольные точки из А. Тогда сУществУют точки и, о Е Хо такие, что ао > !'(а), со > !(о), а! > д!(и), с! > > д (о), 4 =1,..., гп.
Возьмем произвольное а Е[0, 1] и положим а, = аа+ + (] — а)с, и„= ам Ч (! — а)о. Из выпуклости Х, следует и Е Х,. Далее, из выпуклости функции 7(н), д,.(и) имеем 1(н ) < а7(н) + (1 — а)7(и) < аао+ (1 — а)со, д!(а ) < ад (и) + (1 — а)д,(о) < аа! + (1 — а)с,, з = 1,..., гп. Это означает, что а Е А. Выпуклость А доказана. Аналогично доказывается выпуклость В, В силу теоремы 5.2 тогда существует гиперплоскость (с, а)= ! с нор- мальным вектором с=(Л*, Л*„..., Л* )фО, отделяющая А и В, а также А и В=(Ь=(Ь„Ь„..., Ь„) ЕЕ"+', Ь <,!"„, Ь, < О,..., Ь <0]-, Это значит, что (с, Ь) = 2, 'Л,*Ь! <.у < (с, а) = 2,' Л,".а! ЧаЕ А, Ь Е В.
(16) =о =о Заметим, что у =(7"„О,..., 0) Е А Г!В. В самом деле, возьмем какую-либо точку х„ЕХ„. Тогда !'(х,) =!'„до(х,) <О, Ь = 1,..., гп, что означает у Е А. Включение у Е В очевидно. Тогда по теореме 5.2 величина 7 из (16) равна Т = (с, у) = Л;7'., и (16) можно переписать в виде Л;Ь,+ ~" Л;.Ь! < Л;Х,< Л,*а,+ 2 Л;.а,. ЧаЕА, Ь Е В. (17) о=! !=! Возьмем точку Ь = (Г, — 1, О,..., 0) е В.
Из левого неравенства (17) получим Ло(7'.— 1)< Лоу„, откуда Л,* >О, Далее, беря Ь =(7"„,О,...,О, — 1,0,..., 0), нз левого неравенства (17) ймеем Ло7", — Л,". < ЛоХ, т. е. Л,*. > О, 4 =1,, гп. Таким образом, показано, что Л* = (Л*„..., Л' ) > О, Л," >О. Далее, возьмем произвольную точку х. е А.',, Тогда а= (!'(х,) = ~., О,... ...,О, д,.(х„), О,..., 0) Е А Г! В. Подставляя эту точку в левое и правое неравенства (17), получаем Л" 7", + Л;д,,(х„) < Лоу„( Л*7"„+ Л;.д!(х,), откуда Л,*.д (х ) <О < Л;д (х ) или Л,*д (х ) =О, ! =1,..., гп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
