Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 21
Текст из файла (страница 21)
Расомотрим вопрос об неотделимости введенных конусов Кь Воспользуемся теоремой 1.3.5. Таи как 1лпКо= К", то условие б) этой теоремы выполняется автоматически. Поэтому конусы неотделимы тогда и только тогда, когда пересечение ш1Кь 1=1, ... ..., т, не пусто.
Но это, очевидно, эквивалентно совместности системы (1.16). Если теперь учесть, что К'; = ( — Лох,*: Ло ) 0) 1 !. линеннов пгогглммиговлепге 139 и определенпе 1.3.3 отделимости, то получаем, что система ИЛО) совместна тогда и толико тогда, когда равенство ИЛ7) невозможно. Теорема 1.10. Система неравенств (х,х;)~(0, г=1,...,т, (х, х*) <О совместна тогда и только тогда, когда не существует таких Л;~0, (=1, ..., т, что т + ~ Л,х,'=О.
(1.19) Доказательство. Очевидно, что система ИЛ8) не совместна тогда и только тогда, когда из системы И.15) следует, что произведение <х, хе> неотрицательно, т. е. когда хе~и К", где К вЂ” конус, определяемый системой ИЛ5). Но по теореме 1.4.9 в х*= — ~ Лгх1, Л;' эО, 1=1, ..., т, Легко видеть, что вопросы о разрепгнмости системы И.20) сводятся к исследованию аналогичных вопросов для системы (х, х; ) — и;хг ( О, 1 = 1, ..., т, — хе< О, в которой неизвестным является вектор (х, хс) ~в К"+'. т. е.
справедливо соотношение ИЛ9). Итак, система ИЛ8) несовместна тогда и только тогда, когда (1Л9) выполняется, что доказывает теорему. Т е о р е и а 1.11. Система И.15) имеет единственное решение х=О тогда и только тогда, когда для любого хе~я К" существуют такие Л~>0, что выполняется равенство ИЛ9). Это — элементарное следствие теоремы 1ЛО. Рассмотрим теперь неоднородные системы неравенств (х, х ) — иг((0, 1= 1, ..., т. (1.20) гл.
гк Выпукпон пгогглммиговлнив Т е о р е м а 1Л 2. Система (х,х;) — а»<0, »=1, ..., т, разрешима тогда и только тогда, когда не существует таких чисел Х;>О, г=1, ..., т, что й» не все равны нулю и ~ )г»х» = О, ~ Л»а» ( О, (1.22) Доказательство получается применением теоремы 1.9 к системе И.21) со знаками строгих неравенств. Т е о р е м а 1.13, Система И.20) совместна тогда и только тогда, когда не существует таких Х, > О, что ч"„)»х» = О, ~ч', Л»а» = — 1.
Доказательство получается прямым применением теоремы 1ЛО к системе И.21). Рассмотрим теперь вопрос о том, при каких условиях множество решений системы И.20) ограничено. Пусть К вЂ” конус, определяемый неравенствами ИЛ5). Если К содержит элементы х, отличные от нуля, то множество решений системы И.20) неограничено. В самом деле, если хо»нК, хочьО, и если х удовлетворяет системе И.20), то х+ рхо удовлетворяет системе И.20) прн всех р~ О. Обратно, если хь ) =1, ...,— решения системы И.20), !!х»!!-, то, выбирая из последовательности у»= =!)х»!! 'х, сходящуюся (без ограничения общности можно считать, что уг — уо, !!у,!! = 1), получаем аг (у„х») — — О, »=1,..., т.
Р» ~! Отсюда после перехода к пределу получаем систему неравенств (Уо» х;) «(О, г = 1,..., ог. Таким образом, уо»нК и уоФО. Итак, множество решений системы И.20) ограничено тогда н только тогда, когда К = (0). На основании утверждения теоремы 1Л1 убеждаемся в справедливости следующей теоремы.
4 ь линейнОе пРОГРАммиРОВАние 44! Теорема 1Л4. в(нохсество решений И.20) ограничено тогда и только тогда, когда для любого хвоей" существуют такие Х > О, что выполняется равенство ИЛ9). Т е о р е м а 1Л5. Пусть система И.20) несовместна. Тогда существует такая ее подсистема (х, х!) — а!(О, !Ен У, Тс(1, 2,..., т), которая также несовместна, а число элементов в множестве индексов Т не превосходит и+ 1.
Доказательство. Пусть система И.20) иеразрешнма. Тогда найдутся такие ) ~ О, что ~~.", Л!х,* =О, ~ ).!а! =- — 1. (1.23) Обозначим У=(й Х!)О, 1=1, ..., и). И.24) Если мощность множества У больше и+1, то векторы ь+! (х!, и!) ~ К +' линейно зависимы. Поэтому существуют такие пе все равные нулю (ь что ~ у!х,* = О, ~.", у;сс; = О. (1.25) е х !Ну Положим (л; ее = пип ~ — ': у; ) О . !Нх т! Тогда все числа )!=Х; — еь"(! неотрицательны и из соотношепий И.23) — И.25) следует ~).!х,'=О, ~),= — 1.
(1.26) ив ьяг Заметим, что в соответствии с выбором ее одна из величин Хь !~у, равна нулю, и поэтому в суммах И.26) не все слагаемые отличны от нуля. Исключая равные нулю слагаемые и повторяя указанную процедуру несколько раз, придем после конечного числа шагов к ситуации, когда в суммах И.26) будет не более и+1 отличных от нуля слагаемых. Взяв тогда в качестве 1 множество индексов, отвечающих ненулевым компонентам Хь получим на основании теоремы, 133;,что соот- 442 Гл.
1ч. Выпуклов пгогглммиговлнин ветствующая подсистема неравенств несовместна, что и доказывает теорему. Теорема 1 15 показывает, что система (1.20) совместна тогда п только тогда, когда разрешима любая ее подсистема из и+ 1 неравенств. з 2. Необходимые условия экстремума в выпуклом программировании Пусть хг — точка минимума функции )г(х) на множестве М.
Очевидно, что точка хг должна выделяться своими свойствами среди всех точек х ы М. Условия, которые в определенной степени характеризуют точку минимума, называются необходимыми условиями экстремума. Если минимизируемая функция и множество М выпуклы, то зти условия оказываются, как правило, и достаточными. Нижеследующие теоремы дают необходимые условия, форма которых варьируется в зависимости от степени детализации описания множества М. 1. Ограничения, заданные выпуклыми множествами. Пусть )(х) — собственная выпуклая функция, а хг— точка ее минимума во всем пространстве: ~(х) ~ у(хс), х ~н Х. Договоримся, что всюду в дальнейшем, если хг — точка минимума, то )(хг) ) — . Переписав неравенство для )(х) в виде У(х) — У(хг) > <х — хг, 0>, ОыХв, (2.1) получаем, что Оыд/(хг).
Таким образом, справедлива Теорема 2.1. Для того чтобы точка хг былаточкой минину а выпуклой функции 1(х) во всем пространстве, необходимо и достаточно, чтобы Оы д~(хв). Эта элементарная теорема в сочетании с доказанными ранее позволяет получить ряд новых результатов. Теорема 2.2. Пусть М вЂ” выпуклое множество и существует точка х1шМ, в которой выпуклая функция 1(х) непрерывна. Для того чтобы точка хг была точкой минимума ~(х) на множестве М, необходимо и достаточно, чтобы (2.2) Н(хг) ПХм(хв)+8 % 2. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА 143 где К„(х,) = соп(М вЂ” хо) = (х: хо + Хх ои М при малых А > О). Замечание. Так как конус Кн(хо) будет часто встречаться в атом параграфе, рекомендуем читателю вспомнить и.
4 $3 главы 1 и теоремы 1.3.6 — 1.3.9., Доказательство. Так как по определению (О, хеМ, 6 (х) М) = ~ то легко видеть, что нахождение минимума 1(х) на множестве М эквивалентно нахождению минимума функции 1(х)+6(х~М) во всем пространстве. По теореме 1?.ЗЗ субдифференциал функции 1(х) + 6ЫМ) равен сумме субдифференциалов функций 1(х) и 6(х~М). Но согласно формуле (11.3.25) справедливо равенство дб(хо) М) = Км(хо) (2.3) Таким образом, субдифференциал функции 1(х) + + 6(х~М) в точке хо равен д?(х ) — Км(хо).
Согласно теореме 2 1 для того, чтобы точка хо была точкой минимума функции 1(х)+6(х)М), необходимо и достаточно, чтобы О ~ д) (хо) Км (хо), что эквивалентно соотношению (2.2). Теорема доказана. Теорема 2.3. Лусть выполнены условия предыдуи)ей теоремы и М=М,ПМ П...()ММ где Мь 1= 1, ..., й,— выпуклые множества, причем ?пь М~ П 1п( Мз П... П 1Н1 М„1 П М„Ф И. Тогда для того, чтобы точка хо была точкой ми ма ?бункг)ии 1(х) на множестве М, необходимо и до таточ чтобы нашлись такие точки х; ееКМ,(х,), 1 1, ..., и и точка х* он дг(хо), что о 4 х =х,+ ... +хо. (44 ГЛ.
ГУ. ВЫПУКЛОВ ПРОГРАММИРОВАНИЕ Д о к а з а т е л ь с т в о. Согласно теоремам 1.3.7 и 1.3.6 из условий теоремы следует, что Км(хо) = П Км;(хо), (2.4) и если хгои(п(Мн ( = 1, ..., й — 1,хгои Мм то х, = х — хоан(в(Кмо(х), ( =- 1,..., й — 1 "о ~ Кмо(хо). Поэтому (п(КМ,(х,)П... П(ПСК„,,(,)ПК„,(,)+а. (2.5) Из соотношений (2.4), (2.5) и теоремы 1.3.2 вытекает, что Км (хо) = Км, (хо) + ° ° ° + Кмо(хо) (2 6) Тогда точка хо еи д~ (хо) П Км (хо), которая существует согласно теореме 2.2, допускает разлон'ение х*=х',+ ... +хо, хоки Ко,о(х,), (=1,...,)о, (2.7) что доказывает теорему.
Т е о р е м а 2.4. Пусть )(х) — собственная выпуклая функция, М=п Мо о 1 Ххо=х,+ ...+хо. (2.8) Причем, если 1=О, то среди точекх*„...,хоесть хотя бы одна ненулевая. Если же Х= 1, то эти условия являются достаточными. где М, — выпуклые множества, и существует точка х~ ыМ, в которой функция )(х) непрерывна. Тогда для того, чтобы точка хо была точкой минимума )(х) на множестве М, необходимо, чтобы нашлись такие векторы х* и д((хо), х еи Кмо(х ) и число Х, равное нулю или единице, что 5 2. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА 145 Доказательство.
Согласно теореме 22 вует вектор х*еид)(хе) такой, что х я Км(хе). справедлива формула (2.4), то по теореме 1.3.3 ны два случая. 1) Либо верна формула (2.6), а значит и (2.7). Последняя ' совпадает с равенством (2.8) 1. Так как теорема 2.2 давала необходимые точные условия, то в этом случае условие (2.8) одновременно и достаточным. 2) Либо существуют такие х;~ Км,(хе), не ные нулю, что сущестТак как возмож- формула при Х= и доста- является все рав- х,+...
+хе=О. В этом случае формула (2.8) справедлива при Л= О. 2. Ограничения, заданные выпуклыми неравенствами. В задачах выпуклого программирования область, в которой ищется минимум, часто задается системой выпуклых неравенств. Более точно, пусть ~~(х), 1=0,... ..., Ве,— выпуклые функции, Р— выпуклое множество, ао.а У,, Р О Требуется найти минимум выпуклой функции ~е(х) в области М, где М=(х: Цх) <О, 1=1, ..., т, хеиР). (2.9) Рассмотрим многозначное отображение, ставящее в соответствие каждой точке у ен К" множество а(у) = Их, хе): У(х) (у', 1=1, ..., и, 1а(х) (хв, хеиР). (2.10) И',(у, хе, х'*) =((В1 ((х, хе)+ хехее: (х, хе) я а(у)).
(х,хп Если положпть хе =О, хее=1 и обозначить Иг,(у, О, 1) 10 Б. Н. Пюеничнма Так как функции Дх) выпуклы и множество Р выпукло, то нетрудно убедиться в том, что а — выпуклое отображение из У = К" во множество подмнонееств пространства ХХК'. Вычислим функцию И'.(у, х*, хе*): 146 ГЛ. 1У. ВЫПУКЛОВ ПРОГРАММНРОВАНИВ через г'(у), то будем иметь Г(у) = )п$ (х'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
