Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 59
Текст из файла (страница 59)
Тогда существует подпоследовательность ((< А), сходящаяся к некоторему числу р) О. Из равенства Ь „= « „— И дае (й= 1, 2,...) при й- о следует, что пределЪ= Иш Ь „существует, причем 1-» ю Ь = <1 — 1<азам ~>р < в силУ замкнУтости ~г-<. Таким обРазом,показано, что д= Ь+ )заю где Ь<и Де „д > О. Из (20) тогда следует, что <1<и <,"<. Замкнутость <„< доказана. Доказательство теоремы 3. Введем множество с~ Е": с = — ~~ Л<с<, Л ) О,..., ЛР~)0 . (21) <=1 Заметим, что у — конус, порожденный векторами — с„..., — сю — сг«, ..., — с„се+„..., с,. В самом деле, с одной стороны, все точки с = ~, Л<( — с<) + ~ а<( — с;)+ ~ч~~ р<с< (Л,)0, 1=1,...
т Р+1 <е Р+1 ..., р; а< ~ О, р< ) О, 1= р+ 1, ..., г) принадлежат <',>. С другой стороны, любая точка с = — Л,с, —... — Л,с, представима в виде предыдущего равенства при и, = шах(0; Л<), р< = шах(0; — Л,) (1= т+ 1, ..., з), так как Л< = а< — («. В силу леммы 3 тогда множество (21) является выпуклым замкнутым множеством. Для доказательства теоремы 3 достаточно установить, что < Ке = <>. Возьмем произвольный вектор с ~ <<<, т.
е. с = — 2< Л<с< <=1 (Л< ~ О, ..., Л<, ~ 0). Тогда для любого е <и К имеем <с, е) = = — ~ Л<<с<, е) зО. Это значит, что с~К*. Тем самым пока<=1 вано, что <',> ':- К*. Покажем обратное включение Ке — (>. Предположим противное: пусть существует у ~ К", но у Ф <',>. Поскольку <> — замкнутое выпуклое множество, то по теореме 5.1 зто множество сильно отделимо от точки у.
Это означает, что существует гиперплоскость <д, и — у>=0 с нормальным вектором «чьО такая, что «<, с — у>) 0 или «1, с>>«<, у> для всех с <и (>. Согласно (21) зто значит, что < д, —,,"~~ Л,су) = — ~~ Л; <с;, с<> ) (<(, у) (22) 1=1 <' 4=1 при всех Л„..., Л., лишь бы Л, > О, ..., Лг ) О.
Покажем, что тогда д ~ К вЂ” замыкание К. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА (гл. 4 Зафиксируем некоторый номер (, 1 < ( < р, и в (22) примем >в= 0 при всех )Ф й Получим — >в<се Н» <й, у> для любого >ч>0. Отсюда, деля на гв>0 и устремляя Х; —, получаем <сь г(>) 0 или <сь с(>< 0 ((= 1, ..., р).
Далее, зафиксируем номер ( (р+ 1 < ( < з) и в (22) примем Л; = 0 при всех у Ф (, Л; = а<со й> (г > 0). Получим — П <се г(>~' ><и, у>. Отсюда, деля на ( > 0 и устремляя ( —, получаем — ~<со й)!' > 0 нли <сь с(>= 0 (( = р+ 1, ..., з). Таким образом, показано, что йжК. Теперь вспомним, что у ш Кв. Это значит, что <у, е» 0 для всех е ~ К. Отсюда с помощью предельного перехода нетрудно получить, что <у, е)> 0 для всех е гк К.
В частности, для .а'ю К имеем <у, с(>~ О. Но, с другой стороны, если в (22) принять Е, = 0 (( = 1, ..., з), то получим <у, а>< О. Пришли к противоречию. Следовательно, К* — <>. Сравнивая с ранее доказанным включением чг — К*, заключаем, что К* = ь>. Равенство (19) и, тем самым, теорема 3 доказаны. 4.
Рассмотрим задачу минимизации функции г(и) на множестве П =(и ш Г,: у~(и) =<аь и> — Ь' < О, ( = 1, ..., т; у,(и) =<аь и> — Ь' = О, ( = пг + 1, ..., з), (23) где П, =(и ш Е": <аь и>< р', ( = 1, ..., р; <йь и>= ~', =р+1, ..., ц) — МНОГОГраННОЕ МНОжЕСтВО, ао а;'ЕЕ" — Задапные векторы, Ь', Т вЂ” заданные числа. В частности, здесь может быть П, = Е~.,' П, =(и =(и', ..., и"): и* > О, ( ~в П, Т— некоторое подмножество номеров (1, ..., п); П, =(и =(и', ..., и"): и~ < и' < (>ь (= 1, ..., и), а;, ~ч — заданные величины, оа < р„причем, возможно, некоторые а<— Теорема 4.
Пусть функция г(и) выпукла на Пь г(и)~ ж С'(П,), гзножество П определено согласно (23), Г„ь(и ен (Т: г (и) = 1п( у(о) = У ) — оо)чь 8. Тогда для каждой точки чаи ив е= Пв необходимо существуют множители Лагрангка л* = (>ч, ..., ),) ~ Л„= (Ь = (>,..., >.,) ~ Е': >ч) О,..., А ) 0) такие, что пара (ив, Х*) образует седловую точку функции Лагранжа на множестве П, Х Л,. Из этой теоремы, в частности, следует, что в любой задаче линейного программирования, имеющей решение, функция Лагранжа всегда имеет седловую точку. Доказательство. В силу теоремы 2 11 множество (23) выпукло. Возьмем любую точку ив е= Пв.
Введем множества индексов Хд — (О 1((~~т, (аь и ) = Ь'), Тз =((: 1(((р, <ан и„,) = Я зм ТЕОРЕМА КУНА — ТАККЕРА. ДВОИСТВЕННАЯ ЗАДАЧА 245 и составим конус К=(ееиК": (а1,е)~(0, 1~11, (а;,е)=0, 1=т+1,...,з; (а1, е) < О, 1 е= 12, Щ, е) = О, 1' = р + 1,..., д; е ~ 0). (24) Покажем, что множество возможных направлений множества (23) в точке ие совпадает с конусом (24). Пусть е =(е', ..., е")Ф 0 — произвольное возможное направление в точке ие.
Согласно определению 2.3 тогда существует такое число 1, > О, что и = и + Те ек П или (а;, ие + 1е) < Ь1, 1 = 1, ..., т; (а1,и + 1е) = Ь', 1=т+1,...,г; (25) (111, не+ 1е)(/1, 1= 1,..., р; (д1, и, + $е) = 11, 1=р+1,...,7, при всех 1 (0<1<1,).
С учетом иеенПес11 из (25) сразу получаем еж Х. Верно и обратное: если еж К, то е — возмоя1- ное направление в точке и„. В самом деле, пусть еж К. Тогда для 1~ 1, имеем (а;, из + 1е) = Ь1+1(а1, е)<Ь1 при всех 1> ~~0, а если 1Ф1, (1<1<т), то (аь и )<Ь1 и найдется такое Г, > О, что (аь ие + ге) <Ь' при 0 < ~ < 1,. Если т+ 1< <1< а, то (а;, из + 1е)=Ь1 при всех й Аналогично, взяв при необходимости 1,>0 еще меньшим, убедимся, что выполняются и остальные соотношения (25), так что из+ 1еен 51 (0<1< <1,). Тем самым показано, что для множества (23) множество возможных направлений в точке ир совпадает с конусом (24).
Согласно теореме 2.3 для того, чтобы ар ~ 112, необходимо и достаточно выполнения неравенства (Х'(и. ), и — и.'))0 11и~(1. (26) Возьмем любое е 1и К. Тогда и = ир + Те я 11 (О < 1 < Т„тз) 0). Подставим такую точку и в (26) . Получим (Х' (и„), е) 1) 0 или (1 (из), е)~)0 при всех еж К. Это значит, что Х'(ир)енК*. Ф По теореме 3 тогда найдутся числа Лз )~ 0 (1ек 11), Л +„..., Л„ р1) 0 (1ен 1,), рре„..., )22 такие, что 1'(ир) = — ~', Л1а; — ~; Л;а; — ~ р;г(1 — ~'„р;д1.
(27) 1 1 1=и+1 ° 1* 1=Р+1 2 Если доопределим Л; = 0 при 1~(1,..., т)'~1„то получки точку Л* = (Л„..., Л,) ~ Ле. Отсюда, учитывая определение множества 1, и условие ие е= 11е с=(1, имеем Л1 ((а1, ие) — Ь') = Л4я1(ие) = О, 1 = 1, ..., г2 (28) ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА !РЛ. 1 246 а равенство (27) можем переписать в виде в в 1'(и ) + Д Л;а; = — ~ р;а1— 1=1 1е а+1 »ит (29) Функция Лагранжа в рассматриваемой задаче такая: 1 (и, Л) =1(и) + ~ Л1((аь и) — Ь1), нее П», ЛенЛ,. Тогда, используя неравенство Х(и) — 1(и»))(1 (ие), и — и ) (и~0) (см. теорему 2.2), определение множества 1„(условие р1 )О (1е= 1,') и равенство (29), для каждого и 1к П, получаем 1,(и, Л») — 1,(и, Л») = 1 (и) — 1 (и ) + Д Л1 (а1, и — иь) ) 1=1 ) Х'(и )+ ~~э~ Л1а1, и — иь = — ~; р,'(дь и — и„'>— 1=1 1итз' — р1 (с(1, и — и ) = — ~ р; ((с(1, и) — 11) ~~ О» 1=Р+1 з 'и1 или непусто.
Кроме тово, пусть выполняется хотя бы одно из следующих условий: а) П, — многозранное множество, функции 1(и), у1(и), ..., д„(и) выпуклы на выпуклом множестве Ит, открытом в а11Ит (т. е. Ит=г1И'), П,сИ' и существует точка й1В П такая, что д1(й) ~ О (1 = 1, ..., т); б) существует точка й ы г1 П, О П так ц что у;(й) < О (1=1, ..., Л»).
Л (иь, Л*) (1 (и, Л*) Чи ее П». Отсюда и из (28) с помощью леммы 1 заключаем, что (и», Л*)— седловая точна фуннции Лагранжа. 5. Наконец, приведем следующий более общий вариант теоремы Куна — Таккера. Теорема 5. Пусть П, — выпуклое множество из Е', функции 1(и), у,(и) (1=1,...,т) выпуклына Пну~(и)=(а<,и> — Ъ' (1= п»+ 1, ..., 1) — линейные функции. Пусть множество Пь точек минимума функции 1(и) на множестве П=(и1и П~.' в1(и)(0, 1= 1, ..., у<(и)=<а„и> — Ъ' ( О, 1= т+ 1, ..., р; у,(и)=(аь и> — Ь* = О, $ = р+ 1, ..., з) $9! теОРемА кунА — тАккеРА. дВОйстВеннАя ЗАдАчА 249 Тогда для каждой точки и ее П необходимо существуют множители Лагрангеа Ле = (Л~г, ..., Л,') е= Л = (Л~ Е": Лг) ~)0,..., Лр)~0) такие, что пара (из, Л*) ооразует седловую точку функции Лагранжа на множестве (во ХЛ,.
В этой теореме не исключаются возможности, когда отсутствуют какие-либо из ограничений дв(и)(0 или ув(и)=0, т. е. р = 0 или т = О, или з = О, или т = р, или т = з, или р = т = = з. Доказательство теоремы 5 требует весьма тонкого использования теоремы отделимости 5.2; за подробностями отсылаем читателя к (211 (ср. с (264, 3 28?). Условия а), б) теоремы 5 представляют собой обобщения условия регулярности (13) на случай более общей аадачи (1), (2).Нарушение этих условий может привести к отсутствию седловой точки. Пример 2. ПустьП, = (и = (х, у) 9=.Е9: х)0, у)0) = Ез+ з(и)= Уху, у(и)=х, П=(иш Уо: у(и)< 0). Здесь По выпукло, г(и), д(и) выпуклы на П„у = О, Пз= 5" = (из=(0, у), у)0).
Функция Лагранжа Ь (и, Л) = — Уху + Лх (х ) О, у > О, Л > 0) не имеет седловой точки. Нарушено условие а): функция г(и) выпукла лишь на П„требуемой точки й нет. В примере 1 и'У, П П = 8 — нарушено условие б). С другой стороны, нетрудно привести примеры выпуклых задач, в которых условия регулярности а), б) нарушены, но седловая точка существует. П р и м е р 3. Пусть 5то =(и вн Е': и ~~ 0), вв(и) = и, у(и) = ио, П =(и: и ш П„д(и)» 0).
Здесь (?, выпукло, функции г (и), у(и) выпуклы на По. Множество (? состоит из единственной точни и= О, так что л„= О, Пз = (0). Функция Лагранжа Ь(и, Л)= и+Ли' (и ~ О, Л ~ 0) имеет седловую точку (из = О, Ле = 0), хотя г( ьв'о П (? = оо. Этот же пример показывает, что множители Лагранжа, вообще говоря, определяются неоднозначно — здесь точки (из = О, Л*) при любом Лз)~ 0 являются седловымп точками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
