В.М. Алексеев, В.М. Тихомиров, С.В. Фомин - Оптимальное управление (1979) (1155777), страница 10
Текст из файла (страница 10)
б! Мы увидим далее, что для очень большого числа задач общий замысел Лагранжа оказывается правильным, 1.3.3. Теорема Кума — Танкера, В этом пункте мы рассмотрим задачи выпуклого программирования, для которых идея Лагранжа приобретает наиболее завершенную форму, Этот класс задач стали изучать сравнительно недавно. Основы теории линейного (а это частный случай выпуклого) программирования были заложены в работе Л. В. Канторовича в 1939 г. Теорема Куна — Таккера— основной результат этого параграфа — была доказана в 1951 г. Рассмотрим следующую экстремальную задачу (задачу выпуклого програльяирования): (,(х) (п1, ~;(х)(0, 1=1,...,т, х~А, (1) где Х вЂ линейн пространство (не обязательно конечно- мерное), 1; †выпукл функции на Х, А †выпукл подмножество Х. Отметим, и это существенно, что (1) — это задача минимизации, а не йакснмизации.
Напомним, что множество С, лежащее в линейном пространстве называется выпуклым, если вместе с любыми двумя своими точками х и у оно содержит также и весь отрезок 1х, у] = (г ~ г = ах+ (1 — сь) у, 0 ч ' сс ( 11. Функция Х вЂ” К называется выпуклой, если для любых х и у ~ Х выполнено неравенство Иенссена )(ах+(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, ..., З, З ЛЮООЕ к ! Зги конусы не пересекаются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
