Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 58
Текст из файла (страница 58)
е. множество П имеет вид П=(иыП,: у<(и)<0, <=1, ..., лс). (12) Определение 2. Множество (12) называют регулярным, если существует точка й <в П такая, что у, (й) < О, ..., у. (й) < О. (13) Коли П, — выпуклое множество, функции у<(и) выпуклы па П„то вместо (13) достаточно потребовать для каждого $ существования точки й,ся П такой, что у<(й<)<0 (1=1, ..., и). Тогда в качестве й из (13) можно взять и = ~,' аси<, сс<) О, <=1 а<+ ас+...+с< = 1, поскольку й ~ П, и в силу неравенства (2.2) уг(и)~ ~'„асу;(ис)(а;уг(и;)(О (1=1, ..., т).
Условие <с Г (13) часто называют условием Слейтера. Для наших целей подошло бы и несколько иное более общее, чем (13), определение регулярного множества: множество (12) назовем регулярным, если для любого вектора Л* = =(Л„..., Л ) МО (Л„)0, ..., Л )0) существует такая точка й = й(Лв), что е 9! ТЕОРЕМА КРНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 339 но. Пусть л<ножество Ув точек минимума функции Л(и) на множестве (12) непусто.
Тогда для каждой точки иоееУо необ- ходимо существуют множители Лагранжа Ло = (Л„..., Л,„) <и< я Ао = (Л ее Е: Л<>0,..., Л >О! такие, что пара (ио, Ло) образует седловую точку функции Лагранжа на множест- ве У< ХЛ,. Доказательство. В пространстве Е +' переменных а= =(а„а„.. и а ) введем множества А =(а = (а„а„..., а„) <и Е"+': а, > л (и), а, > у<(и), ..., а ) у„(и), аж Уо), В=[Ь=(ьо,ь„...,ь ) Е +: Ь <Уо, Ь,<О,„„Ь <О). Покажем, что А и В не имеют общих точек. В самом деле, пусть а <и А.
Тогда найдется точка и он У, такая, что а, > л(и), а,>д,(и), ..., а„>д„(и). Возможно, что ит <<. Тогда аоЪ ))У(и)>~Хо и заведомо аФ В. Если же ион У<~У, то найдется номер ! (1(<( т) такой, что д<(и)>0. Тогда а<>у<(и)> 0 и снова а Ф В. Итак, А П В = О. Далее, нетрудно видеть, что А и  — выпуклые множества. Покажем, например, что А выпукло. Пусть а, с — две произвольные точки из А. Тогда существуют точки и, о »н У, такие, что а< пп л (и), со > г (У) < а< Р- у<(и), с» у<(У) (! = 1, и т) ° Возьмем произвольное аег [О, 11 и положим а, = па+(1 — а)с, и„= аи+(1 — а)о. Из выпуклости Уо следует и ои Уо. Далее, из выпуклости функций л (и), у<(и) имеем л (и„) ( ал (и) + (1 — а) л (о) ( с<а, + (1 — а) с„ у (и )~ ау (и)+(1 — со)у<(о)(<ха<+(1 — а)сь 1=1, ..., т.
Это означает, что а„<ЕА. Выпуклость А доказана. Аналогично доказывается выпуклость В. В силу теоремы 5.2 тогда существует гнперплоскость <с, а)= с нормальным вектором с = (Ло, Л<, ..., Л, ) ~ О, отделяющая А и В, а также А я В =(Ь = (Ьо, Ь„..., Ь„) ен Е~~~: Ьо((зоо Ь, < О, ..., Ь < 0). Это значит, что п» »и (с, Ь) = ~ Л;Ь<(у((с, а) = ~~З„Л<ао '<!'вен А, ЬЕЕВ, (15) <=о <=о Заметим, что у = (ло, О, ..., 0) ее А П В. В самом деле, возьмем какую-либо точку иоееУо.
Тогда < (и ) =Хо, у»(и )<О (г = 1,..., т), что означает у ~ А. Включение у жВ очевидно. Тогда по теореме 5.2 величина у яз (15) равна у = (с, у) = Л,го„ и (15) можно переписать в виде и» пъ ЛоЬо+ Х Л'Ь<(ЛоУо--.Лоао+ Х Л<а; 9<ае=А, ЬееВ. (16) 240 ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА ИГЛ. В Возьмем точку Ь =(Х вЂ” 1, О, ..., 0) ы В.
Из левого неравенства (16) получим Ль (Хе — 1)<Ло Хю откуда Л, ЪО. Далее, беря Ь= (Хе, О,..., О, — 1, О,..., 0), из левого неравенства (16) имеем ЛзХе — «й~(«оХе т. е. Л' ~)0 (г = 1,..., т). Таким обраь 1 А зом, показано, что Л* = (Л„..., Л ) > О, Л, ) О. Далее, возьмем произвольную точку ие ~ П . Тогда а = = (Х(ие) = Хе, О,..., О, рд(ие), О,..., 0) ~ А П В. Подставляя эту точку в левое и правое неравенства (16), получаем Л,Хе + + Л;дз(ие)<Л,Х„<Л,Хе+Л;уь(и. ), откуда Льд;(и )<О<;д;(и„) или Л;д(и ) = 0 (1=-1,..., и). Равенства (7) доказаны.
Покажем, что Л,)0. В самом деле, в (16) подставим а = =(Х(й), д,(и), ..., д (й))шА, где й взято из (13) или (14). Получим Л,Х < Л,Х (и) + ~ Л; дз (и). Допустим, что Л, = — О. г=ь Поскольку не все Л,' (1= О, 1,..., и) равны нулю, то Л*+О. е Тогда из предыдущего неравенства при Ль = 0 с учетом усло- вия (13) или (14) имеем 0(~ Д Л;дь(и)<0. Полученное протиь=г воречие показывает, что Ль ) О. Неравенство (16) и все после- дующие рассуждения сохраняют силу, если (16) поделить на е ь Ле ) О. Это значит, что в (16) можно принять Ль = 1. Наконец, возьмем произвольную точку и ~н Ь н Тогда а = (Х(и), у,(и), ..., у„(и))~А. Подставим зту точку в правое неравенство (16). С учетом того, что Ль = 1, получим Хе < ((Х(и)+ ~ Л;уь(и) = Е(и, Л*) (и~ В,).
Но в силу (7) Хе = с=т =Е(ие, Л*) при любом выборе и„енПе. Отсюда и из предыду- щего неравенства следует условие (6). Согласно лемме 1 тогда (ие, Л*) — седловая точка. 3. Приведенный выше пример 1 показывает, что без допол- нительного требования регулярности множества теорема 2, во- обще говоря, неверна. Однако если (2) — многогранное множест- во, то, оказывается, теорема о существовании седловоп точки будет верна беа каких-либо дополнительных условий типа усло- вий регулярности. Важную роль при установлении Этого факта, а также во многих других вопросах выпуклого анализа играет следующая теорема, известная в литературе под названием теоремы Фаркаша.
Те орем а 3. 77усть дано множество К =(е я Е": <со е>< О, 1= 1, ..., и; <с„е>< О, 1= и+ 1, ..., р; <сь е>= О, 1 = р+ 1, ..., в), (17) еде с„..., с, — некоторые векторы из Е". Тогда для того чтобы 9 91 ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 241 некоторый вектор сж Е" удовлетворял неравенству (с, е))0 1/вен К, (18) необходимо и достаточно, чтобы существовали такие числа Лвв Лв (Лв > Ов ° .в Лр ~ >0) ~ что с = — Лвс —...
— Л с,. (19) Нетрудно видеть, что К вЂ” конус с вершиной в нуле, а всякий вектор с, удовлетворяющий условию (18), принадлежит двойственному конусу К* (см. определения 5.4, 5.5). Поэтому теорему Фаркаша можно переформулировать на языке конусов следующим образом. Теорема 3. Пусть К вЂ” конус, определенный условиями (17). Тозда двойственньвй ему конус имеет вид в К*= )сея Е: с = — ~ Лзс;, Л,)0,..., Лр)0 .
(19) 1=1 Заметим, что в (17) не исключаются случаи, когда какие- либо виды ограничений (ограничения типа нестрогого или строгого неравенства, или типа равенства) отсутствуют, т. е. возможно т=О при т=р, или р=з, или т=р=О, или т=О, р=з или т=р=з. Для доказательства теоремы 3 нам понадобится Лемма 3. Пусть а„..., а„— некоторое конечное мнозеество векторов из Е". Тозда ае=Е: а= ~~'„ивав, ив)0, 1=1,..., р 1=1 есть выпукльвй замкнутый конус р Доказательство. Если а~(в, то Ла= ~Лиав(Лив)0,.
1=1 1= 1, ..., р) при любом Л ) О. Это значит, что в,в — конус. р Далее, пусть а, Ь вЂ” две произвольные точки на (7, т. е. а = ~изин 1=1 р Ь = ~', р;а; (свв ~ О, рв ~ О, 1 = 1,..., р). Тогда для всех и ~ (О, 1) 1=1 р иа + (1 — и) Ь = ~~~ (иив + (1 — и) )11) а;, в=1 ииз+(1 — и))11)0, 1=1, ..., р, так что (в — выпуклый конус. Кстати, тогда из а, Ь вн в,в следует а+ Ь ~ч. В самом деле, в силу выпуклости конуса (/ имеем а+ Ь = и (а/и)+ (1 — и) (Ы(1 — и) ) ж ч при всех и (О < и < 1), поскольку а/и, Ы(1 — и)ви ф. элкмкнты выптклого анализа ~ГЛ.
1 Замкнутость 1) докаягем индукцией по числу образующих лекторов а„..., аР. При р=1 (1=(а1иЕ": а=па„сг>0)— полупрямая (луч) — замкнутое множество. Пусть известно, что конус с любыми р — 1 образующими замкнут. Покажем, что тогда конус 1, с р образующими а„..., аР также замкнут.
Рассмотрим два случая. 1. Конус С) наряду с векторами ао ..., аа содержит также и р векторы — а„..., — ат. Тогда наряду с точками а = ~ а1аг 1=1 Ьиг)0, 1= 1,..., р) выпуклый конус () содержпт все точки Ь= )~ р1( — а1) (р1)0, 1=1, ..., р), а также точки а+ Ь. По1=1 кажем, что в рассматриваемом случае (1 является подпространством (линейной оболочкой), натянутым на векторы а„..., а,.
р В самом деле, пусть д= 2~ уга;, где у, (1=1, ..., р) — про1=1 невольные числа. Положим еп = шах(0; у~), (), = шах(0; — (1). р р Тогда (, = а1 — р1 (1= 1, ..., р). Позтомуд= ~уга1= ~ агаг+ 1=1 1=1 Р + У ()1( — а1)~Ч при всех действительных т, (1=1, ..., р). 1=1 Таклм образом, (1 — подпространство, натянутое на векторы а„..., аР, размерность которого не превышает числа гаш(р; и). По в конечномерном пространстве Е" любое подпространство замкнуто 1931. Следовательно, () замкнут. 2.
Хотя бы один из векторов — а„..., — аз не принадлежит Пусть для определенности — а„Ф (). Обозначим Чр-1 = р — 1 = )Ьен Е": Ь = ~~агап а1)~0, 1= 1, ..., р — 1~ — это конус, по1=1 рожденный векторами а„..., аР 1. По предполо1кению индукции Р— 1 конус ЧР 1 замкнут. Далее,из представления а = ~ а1аг + акр (а1»0, 1= 1, ..., р — 1, я)0 следует, что ч1=ч11-~+ааю а~О. (20) Пусть д — какая-либо предельная точка множества ч.
Тогда существует последовательность (и' )1и ф, сходящаяся к И. Из (20) следует существование Ь„1яЧР 1 и чисел р ~ 0 таких, что д„= Ь + р ае (т = 1, 2, ...). Покажем, что (р„) ограничена сверху. Допустим, что (р ) пе ограничена сверху. Тогда существует подпоследовательность (р 1): <„>. Поскольку (д ), как сходящаяся последовательность, ограничена, то д „/р,а„-~ 0 при З 9] ТЕОРЕМА КУНА — ТАНКЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 243 й-э со.
А тогда (Ь А(р д — — (<< Др д) — ар) имеетпределпри <<в , равный — аю Но так как (Ь „/(< 1) анар 1, а конус замкнут, то предел †будет принадлежать К, < Из (20) при <х = 0 следует Ке < — ч, так что — аг ш (>. Получили противоречие с рассматриваемым случаем. Это означает, что 0» д ~ сопзс (т= 1, 2, ...).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
