Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 67
Текст из файла (страница 67)
более того, даже в выпуклых задачах с Х„~И в общем случае нельзя ожидать, что функция Лагранжа будет иметь седловую точку. Пример 1. Рассмотрим задачу из примера 8.1: 7'(х)= — х- 1п1, хе Е Х = ( х Е Х: д(х) = х < О), где Хо — — (х Е Ь '. 0 < х < а), 0 < а < со. Здесь множество ло выпукло, функции Г(х), д(х) выпуклы на Хо. Множество Х состоит из одной точки х = О, так что 7', = 7"(0) = О, Х„= (0). Функция Лагранжа Ь(х, Л)= — х+Лхо, 0< х< а, Л )0> рассматриваемой задачи не имеет седловой точки. Таким образом, для существования седловой точки на задачу (1), (2), кроме условий выпуклости, должны быть наложены какие-то дополнительные ограничения.
Начнем с рассмотрения случая, когда в (2) ограничения типа равенств отсутствуют (т = г), т. е. множество Х имеет вид Х = (х Е Хо; д!(х) < О, 4 = 1,..., т). (14) Предположим, что выполнено условие Слейтера, т. е. существует точка х е Х такая, что д,(х) < О, ..., д,„(х) < О. (15) Напомним, что условием (15) мы уже пользовались в В 8. Если Хо — выпуклое множество, функции до(х) выпуклы на Х, то вместо (15) достаточно потребовать для каждого 4 существования точки х! Е Х такой, что до(х!) < О, 4 = 1,, т, Тогда в качестве х из (15) можно взять х = ~ с!ох!, !х! > О, а! + а, +... + !л„= 1, поскольку х Е Х и в силу неравенства (2.2) д,(х) < 2; оод,.(х!) < о!д,(х,) < О,,у' = 1,..., т.
!=! Не следует думать, что если множество (14) выпукло и имеет внутренние точки, то условие Слейтера непременно выполняется. Пример 2. Задача: 7(х)=х- !п1, хЕХ=(хЕЬ': д(х)<0), где )' х при х<0, 1 0 при х>0. Очевидно, функции 7(х), д(х) выпуклы (и даже дифференцируемы) на Х = = Е ', так что задача выпукла.
Здесь Х = Е,', Х„= (0), 7", = О. Как видим, все точки х > 0 являются внутренними для мйожества Х, но д(х) =0 Чх > О, и условие (15) заведомо не может выполняться. Убедимся, что функция Лагранжа Ь(х, Л) = х+ Лд(х), х Е Хо = Е', Л Е Ло = Е+ этой задачи не имеет седловой точки. Согласно теореме 1 седловыми могут быть лишь точки вида (х„= О, Л > 0). Однако не~оавенство Ь (О, Л ) = 0 = 7, < Ь (х, Л ) не может выполняться при всех х Е Е ни при каком Л > О. В самом деле, если Л = О, то Х (х, Л) = х < 0 Чх < 0; если Л > О, то Х (х, Л) = х+ Лхо < О при всех х, -Л < х < О.
Т е о р е м а 2 (Кун — Таккер). Пусть множество Х, выпукло, функции 7(х), д (х), 4 =1, т, вьтуклы на Хо и выполнено условие (15). Пусть множество Х, точек минимума функции 7'(х) на множестве (14) непусто. Тогда для каждой точки х, Е Х, необходимо существуют множители Лагранжа Л'=(Л;,..., Л,*„)ЕЛ =(Л ЕЕ™м: Л, >О,..., Л >О) такие, что пара (х„Л*) образует сгдловую точку функции Лагранжа на множест- ве Хо х йо До к а з а т е л ь с т в о.
В пространстве Е"+' переменных а= (а, а„... ..., а ) введем множества А=(а=(ао, а„..., а )ЕЕ "'. ао >7(х), а, > д(х),..., а > д (х), хЕХ), В = (Ь = (Ъ, Ь„..., Ь„) Е Е + '. Ьо < 7'„, Ъ! < О,..., Ь < О). Покажем, что А и В не имеют общих точек. В самом деле, пусть а Е А. Тогда найдется точка х Е Хо такая, что ао > 7(х), а, > д,(х),..., а„> д (х). Возможно, что х Е Х. Тогда а > 7(х) > ~„и заведомо а !р В.
Если же х Е Е Х, 1 Х, то найдется номер 4, 1 < 4 < т, такой, что д,.(х) > О. Тогда а! > > д(х) >0 и снова а!р В. Итак, А ПВ =Я. Далее, нетрудно видеть, что А и  — выпуклые множества. Покажем, например, что А выпукло. Пусть а, с — две произвольные точки из А. Тогда существуют точки и, о Е Х такие, что ао > 7(и), с > Г(и), а! > д,. (и), с! > > д. (и), 4 = 1,..., т. Возьмем произвольное с! Е [О, 1] и положим а„= с!а+ + () — а)с, и„= ои+ (1 — о)о. Из выпУклости Хо следУет и Е Хо. Далее, из выпуклостй функций 7(и), до(и) имеем Г(и„) < с!7(и) + (1 — а)1(и) < соа + (1 — а)со, д (и,) < од (и)+ (1 — со)до(и) < аа, + (1 — о)со, 4 = 1,..., т.
Это означает, что а, Е А. Выпуклость А доказана. Аналогично доказывается выпуклость В. В силу теоремы 5,2 тогда существует гиперплоскость (с, а)=Т с нор- мальным вектором с=(Л', Л*„..., Л' )~0, отделяющая А и В, а также А и В=(Ь=(Ъ„Ь„..., Ь„) Е Е" +'! Ь < У„Ь! < О,..., Ь < О). Это значит, что (с, Ь) = 2" Л,*.Ь! < у < (с, а) = 2" Л,*. а! Ча Е А, Ь Е В. (16) о=о ;=о Заметим, что у = (7„0,..., 0) Е А ОВ. В самом деле, возьмем какую-либо точку х. Е Х,. Тогда 7(х„) =7"„до(х„) <О, 4 =1,..., т, что означает у Е А.
Включение у е В очевидно. Тогда по теореме 5.2 величина Т из (16) равна "у = (с, у) = ЛК, и (16) можно переписать в виде ЛоЪо+ л,' Л,."Ь! < Ло~ < Лоао+ Я Л а,. ЧаЕА, Ь Е В. (17) ю=! !=! Возьмем точку Ь = (7. — 1, О,..., 0) е В. Из левого неравенства (17) получим Л "(7„— 1) < Л;7"„, откуда Л; > О. Далее, беря Ь = (7„0,..., О, — 1, О,..., О), из левого неравенства (17) ймеем Лоу'. — Л,*. < Л*Г"„, т. е.
Л,'. > О, 4 = 1,, т. Таким образом, показано, что Л*=(Л*„..., Л ) > О, Л' >О. Далее, возьмем произвольну!о точку х„Е Х,. Тогда а= (7" (х,) = 7"„О,... ..., О, д,(х„), О,..., 0) е А П В. Подставляя эту точку в левое и правое неравейства (17), получаем Л*У„+ Л'.д,. (х„) < Л;7', < Ло,!', + Л;д,(х,), откуда Л,*.д (х ) < О < Л,*д (х ) или Л,".д (х ) =(), 4 = 1,..., тп. Равенства (7) доказаны. Покажем, что Л," > О. В самом деле, в (17) подставим а=(7(х), д,(х),... ..., д (х) Е А, где х взято из (15). Получим Ло,7, < ЛоУ(х)+ л,' Л;до(х) До пустим, что Л* = О.
Тогда Л' ~ 0 и из предыдущего неравенства при Л* = 0 с $9. ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 223 222 Гл. 4 ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА учетом условия (15) имеем 0 < Х Л,*.дв(х) < О. Полученное противоречие по! =. ! казывает, что Л; > О. Неравенства (17) сохраняют силу, если (17) разделить на Л" > О.
Поэтому в (17) можем считать Л' = 1. Наконец, возьмем произвольную точку х е Хг. Тогда а= (1(х), д,(х), ..., д (х)) я А. Подставим эту точку в правое йеравенство (17). С учетом того, что Лг — — 1, получим Х„( Х(х) + 2, Л,'дв(х) = Х (х, Л*), х Е Хв. Но в р= ! силу (7) 1, = Х (х„, Л*) при любом выборе х, Е Х,. Отсюда и из предыдущего неравенства следует условие (6). Согласно лемме 1 тогда (х., Л')— седловая точка.
Теорема 2 доказана. П Другую форму теоремы 2 читатель найдет в $5.5. 3. Приведенные выше примеры 1, 2 показывают, что без дополнительных условий вида (15) теорема 2, вообще говоря, неверна. Однако, если (2)— многогранное множество (пример 1.6), то, оказывается, существование седловой точки функции Лагранжа выпуклой задачи (1), (2) можно доказать без каких-либо дополнительных условий. Это мы уже показали для общей задачи линейного программирования — см. теорему 3.5.5. Теперь рассмотрим более общий случай, не предполагая линейности целевой функции. Будем пользоваться следующим представлением многогранного множества Х = (х Е .Е": х Е Хю д, (х) = (ав, х) — 6, < О, в' = 1,..., т; дв(х) = (ав, х) — 6, = О, в = т+ 1,..., г), (18) где Х, в свою очередь, является многогранным множеством и задается в виде: К=К(х,)=ве ЕЕ: ет=О, (ав, е) (~0, в Е 1,, (ав, е)=0, в=тц-1, г (йв е) ( <О! в' е Хв', (йв, е) = О, в' = р 1 1,, г) где 1!" — — (в: 1 ~< в < т, (ав,х,) = 6,), Х' = (в; 1 < в < р, (,Х, Доказательство.
Пусть е =(е',..., е") ~0 — произвольное возможное направление множества (18) в точке х„. Согласно определению 2.3 тогда существует такое число 4, > О, что х = х, + ве Е Х или (а„х. + Ье) < Ьв, в'=1,..., т; (ав, х,+се)=ЬИ в'=т+1,..., г; (йв, х,+ве) ( г„в=1,..., р; (йв, х,+Ье) = г„в'=р+ 1,..., д; при всех в, 0 < 4 < ~. С учетом того, что х, е Х и определения множеств 1;, 1," активных индексов точки х. из (20), сразу получаем е е К.
Верно и (20) Хь — — (х С Е": (в(в, х) < гв, в' = 1,..., р; (йв, х) = гв, в = р + 1,:, д), ав, й! е Е" — заданные векторы, Ьв, г! — заданные числа. В частности, здесь возможно Х =Е", Х =Е+, Х =(х=(х',..., х"): х! >О, в е1), 1 — некоторое подмножество номеров (1,..., и); Х,=(х=(х',..., х"): ов < х! < < дв, в = 1,..., и), ав, !8! — заданные величйны, св! < Д, причем некоторые Для многограйного множества несложно дать полное описание всех возможных направлений в любой его точке (определение 2.3). Л е м м а 3. Множество возможных направлений множества (18) в любой его точке х, совпадает с конусом: а равенство (22) можем переписать в виде Х'(х„)+ 2, 'Л;а! = — 2, 'р,вй, — 2, 'вв,*.й!. '=! ~вГр' в=р+! (24) Функция Лагранжа в рассматриваемой задаче (1), (18) такая: Х (х, Л) = Х(х) + Я Л,.((ав, х) — Ь,), х ь.
Хю Л е А . в=! Тогда, используя неравенство 1(х) — 1(х„) > ( 1'(х,),х — х,), х ~ Х (теорема 2.2), определение множества Х*, условие ввг > О, в е 1*, и равенство (24), для каждого х е Хв получаем 5(х, Л*)-Х,(х.,Л")=Х(х)-Х(х.)+ Х.л:(а! х-'.) > р * =! > ( г'(х,) + 2 Л,"ав, х — х„) = — ~ ~ р~(йв, х — х„)— в вру ,*(й х ) — — 2 р'((йв, х) — г!) > О, в=рв! ' е в! Х,(х„л') ( Е(х, Л') ввх Е Хю или обратное: если е е К, то е — возможное направление в точке х,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
