Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач (1050553), страница 11
Текст из файла (страница 11)
Поскольку нз выпуклости функции ) не следует, вообще говоря, выпуклость функции — 1, то существенно, что (з) — задача не максимизации, а минимизации. 3 Точка х называется допустимой в (з), если хенА н ~;(х) <О, 1=1,..., т. Л ем м а. Пусть Х вЂ” нормированное пространство. В выпуклой задаче локальный минимум является и глобальным. <! Пусть хен!осш!пз.
Это означает, что существует окрестность со точки х, такая, что — ьь<1о(2) <1о(х) для любой допустимой точки хенМ. Возьмем пронзвольную допустимую точку х. Тогда прн достаточно малом а)0 вектор х=(1 — а)х+ +акын«! н является допустимым. Следовательно, по неравенству Иенсена (п. 1.5.1) го(х) <)о(х)-~ (1 — со)!о(х) +сс!(х), откуда о(х) <Ро(х). Г> оэтому в дальнейшем в выпуклых задачах, говоря «минимум», имеем в виду абсолютный минимум.
2.3.3. Теорема Куна — Таккера. Пусть Х вЂ” линейное пространство, 1иХ вЂ” Ж, 1=О, 1,, т, — выпуклые функции на Х, А — выпуклое подмножество Х. 1, Тогда если 2 — решение задачи выпуклого программирования, то найдется ненулевой вектор множителей Лагранжа Л= = (Ло, Ль, Л~), такой, что для функции Лагранжа ' (х, Л) = =~ ЛА(х) выполняются: о о а) принцип минимума для функции Лагранжа ш(п.У(х, Л)=.У(х, Л); «ел б) условие дополняющей нежесгкости Л4(х) =О, 1=1,..., и; в) условие неотрицательности Л;~0, 1=0, 1,..., т. 2 'Если ЛьФО, то условия а) — в) достаточны для того, чтобы допустимая точка х была решением задачи. 3.
Для того чтобы ЛьчьО, достаточно выполнения условия Слейтера, т. е. существования точки хенА, для которой 1;(х)< <О; 1=1,..., пт. <! Пусть х — решение задачи. Не ограничивая общности считаем, что (ь(Х) =0 — иначе введем новую функцию !ь(х)= =!ь(х) — !ь(х). Положим В=(Ь=(Ьм Ь„..., Ь.,)я)!'"+'~НхепА:Цх)<Ьь 1=0, 1,...,т). (1) А)  — непустое выпуклое множество. Действительно„ й~'"+'~В, т. е. любой вектор с неотрицательными компонента- мн принадлежит В, нбо в (1) можно положить х=х. Докажем его выпуклость, Пусть Ь н Ь' принадлежат В, 0<а<1, х н х'— такие элементы нз А, что (в соответствии с (1)) ~;(х)<Ьь.
1;(х')<Ь, 1=0, 1,...,т, Положим х =ах+(1 — и)х', Тогда х ~А, поскольку А — выпукло, а ввиду выпуклости функций ~;,1=0, 1,,т, !г (х,.) = ! г ( ах+ (1 — а) х') <сс~; (х) + (1 — а) 1г (х') <аЬ;+ (1 — а) Ь, т. е. точка аЬ+ (1 — а) Ь'енВ. Обозначим С=(с= (со, О,, 0) ~Вы+' !со<0). Б) С вЂ” непустое выпуклое множество н СПВ=Я.
Дейст- вительно, если существовала точка с= (со, О,..., 0), со<0, при- надлежащая В, то ввиду определения (1) отсюда следовало бы, что имеется элемент х~А, для которого выполняются неравен- ства: !ь(х) <со<0, 1~(х) ~0, 1=1, ..., т. Но из этих неравенств следует, что х не решение задачи.
Значит СПВ=И. По первой теореме отделимости в конечномерном случае (п. 1.2.2) множества В и С можно отделить, т. е. существует вектор Л= (Ль, Ль..., Л ) ФО, для которого !и! ~~ Л,Ь; ~~зпр,) Л,с,. (2) ьев ь пес ь ~ ЛЬ,>0 УЬенВ. о (3) 49 Поскольку 0 ен В, то нз (2) 0>зпр~~'„Л,с;=зпрЛ,с . Отсюда Л,>0 ~ее ь,сс н, значит зпрЛ,с =О. Тогда неравенство (2) перепишется в следуюсес щем виде: В) Множители Ль 1=0, ..., и, удовлетворяют условиям не.: е)трнцательности.
Действительно, так как мы уже говорили, что любой вектор с неотрицательными компонентами принадлежит В, то вектор (О,...,О, 1, 0,...,0)енВ, где единица стоит на чм месте. Подставив эту точку в (3), получим, что Л)~0. Г) Множители Л), )=1,, т, удовлетворяют условиям до-,! полняющей нежесткостя, Еслн ))(х) =О, то равенство Л)))(х) = =0 тривиально. Пусть )))(х) ~0 для некоторого ), тогда ))(х)» <О. Точка (0...,0, 1)(х), 0,,0)енВ, где число ))(х) стоит на )чм месте (достаточно взять точку х в качестве х в (1)).
Подставив эту точку в (3), получим что Л)1)(х) ЪО н, значит ЛжО. Но было уже доказано в п. В, что Л)ъО. Поэтому Л)=0 з! Л)()(х) =О. Д) В точке х выполнен принцип минимума. Возьмем хенА, тогда точка ()е(х), ))(х),...,)' (х)) енВ. Подставив эту точку в . ' (3), имеем, что ~ЛА(х) =.2'(х, Л) > О. а — — О Теперь если учесть равенство 1))(х) =0 н условия дополняаощей нежесткостя, то получим для любого х~А Я(х, Л)в О= ~ ЛД(х)=Я(х. Л).
а =-О Утверждение 1 теоремы доказано. Е) Докажем утверждение 2. Пусть ЛеФО. Полагаем Ла)=1. Тогда для любого допустимого х получаем в) ве! а) зе! 7,(х)) 1„(х)+ ~".ЛА(х)=Я(х, Л)~Л(х, Л)=1,(х)+ а=.! + ~', Л)1! (х) = (в(х), а=.! т. е. х — решение задачи. Ж) Докажем утверждение 3, Пусть выполнено условие Слейтера, но прн этом в утверждении 1 Л!)=О. Тогда сразу же получается противоречие: так как не все множители Лагранжа равны нулю, то .2(х, ц= ~"„Л)1,(х)(О=Я(х, Л), а=! в то время как вследствие а) 2'(х, Л) )Ю(х, Л). ~ 2.4. Гладкие задачи с ограничениями типа равенств и неравенств Рассмотрим задачу Еь(х)-»-Еп1; ~~(х)ч:О, Е= 1,...,»п, Р (х) =О, (зу где ЕпХ-»К, Е=О, 1,, т, Р:Х- У, Х, У вЂ” нормированные про- странства, Теорема.
Пусть в (з) Х и У вЂ” банаховы пространства (условие банаховости), ~~енЬР(х), Е=О, 1,...,т, РяИ(х) (условие гладкости) и 1т Р'(х) — замкнутое подпространство в. У (ослабленное условие регулярности). Тогда если й~уосш(пз, то существуют вектор Ленй +' и функционал у*яУ», не равные одновременно нулю и такие, что для функции Лагранжа зада- чи (з) Я(х, у', Л)=,~ ЛА(х)+(у', Р(х)) »=а выполнены следующие условия: а) стационарности: Я,(х, у', Л)=Ос=»,т Щ(х)+(Р'(х))'у*=0; » —..0 б) дополняющей нежесткости.
Л»Е';(х) =О, Е=1,..., »и; в) неотрицательности: Л;>О, 1=0, 1,...,гп. Мы сформулировали теорему в бесконечномерном случае ибо она будет использоваться нами в этой части (в $5). Доказательство опирается на два утверждения, относящиеся к функциональному анализу, которые доказываются у нас во. второй части (п. 7.2).
Для тех, кто пожелает продумать данную теорему в конечномерном варианте, нужно проанализировать те две леммы высшей алгебры, на которые следует ссылаться вместо лемм из п. 7.2. Отметим, что в формулировке теоремы и. 2.2.2 нет требования о замкнутости подпространства 1тР'(х). Это так потому что подпространство конечномерного пространства всегда замкнуто. Переходим к доказательству теоремы. сЕ Можно считать, что Еь(х) =О, иначе рассмотрим функцию 1»(х) =1»(х) — Еь(хд). Если )~(х)~0 при 1<Е<т, то отбросим это ограничение, поскольку для локального экстремума огРаничения 1ч(х) <О несущественны. Таким образом, можно.
51. считать, что условия дополняющей нежесткостн уже выполнены. А) Вырожденный случай. Если 1ш Р'(х) есть собственное надпространство У, то по лемме о нетривиальности аннулятора (и. 7.2) существует функционал у*гну', у*ФО, такой, что (у', у) 0 Уу~1ш Р'(х) е=»(уе, Р'(х)(х])=0 УхенХоо (Р'(х)) *у»=0. Остается положить Лз=О, 1'=О, 1,...,т, н приходим к утвержденню теоремы. Б) Пусть Р'(х) отображает Х на все..
У, т. е. 1тп Р'(2) = У. Положим для 0(й(т Аь=(х](1;"(Я), х)<0, 1=7т, й+1,..., т, Р'(х) 1х] =О). "Очевидно, что Асс:А1с... ~А Лемма 1 (основная). Если 2ен1осгп!пз, то А,— пустое леножество. лс2 Предположим противное, т. е. 'что АоФЯ. Тогда существует вектор ~~КегР'(х), для которого () (2), $)=рт<0, 1= =О, 1,...,т. По теореме Люстерннка* (и. 1.4.4) существуют атображенне г: 1 — а, а] — »Х (а>0) н число К, такие, что Р(х+Л$+г(Л)) =0 УЛ~( — а, а], (1); Цг(Л) !! к:К~~Р(2+~4) — Р(й) ]!=К~~ЛР'(хЩ+о(Л) ]!=о(Л). Прн малых Л>0 имеем для 1=0, 1,...,т, неравенства 1»(х+Ц+г(Л)) =(т(х)+Л(~ (х), с)+о(Л) =а()~+о(Л) <О.
(1т) Соотношения (1) н (1;), 1=1,...,т, означают, что прн ма- лых Л>0 элемент х+Л$+г(Л) допустимый в задаче (з). Но, прн этом неравенство (1е) противоречит тому, что хан ~1осш)п з. > ]> В) Лемма 2. Если А есть пустое множество, то для за- дачи (з) верен принцип Лагранжа, ее$ <<~ Поскольку А =(х,'(7 (х), х) <О, Р'(х) (х] =0) — пустое множество, то (7 (х), х) =0 для любого х е= КегР'(х), т. е. (х) ~(КегР'(х)) . Так как по лемме об аннуляторе ядра регу- .лярного оператора (и.
7.2) (КегР'(х))~=1ш(Р'(х))', то существует у* ~ У*, для которого 4 1 (х)+(Р'(х))" у'=О. Получили. условие стацнонарностн функции Лагранжа сс (х, у*, Л) с Ле=... =Л =О, Л =1. » В конечномерном случае — цо теореме о неявной функции. Таким образом, из п. Б) н В) вытекает, что либо принцип ,Лагранжа уже обоснован (А =Я), либо Нй, О~й(т: А«=Ы, А«+сФЯ.
' (2) Г) Лемма 3. Если выполнены соотношения (2), то х=О является решением следующей задачи: (~ь'(х), х>- 1п1; ((с'(х), х>(0, с=й+1,..., т, Р'(х) [х) =О. (з) <><> Предположим, что утверждение леммы неверно. Тогда ,найдется такой элемент т>, что (>с (х), т1>~(0, с Й+1,...,т,' Р'(х) 1с)) =О, но прн этом (~а'(х), т>>(0. Пусть $ — элемент, принадлежащий А«+ь т.
е. 5'(2), $>(0, с=>с+1, ..., т, дн(2)1ч)=0. Тогда прн малом е)0 элемент с)+е$ принадлежит А„в противоречии с (2). г. г. Д) Завершение доказательства. Применим к задаче (з) теорему Куна — Таккера (п. 2.3.3), учтя прн этом, что условие Слейтера для дтой задачи выполнено (нз-за непустоты Аь«.с). По этой теореме найдутся' неотрицательные числа )с«='1, За+с...,>с, такие, что для функции Лагранжа задачи (з) -~(х М=,)'.,"с(сс (х), х) в точке х=О выполнен принцип мисанм ума: ппп 2(х, Л)= '6(х, Х)=0. «як«се с«с Из последнего соотношения вытекает, что Я(х, >с)= ( Е сс1с'(х).х) =0 для любого хенКегР'(х), т. е. Б « Е Р~сРс'(х) ен (Кег Е'(х))".. с Поскольку по лемме об аннуляторе ядра регулярного оператора (КегР'(х))с=1ш(Р'(х))*, существует у*ену*, для кото1сого 7>Д'(х)+(Р'(х)) у =О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
