Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 7
Текст из файла (страница 7)
Сравнивая последнее равенство с соотношенпем (4.14), получаем Ин(х* + архе) = И' (хо) + а,(хо, х*), Х(х* + а„х*) — 1(х*) 0 (р). Таким образом, множество 1(хо+ а,х*) содержит больше индексов, чем Х(х"). Более того, векторы х,— жь 1ы1(х*), и х, — х; линейно независимы, так как <х, — хь хе) = О, ( ю Х(х*), (хр хь х ) = (хр х*) (хм х*) ) О~ что вытекает нз формулы (415) и положительности а„. Итак, показано, что среди векторов х; — хь ы 1(х* +архе), число линейно независимых по кРайней мере на один больше, чем среди векторов х, — ть (ш 1(х*). Кроме того, для всех х ы М (х, хв + архе) ( И'н(х" + арх") = = Игл(х*) + ар(хо~ х ) ~ (хо, х ) + ар(хо, х ) = = (хо, хе+ архе), т. е. вектор хе+ архе отделяет точку хо от М. Еслп среди вектоРов х, — хь 1~и 1(ХР+ архе), число линейно независимых меньше, чем и — 1, то описанную выше процедуру можно повторить.
Очевидно, что крайняя опора будет построена за конечное число шагов. Нетрудно видеть, что число крайних опор конечно. Действительно, если вектор хо определяет крайнюю опору, то он ортогонален н — 1 векторам х, — хь (ш 1(х*), и, следовательно, определяется однозначно с точностью до скалярного множителя. Так как 1(хе) есть подмноже- Е А езРАеенне точки и мееОТОГРАннык мнОжестВА 45 ство конечного множества Х, то число возможных подмножеств Хехг) конечно, а значит, конечно и число крайшех опор.
Теорема 4.6. Выпуклый многогранник может быть задан конечной системой линейных неравенств. Доказательство. Пусть 1п1ЛХта 8 п векторы хг, А =1, ..., 1, определяют все крайние опорЫ к М. Тогда система линейных неравенств (х, хь) (И'ге(хг), й = 1,..., 1, определяет многогранник М. Действительно, любая точка хлвЛХ удовлетворяет этой спстеме, а любая точка хФ М должна нарушать хотя бы одно из этпх неравенств согласно теореме йе.5. Если 1п1М = В, то можно рассмотреть множество М вЂ” хг, хг ен М, относительно надпространства Х ш ЛХ, в котором М вЂ” хэ лежит и имеет внутренние точки. В подпространстве ЬепМ многогранник М может быть задан конечной системой линейных неравенств.
Само подпространство ХХНМ можно задать конечным числом линейных уравнений. Совмещая все эти соотношения, получаем утверждение теоремы. Из теорем 4.4 и 4.6 непосредственно следует, что определения многогранника как выпуклой оболочки конечного числа вершин и как ограниченного множества, точки которого описываются конечной системой линейных неравенств, эквивалентны. Поэтому в зависимости от обстоятельств можно пользоваться либо одннм, либо другпм определением.
3. Многогранные конусы. Многогранники представляют собой ограниченные множества, которые можно задать конечной системой линейных неравенств. Рассмотрим важный класс неограниченных множеств, которые можно задать системой однородных линейных неравенств. Определение 4.4. Конус Х( называется миогограеи ным, если существует конечный набор векторов хь ...
..., х„ таких, что для векторов хш К и только для нкх выполняется равенство х= ~ А;х;. 1.;)6, 1'=1, ..., пе. (4.16) Е=Е гл. 1. Выпуклые 31ножествА Теорема 4.7. Многогранный конус может быть годан конечной системой линейных однородных неравенств (х, хь))~0, й = 1,..., 1. (4Л7) Д о к а з а т е л ь с т в о. Рассмотрим множество М точек вида (4Л6), для которых дополнительно выполнено неравенство Нетрудно видеть, что М есть многогранник, натянутый па точки О, хь ..., х... поэтому он может быть задан конечной системой линейных неравенств (х, хь))аю й= 1,..., 11. (4.18) Подставляя ОжМ в систему (4.18), получим, что а,~О, й= 1, ..., 1ь Пусть аз=О для й = 1, ..., 1~1н т. е.
прп 1 < й~1 неравенства (4Л8) переходят в (4Л7). Покажем, что точки х, удовлетворяющпе условиям вида (4Л7), и только они принадлежат конусу К. В сапом деле, если х определяется формулой (4Л6), то прп достаточно малом а ) 0 т т ах=,~~ айгхн ~ аЛ1.-=1, т. е. ахжМ, ах удовлетворяет неравенствам (4Л8), и, в частности, (4Л7). Но тогда точка х удовлетворяет однородным неравенствам (4Л7), так как а) О. Обратно, если х удовлетворяет неравенствам (4Л7)„ то при достаточно малом а)0 точка ах удовлетворяет условиям (4.18), т.
е. принадлежит многограннику М. Это озпачает, что т т ах= ~ Л1хо У~ Х1(1, Л1) О; поэтому Лг х= ~' — 1 х1 епК. Теор ем а 4.8. Многогранный конус замкнут. 4 4. БРАйние точкп и многогРАнные мнОжестВА 47 Доказательство. На основании предыдущей теоремы многогранный конус задается системой нестрогих линейных неравенств. Отсюда сразу следует, что он вам кнут. Теорема 4.9. Если конус К задан системой линейных неравенств (4 17), то сопряхсенный елгу конус К* является многогранным и состоит из элементов хв = ~ удхю ТАЪО. А=1 Доказательство.
Рассмотрим многогранный конус К = хв: хв = ~л~~~ уьхь, 'рь) О . а=г Он замкнут согласно предыдущей теореме. По определе- нию х~и (К)в, если 1 , х, Х,ьхь РО, 7,>О, у=1,... й а=1 Но последнее возможно лишь в том случае, когда <х,хЬ~О, й=1,...,), т: е. х ю К. Итак, К = (К)*. Так как К замкнут, то К*= (К)в*=К, что и требовалось доказать. Теорема 410.
Конус, заданный системой линейных неравенств, является многогранным. Доказательство. Пусть конус К задается системой линейных неравенств (4.17). Так как сопряженный ему конус К* является многогранным, то существуют такие точки хь ( = 1, ..., т, что точки х*ш Кв н только онп удовлетворяют неравенствам <хь хв> «О, 1=1,..., пг. Так как конус К замкнут, то К= (К*)в и на основании теоремы 4.9 т х = ~ч'„Х;х;, л4>0, т.
е. К вЂ” многогранный конус. 48 Рл. 1, Вьпхуклые множествА На основании теорем 4.7 и 4.10 можно заключить, что многогранный конус можно определить двумя способами. либо определением 4.4, либо при помощи конечной однородной системы линейных неравенств. Из существования двух способов задания многогранных конусов можно извлечь важные следствия. Теорема 4Л1.
Сумма многогранных конусов есть л1ногогранный конус. Доказательство. Пусть К1 и Кз — многогранные конусы. Тогда их злементы молино представить соответственно в виде ФИ 1 х, =,~~ Алх11 й1ЪО, хг = лв~ у;х,г.. Т;~)0. 1=1 1=1 Если теперь х 1н К1 + Кг, то т х = х1 + х, =,~„Л1х11+ ~л у;хпо 1=1 1=1 т.
е. К1+Кг есть снова многогранный конус. Т е о р е м а 4Л2. Пересечение многогранных конусов есть снова многогранный конус. Доказательство. По теореме 4.7 многогранные конусы К1 и Кг могут быть ааданы конечными линейными системами неравенств вида (4.17). Ясно, что пересечение К1 й Кг удовлетворяет линейной системе неравенств, обрааованной путем объединения систем, задающих К1 и Кг.
По теореме 4.10 К, ОКз — многогранный конус. Прямым следствием теорем 4.7 и 4.9 является следующее утверждение. Теорема 4ЛЗ. Конус, сопряженный многогранному, является многогранным. Теорема 4.14. Для многогранных конусов Кь ..., К выполняется соотношение (К1П" ПК )*=К1+ .. +К*. Доказательство. Согласно лемме 3.7 имеет место формула (К1П".ПК )*=К1+ ... +Кт. Но из предыдущего следует, что К;, 1=1,..., 1п,— $4. ИРАнние точки и мнОГОГРАнные множестВА 49 многогранные конусы (теорема 4.13), Ке+... + К многогранный конус (теорема 4Л1), а многогранный конус замкнут (теорема 4.8).
Поэтому черту замыкания над суммой в последней формуле можно убрать. 4. Многогранные множества. В предыдущих разделах были изучены два типа множеств — многогранники и многогранные конусы. Оба эти типа множеств являются'частным случаем более общего многогранного множества. Определение 4.5. Множество точек, удовлетворяющих системе линейных неравенств (х, х;))аи 1=1, ..., У, (4.19) называется многогранным. Теорема 4Л5. Многогранное множество есть сумма многогранника и многогранного конуса, и, наоборот, сумма многогранника и многогранного конуса есть многогранное множество.
Доказательство. Введем дополнительную коордпнату х" и заппшем систему неравенств (х, х";) — хеае) О, ( = 1, ..., 1, ха)~0. (4.20) Это однородная система линейных неравенств в К"+', согласно теореме 4ЛО она задает многогранный конус, элементы которого можно представить в виде (*)= А'Ц( ~), Ег)Е, а.еь Х где через ~ ) обозначен (я+1)-мерный вектор из К"+' с компонентами хе, х', ..., х".
При любых Л~> 0 выражение в правой части формулы (4.21) должно удовлетворять неравенствам (4.20). В частности, если )а=1, а Ь=О прн (Фу, то из неравенств вытекает, что х,')~0. Пусть Хе = 1уд хе = О, у = 1,..., т), 1+ = (уд хв е) О, у = 1,..., т1. Обозначим уу = х,/хчу, у; = )ух';, у ее 1т, и перепишем 4 Е.
Н. Пшеничный 50 гл. 1. Выпуклъге множестВА формулы (4.21) в следующем виде: ).)х,' = ~ у;, )е~" )ег+ х= ',~,'))х,+ ~ Х,х,(' — ",1= ~~Хх,+ ~р, уу;, )ег у;) О, (4.22) у, ) О. (4.23) Итак, каждое решение системы (4.20) можно представить в виде (4.22), (4.23). Но решение системы (4Л9) получается пз решения спстемы (4.20), если положить ха=1. Таким образом, любое решение системы (4.19) можно представить в виде х= с' Х;х)+ ~ у,у;, )м)~0, (4.24) у; =1, у;)О, усну+. (4.25) )нг' Доказательство.
Так как К':-'1апК, то Квы зз (Ь~п К)", где (Еш К)А — ортогональное дополнение 1лпК до всего пространства Х. Очевидно, что Кй Ка'= — Вш К. Возьмем в качестве основного пространства Ь~ВК и найдем сопряженный конус (К й Кс)е относительно этого пространства, т. е. рассматривая векторы хе только нз БЫК. Так как г( К й Кс Ф О, то в пространстве Ып К применима теорема 3.2, т.
е. Из этих формул видно, что первая сумма в правой части формулы (4.24) представляет собой точки некоторого многогранного конуса, вторая — многогранника. То, что сумма многогранника и многогранного конуса есть многогранное множество, легко доказывается обратным ходом рассуждений от формул (4.24), (4.25) через соотношения (4.22), (4.23) к системе (4.20) и от нее (хг = 1) к системе (4.19). Теорема доказана. 5. Пересечение многогранного и произвольного конусов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
