Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 57
Текст из файла (страница 57)
Доказать, что тогда необходимо (Н'а (а„, Хе) Ь, Ь) > 0 при всех Р, удовлетворяющих условиям (5) — (7), и всех Ь зв Н (и,„) = (Ь ш Е": (У' (и„), Ь) (О; (у,. (ае), Ь)(0, геи 1е =(1: 1(1((т, у,. (ие) =0; (г,, (а ), Ь) =О, 1 = т+1, ..., э) ([21, с. 143)). 7. Пусть в задаче (1), (2) фувкции 7(а), у~(э), ..., у,(п) дважды дпфферепцируемы в точке а„ев У, пусть для некоторого Ьэ выполвевы условия (5) — (7) и, кролге того, (Н'аа(и„, Х*)Ь, Ь) >О для всех ненулевых Ьв К (ае) ПН(и„), где К(а„) — эзмыкэяие мвожества К (а ) =(Ь ж Е"; Ь4 Ь(а — ае), Х>0, аж Уз), Н(ие) опРеДелено в УпРажвевии 6. ТогДа иэ — точка строгого локального минймума в задаче (1), (2) ([21, с.
141)). $9. Теорема Куна — Таккера. Двойствеппая Задача 1. Перейдем к рассмотреиию условий оптимальности для задач выпуклого программироваппя. Под выпуклым программированием понимается раздел теории экстремальных задач, в котором изучаются задачи мииимиэации (или максимизации) выпуклых функций па выпуклых множествах. Точнее, под задачей выпуклого программирования понимается следующая задача: Х(и)- 1п(; и зи П, (1) Г = (и ш с7,: Е~(и) ( О, 1 = 1, ..., пэ; Кз(и)= О, 1 т+1, ..., г), (2) где (7, — заданное выпуклое множество иэ Е, функции Х(и), Е,(и), ..., д (и) определены и выпуклы па По а Е,(и)= = <а„и> — Ь' при 1= т+ 1, ..., г — линейные функции, Ь'— заданные числа, а,— заданные векторы иа Е".
Здесь пе исключаются возможности, когда отсутствуют либо ограничения т о«ткогкмя кунА — тАБКЕРА. Двоиствквная задача 235 б,(и)~0 типа неравенств (т=О), либо ограничения у;(и)=0 типа равенств (г = л«), либо оба эти вида ограничений (и = г = О, У «Х,). При сделанных предположениях по теореме 211 множество (2) выпукло. Важное место в теории выпуклого программирования занимает теорема о седловой точке функции Лаграня«а, известная в литературе под названием теоремы Куна — Таккера в честь американских математиков Куна и Таккера, впервые сформулировавших и доказавших некоторые варианты этой теоремы. Эта теорема дает необходимое и достаточное условие оптимальности в задаче (1), (2), т.
е. условие принадлежности той или иной точки множеству (Хо = (и ен П: Х (и) = ш1 Х (о) = Хо), оси и выражает собой правило множителей Лагранжа для регулярной задачи (1), (2). Для формулировки теоремы Куна — Таккера введем функцию Ь (и, Л) = Х (и) + ~ Л«у«(и), (3) называемую в отличие от (8.4) регулярной б)ункиией Лагранлса задачи (1), (2), где и~ П„а переменные Л=(Ли ..., Л.) принадлежат множеству Ло=(Л=(Ли ".ч Л,)шЕ'. Л«~~0, ..., Л ~~0). (4) Определение 1. Точку (ио, Л*)~«Хо Х Л, называют седловой точкой функции Лагранжа (3), если Х(и, Л)<Ь(ио, Ло)<А(и, Л*) ЧигнУо, ЛяЛо.
(5) Прежде чем переходить к выяснению связи между седловой точкой функции Лагранжа и решением задачи (1), (2), дадим другую равносильную (5) формулировку для седловой точки. Л е м и а 1. Для того чтобы точка (и„, Ло) о= По Х Ло была седловой точкой у7унк««ии Лагранлса, необходимо и достаточно, чтобы выполнялись следующие условия: Ь(ио, Л*)<Х (и, Лг) 1г'иЯ Уо, (6) Л7у«(иг) = О, « = 1,..., г, и„е= (Х. (7) Доказательство. Необходимость. Пусть (ио, Л*)ен ен «Хо Х Л, — седловая точка.
Тогда условие (6) представляет собой правое неравенство (5). Остается получить условия (7). Для этого перепишем левое неравенство (5) с учетом конкретного вида (3) функции Лагранжа: Х(ив) + „'~~~ Л«у«(ио)<Х(и ) + ~ Л«у«(ио) ЮенЛо. (8) «« «-т элвмзнты ВыпуклОГО АнАлизА 236 ИГЛ. 4 Отсюда имеем (Л1 1Л1) А1 (Иэ) ) )0 туЛ ен Лэ 1=1 (9) (Л; — Л;) л1 (иа) = 0 (10) прн всех 1= т+ 1, ..., г и всех тех 1 (1 <1< и), для которых л1(и„) =О.
Если л1(иэ)(0 прн некотором 1 (1<1'<т), то из равенства (7) следует, что Л;=О. Поэтому(Л1 — Л,) д1(иэ)= = — Л1д1 (и )>О для всех Л >О (1<1< т), для которых д1(иэ)<.0. Складывая полученные неравенства с (10), будем иметь ~~ (Л1 — Л1) д1 (иэ) > 0 для всех Л 1и Л,. Отсюда 1=1 в 1 ~1 Ла1(иэ)- Х Л1д1(иэ) прн всех ЛыЛ,. Добавляя к обеим 1=1 1=1 частям этого неравенства Х(и )„придем к неравенству (8), представляющему собой левое неравенство (5).
Покажем, что и„ен 51. Возьмем точку Л (Л„..., Л.), где Л1 = Л1+ 1 при некотором 1 (1 <1 < т) и Л; = Л; при всех остальных 1=1, ..., з (1чь(). Из определения (4) множества Л, и из того, что Л*1иЛ„следует, что выбранная точка Л1нЛ,. Иа (9) при таком Л получим ( — 1)д1(и„)>0, т. е. д;(и„)(0 при всех 1=1, ..., т. Далее, пусть Л =(Л„..., Л.) — точка с координатами Л; = = Л; + д;(и„) при некотором 1 (и+1 <1< г) и Л; = Л1 при всех 1=1, ..., з (1чьу).
Ясно, что Л шЛ,. Поэтому иа (9) имеем — )д(и ) )'>О, т. е. д(и„.) = 0 при всех 1= т+1, ..., ю Таким образом, докааапо, что иэ ен 7У. Из того, что Л1(и ) = 0 при 1= т+ 1, ..., з, следует, что Л'." 1з1(ПА) = 0 (1 = т + 1, ..., У) Остается получить равенства (7) при 1=1, ..., т. Возьмем точку Л=(Л„..., Л,) с координатами Л1=0 при некотором у (1<у'< т) и Л1 = Л; при всех остальных 1= 1, ..., з (1Фу). Такая точка принадлежит Л„поэтому нз (9) получим 0<Л1'д;(иэ). Но Л1>0, 61(иэ)((0 при 1=1, ..., и, поэтому последнее неравенство возможно лишь при Л1д;(и„) = 0 (7 = 1, ..., т). Все соотношения (6), (7) получены.
Достаточность. Пусть для некоторой точки (иэ, Л")ен е= 5', Х 1Л„выполнены соотношения (6), (7). Покажем, что тогда (иэ, Л*) — седловая точка. Из (6) следует правое неравенство (5). Остается доказать левое неравенство (5). По условию (7) и„~ 51, т. е. Л1 (и„) ( 0 (1= 1,..., т), д (и ) = О (1 = т + 1,... ..., З). Тогда ем теоРемА кунА — тАккеРА. двойственнАя зАдАчА 2з7 Если сделать дополнительные предположения о выпуклости и гладкости задачи (1), (2), то лемму 1 можно переформулировать в следующей так называемой дифференциальной форме. Лемма 2. Пусть (1), (2) представляет собой задачу выпуклого программирования и Х(и), у,(и), ..., у„(и)» С'(П,). Тогда для того чтобы точка (и, )»")~ХХ ХЛ, была седлоеой точкой функции Лагранжа, необходимо и достаточно, чтобы (Х,„(и„„Л*), и — и » = Х'(и„) + ~,' Х;у»(и ), и — ив ))0»»»иве ХХ», (6') ).,'дг(и.
) = О, $ =1,..., з, и„ен(Х. (7') Доказательство. При сделанных предположениях функция Лагранжа (3) выпукла и дифференцируема по переменной и» П» при каждом А»Л». Поэтому условие (6) согласно теореме 2.3 равносильно условию (6'). Как видим, соотношения (6'), (7') напоминают нам условия (8.5) — (8.7) при А» = 1, а соотношениям (6), (7) соответствуют аналогичные (8.20) с 1»,=1. Зги аналогии подчеркивают тесную связь между правилом множителей Лагранжа иэ 3 8 и следующими ниже теоремами. Теперь выясним, как свяааны между собой седловая точка функции Лагранжа и решение задачи (1), (2). Теорема 1. Пусть(ив,)*)енП»ХЛ» — седловаяточкафункции Лагранжа.
Тогда иь вн П», Хв = Х(ив, Хв) = Х(и„), т. е. и„ является решением задачи (1), (2). Доказательство. Из условия(7) имеем ивен(Х и Х(ив, А*) = Х(и„). Тогда неравенство (6) перепишется в виде Х(и )( Х (и, )*) = Х(и) + «г )»»у»(и), и~ П». (11) »=» » В частности, (11) верно и для всех и»ХХ. Но ~'„Цд»(и)(0 »=» при и» ХХ, так как тогда у»(и)<0 и»ч )О при» =1,..., т, так что )чд» (и) ((0 (1 = 1, ..., т) и д,(и) = 0 при» = т+ 1, ... ..., з, так что Х,д,(и) = 0 (» = т+ 1, ..., г). Поэтому из (11) следует, что У(и„,)(Х(и, Л*)(Х(и) при всех и»ХХ, т. е.
иь е= с~,» ° Заметим, что теорема 1, как и лемма 1, доказаны беэ каких- либо ограничений на функции Х(и), у»(и) (1=1, ..., г) и на множество П»; в частности, никакие предположения о выпуклости, сделанные выше при формулировке задачи (1), (2), мы пока не использовали. 2. Возникает вопрос: во всякой ли задаче вида (1), (2) функция Лагранжа имеет седловую точку7 Ответ здесь, конечно, от- злвмвнты выпгклого анализа сгл. г рицательпый: если в задаче (1), (2) Пг = 8, то, как следует из теоремы 1, функция Лагранжа такой задачи пе может иметь седловую точку. Более того, даже в задачах выпуклого программирования (1), (2) с П„Ф 8 в общем случае нельзя ожидать, что фуякция Лагранжа будет иметь седловую точку.
Пример 1. Рассмотрим задачу из примера 8.6: г(и)= = — и- ш1 (и<и П (иыП,: у(и)=й<0)), где П,=(исиЕ<с 0 < и < а), 0 < а < . Здесь множество П, выпукло, фупкции 1(и), д(и) выпуклы па П,. Множество П состоит из одной точки и=О, так что Х. = г (0) = О, Пв =(О). Функция Лагранжа с (и, Л)= — и+Ли*, 0<и<а, Л~О, и~П, (Л*, д(и)) = ч", Л;дс(и)<0.
<=1 Существуют и другие определения регуляряости множеств вида (12), (2), используемые в теоремах Куна — Таккера [24, 41, 299]. Теорема 2. Пусть множество П, выпукло, Функции г'(и), у<(и) (с = 1, ..., ш) выпуклы на П„а множество (12) регуляр- (14) рассматриваемой задачи пе имеет седловой точки. Таким образом, для существования седловой точки на задачу (1), (2), кроме условий выпуклости, должны быть палоясопы какие-то дополпительпые ограничения. Начнем с рассмотрения случая, когда в (2) ограничения типа равенств отсутствуют (и = г), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
