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