Ф.П. Васильев - Методы оптимизации (1125241), страница 67
Текст из файла (страница 67)
Равенства (7) доказаны, !]окажем, что Л* > О. В самом деле, в (17) подставим а=(7"(х), д,(х),... ..., д (х) Е А, где х взЯто из (15), ПолУчим Ло,!, < Лоз (х)+ Л; Л,*д!(х). До- пустим, что Л,*=О. Тогда Л фО и из предыдущего неравенства при Л* =0 с Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА учетом условия (15) имеем 0 < 2', Л;дс(х) < О. Полученное противоречие по=! казывает, что Л,* > О. Неравенства (17) сохраняют силу, если (17) разделить на Л* > О.
Поэтому в (17) но>кем считать Лд = 1. Наконец, возьмем пРоизвольнУю точкУ х Е Хд. Тогда а= (1(х), д,(х),... ..., д (х)) е А. Подставим эту точку в правое йеравенство (17), С учетом того, что Л,", = 1, получим 1, <,1(х) + ~, 'Л,'.д,.(х) = Е(х, Л'), х е Хд. Но в т=! силу (7) 1, = Е(х„Л*) при любом выборе х„Е Х,. Отсюда и из предыдущего неравенства следует условие (6). Согласно лемме 1 тогда (х„Л')— седловая точка.
Теорема 2 доказана. П Другую форму теоремы 2 читатель найдет в $5.5. 3. Приведенные выше примеры 1, 2 показывают, что без дополнительных условий вида (15) теорема 2, вообще говоря, неверна. Однако, если (2)— многогранное множество (пример 1.8), то, оказывается, существование седловой точки функции Лагранжа выпуклой задачи (1), (2) можно доказать без каких-либо дополнительных условий. Это мы уже показали для общей задачи линейного программирования — см.
теорему 3.5.5. Теперь рассмотрим более общий случай, ие предполагая линейности целевой функции. Будем пользоваться следующим представлением многогранного множества Х=(хЕЕ": х~Хд, д(х)=(ас,х) — Ьт<0, т'=1,...,т; д (х) = (ас,х) — Ь, = О, 4 = тп + 1,..., з), (18) где Х, в свою очередь, является многогранным множеством н задается в виде: Хд = (х Е Е": (д„х) < г„т' = 1,..., р; (дс, х) = гс, т' = р + 1,, д), ат, д,. е Е" — заданные векторы, Ьс, г! — заданные числа. В частности, здесь возможно Х = Е", Хд — — Е", Х =(х=(х',..., х"): х! >О, 4 Е 1), 1 — некоторое подмножество номеров (1,..., п); Х =(х=(х',..., х"): стс < х' < < СУо т' =1,..., п), ссс, сУ, — заданные величины, ст! < Д, пРичем некотоРые Для многограйного множества несложно дать полное описание всех возможных направлений в любой его точке (определение 2.3).
Л е м м а 3. Множество возможных направлений множества (18) в любой его точке х„совпадает с конусом: К вЂ” К(**) — (е Е Е": е~О, (ат, е) <О, т Е 1,, (ас, е)=0, с=та+1,..., и, (дс, е) < О, 4 Е 1,", (с1„е) = О, т = р+ 1,..., г) (1о) где 1," = (т; 1 < т < тп, (ас, х,) = 6,.), 1; = (,'; 1 «,' , (,1 ) Доказательство. Пусть е =(е',..., е") ф.Π— произвольное возможное направление множества (18) в точке х,. Согласно определению 2.3 тогда существует такое число 4д > О, что х = х, + се Е Х или (ас, х,+ Ье) < Ьс, т=1,..., тп; (ат, х„+Ье)=Ьс, т'=та+1, ! г; (дс, х,+4е) < гт, 4=1,..., р; (йс, х,+се) = гс, т'=р+ 1,..., д,' (20) пои всех с, 0 < 1 < 1д. С учетом того, что х, Е Х и определения множеств 1, 1," активных индексов точки х, из (20), сразу получаем е Е К, Верно и й 9.
ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 223 (23) а равенство (22) можем переписать в виде 1'(х,) + 2 Л,*.а! = — 2,' Р,. 'д! — 2 Рйтс(с. (24) ' =. т -!- ! задаче (1), (18) такая: Ь,), хЕ Хд! Л ЕАд. „) > (1'(х„), х — х,), х ч Х (теореие рт > О, с ~ 1*, и равенство (24), *- ! д с! Функции Лагранжа в рассматриваемой в Е(х, Л) = 1(х) + 2 Лс((ас, х)— ! Тогда, используя неравенство 1!(х) — 1(х ма 2.2), определение множества 1,*, услов для каждого х е Х получаем 1, л г.(х, Л*) — Е(х., Л*) =~(х) — У(х„)+ ЕЛ:(а; х — х.) ~> с=.
! >(у(.)+~Л,*.ас, — х„)= — '7,рт(д! * — .) '=! т сду (д х х) = — 2 Р'((с(„х) — тс) >О, !=те! ! д т! Е(х„Л )<Е(х,Л*) ух~Хд. или обратное: если е е К, то е — возможное направление в точке х,. В самом деле, пусть е Е К. Тогда для 4 ~ 1; имеем (ас, х, + 4е) = Ьс+ 4(ат, е) < 6! при всех С > О, а если 4 ср 1,*, 1 < 4 < тп, то (ас, х,) < 6! и найдется такое 4д > О, что (ас, х,+ бе) < Ь! при 0 < 6 < сд. Если та+1 < 4 < з, то (ас, х„+ бе) = 6! при всех 4.
Аналогично, взяв при необходимости 4д > 0 еще меньшим, убедимся, что выполняются и остальные соотношения (18), так что х, + ~е Е Х, 0< с < ~ . Лемма 3 доказана. О Теорема 3. Пусть множество решений Х. задачи (1),(18) непусто, Пусть 1(х) выпукла на Х и дифференцируема в точке х, Е Х,. Тогда существуют множители Лагранжа Л" = (Л*„..., Л,*) е А = (Л = =(Л„..., Л,)ЕЕ'! Л, >О,, Л >О), такие, что пара(хэ, Л*) образует седловую точку функции Лагранжа задачи (1), (18). Доказательство. Согласно теореме 2.3 для того, чтобы х„е Х„ необходимо и достаточно выполнения неравенства (т"'(х,), х — х,) >О !УхЕХ (21) Возьмем любое е Е К.
Тогда по лемме 3 х = х, + бе Е Х, 0 < Ь < 4д, 4д > О. Подставим такую точку х в (21). Получим: (1'(х,), е) Ь > 0 или (1'(х,), е), > 0 при всех е Е К. По теореме Фаркаша 3.5.8 тогда найдутся числа Л;. > О, ~'(х„) = — 2,' Л,*. а,. — ~ ' Л,*. а! — ~ р,,. 'д! — ~,' р,*. д! (22) сдс, с=т.т! сду =рт! Если доопределим Л,*. = 0 при т е (1,..., тп) ~ 1,*, то получим точку Л' = = (Л*„..., Л;) е А,. Отсюда, учитывая определение множества 1,* и условие х„е Х, С Х, имеем Л,*((ас, х,) — Ьс) = Л,"дт(х,) = О, т = 1, ., г, Гк 4.
ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 224 'ьЗ"", н, ьа у(х) зх Е Х, +со Гх Е Хь ~ Х. 3 Х,П. Взииьзз Отсюда и из (23) с помощью леммы 1 заключаем, что (х., Л*) — седлоаая точка функции Лагранжа. Теорема 3 доказана. П 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, хеХ=(хеЕ": Ах=Ь1, 2 ПЗ и где А — матрица размера зп х и, Ь е Е, г — произвольная точка из Е, Согласно теореме 4.1 эта задача имеет и притом единственное решение х, =Р (г) Уг Е Е". Функция Лагранжа этой задачи Т (х, Л) = -~х — г1~+ + (Л, Ах — Ь) = -(х — г)~+ (х, А Л) — (Ь, Л). По теореме 3 функция 5 (х, Л) имеет седлоаую точку (х„Л") е Е" х Е и условия (6), (7) приводят к системе 5,(х„, Л) = (х, — г) + АтЛ = О, Ах. = Ь. Отсюда для проекции х„=Р (г) точки г на множество Х получаем представление х, = г — АтЛ, где Л вЂ” произвольное решение системы линейных алгебраических уравнений ААтЛ = Ах — Ь.
Если квадратная матрица ААт неаырожденная, то получаем уже известную нам формулу для проекции из примера 4.3. 4. Наконец, приведем еще один вариант теоремы Куна — Таккера. Т е о р е м а 4. Пусть в задаче (1), (2) Хь — многогранное множество из Е", функции г(х), д.(х), з =1,..., зп, выпуклы на открытом выпуклом множестве Иг, содеджаЩем Хь, д,(х) = (аз, х) — Ь', з = зп+ 1,..., г; существует гпочка х е Х такая, что дз(х) <О, з =1,..., т,; множество Х.
решений задачи (1), (2) непусто. Тогда для каждой точки х, Е Е Х„существуют множители Лагранжа Л" = (Л"„..., Л;) Е Л = (Л Е Е'. Л, > О,..., Л„> 01 такие, что пара (х„, Л*) образует сгдловую точку функции Лагранжа (3). До к а з а т ел ь с та о проведем, пользуясь приемом, изложенным а (2391.
Заметим, что каждая точка х, Е Х, является решением задачи ,г(х) — !зп1, хЕ Х=(хЕГь: дз(х) <О, з =1,..., т), где Г = (хе Х,: д (х) =О, з = т+1,..., г). Согласно теореме 2 и этой задаче функция Лагранжа Ь!(х и) = у(х)+ 2 и д (х), х Е Гь, и = (и',..., и ) > 0 имеет седлоаую точку (х„и"), т. е. '=! * * 5 !(х„и*) ~< 5 !(х, и") !Ух Е Гь,' и,.
'д (х ) = О, з = 1,..., зп; и* > О. $9. ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 225 Отсюда следует, что х„яаляется решением задачи й!(.ти*) — !зп1, х ЕГх Функция Лагранжа Гз(х,о)=Е!(х,зз*)+ 2,' о,дз(х), хЕХь, о ЕЕ' з=п +! последней задачи а силу теоремы 3 и замечания 2 к ней имеет седлоаую точку (х„ о*), что, согласно лемме 1, означает: Е,(х„о") < Ьз(х, о') !Ух Е Хь; о'.д (х.) =О, з = т+ 1,, г. Положим Л =(и, о), Л' = (и*, о*). Функция Лагранжа задачи (1), (2) тогда представима а виде Е(х Л)=У(х)+ 2,' Лзд(х) = Ь!(х и)+ 2,' о д (х), з= э! х ЕХь, Л ЕЛь. Из предыдущих рассуждений следует, что .5(х„, Л') = Т !(х„и')+ ) , 'о д (х ) = Ез(х„о) < Х з(х, о) = з= +! = Г !(х, и*) + 2; о,'д,(х) =- з (х, Л*) з!х Е Хю +! зз,*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
