Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 6
Текст из файла (страница 6)
Крайние точки и многогранные множества В $1 показано (см. лемму 1.3), что в выпуклом множестве любая выпуклая комбинация его точек снова принадлежит этому множеству. Возникает вопрос: какие точки выпуклого множества моясно представить такими комбинациями других точек нз этого множества и какие нельзя? Оказывается, что именно последние являются характервымн и полностью задают данное выпуклое мцожество. 1. Крайние точки. О п р е д е л е и и е 4 1. Точка х вьпгуклого множества М называется крайней точкой, если не существует таких точек хн хгюМ, х1 чьха, что 1 1 — х,+ — х =х. 2 2 Геометрически это означает, что крайняя точка выпуклого множества не может быть серединой отрезка, концы которого лежат в этом множестве.
Вообще говоря, не во всяком выпуклом множестве существуют крайние точки. Например, точки, принадлежащие некоторой гиперплоскости, не могут быть крайними для выпуклого мпожества, совпадающего с этой гиперплоскостью, пбо через каждую точку этого множества проходит целая прямая. С другой стороны, компактные выпуклые множества полностью характериауются своими крайними точками. Теорема 41.
Компактное выпуклое множество в К" совпадает с совокупностью выпуклых колбинаиий своих крайних точек. Доказательство. Удобнее всего провести доказательство ипдукцией по числу намерений и. Для к=1 единственным видом компактных выпуклых множеств гл. 1. Выпуклые множества 38 являются замкнутые отрезки; поэтому теорема верна, ибо для всякого отрезка его концы являются крайними точкамп, а любая другая точка отрезка есть выпуклая комбинация его концов. Предположим теперь, что теорема верна для я( я, и докажем ее для п = й+ 1. Можно считать, что рассматриваемое выпуклое множество имеет в К1+1 внутренние точки. В противном случае его можно было бы погрузить в пространство меньшего числа измерений, где теорема верна по предположению индукции.
Итак, М ж К1+', 1В1Мчь И, хэ1нгпьМ. Возьмем произвольныйвектор рчьО и рассмотрим прямую хе+>.р, 3~1ВК1. Так как хе — внутренняя точка М, а М выпукло и компактно, то существуют >л >О и Аз< О такие, что хе+Ар 1ВМ для всех Х<Х1 п хэ + Хр 1и М для всех Х «)11. Ясно, что (- Хэ) Х1 хэ = 1 1 (хэ + )" р) + 1 Е ( э + »" р) 1 1 1 1 т. е. хэ есть точка отрезка с концами х~ хо + Х1Р, хт'= хо+ ) тр. Рассмотрим точку хь По определению точки хе+Ар прк Л ) ).1 не принадлежат М. Поэтому множества Е = (х = хе+ ХР: Х ) Х1) и М можно разделить, т. е.
существует такой вектор х", что (4Л) (х, х*> ~ (хэ+йр, х ), х1и М, ). ~).ь Отсюда следует, что <р, хе> Рэ О. Действительно, предположнв, что <р, хе> (О, иэ (4Л) получим <х, хе> ( <хм х*>+ >,<р, х">. Правая часть этого неравенства стремится к — , если Х-~+ , что приводит к противоречию. Поэтому пз неравенства (4Л) получаем,что <х, х*> «хе+).1р, хе> = <хп хэ>, хюМ.
(4.2) Положим Р, = (х1вМ: <х,х*> = <хм хе>). (4.3) Это множество не пусто, нбо содержит хь Кроме того, оно представляет собой пересечение компакта М с замкнутой 1 1. КРАНННЕ ТОЧКИ И 11НОГОГРЛННЫЕ МНОЖЕСТВА 39 гиперплоскостью <х, хь> = <х1, хе) п поэтому является ограниченным замкнутым выпуклым множеством размерности не более чем й. Согласно пред- положению индукции точка х, есть выпуклая комбинация крайних точек Р,. Покажем, что если у — крайняя точка Р„ то у — край- няя точка М. Предположим противное: у не является крайней точкой множества М, т.
е. 1 1 У= — У1+ — Уз, У1~М, узенМ, У1ФУ1. 2 2 В силу условий (4.2) и (4.3) выполняются соотношения <уь хе> ~ <хь хе>, <У1, хе> ( <хь хе>, <у, хе) = <хь хе), (х„хь) = (у, хе,1 = — (у„х*) + — (у„хе)((х, хе), Ф 1 поэтому <уь хе> = <х1, хе>, <уа, хе> <х1,хе>, т.
е. Уь у11в Рь Таким образом, у не есть крайняя точка Рь что противоречит допущению. Итак, если у — крайняя точка Р„то у — крайняя точ- ка М. Аналогичными рассуждениями доказываются свой- ства крайних точек множества Рз= (х1ЕМ: <х, х*> = <хз, х*>). Таким образом, согласно предположению теоремы и про- веденным рассуждениям Ь ч. х, =,.".', а1У1, у1он Р„а1)О, ~ а1= 1, 1=1 1 1 Ю* ю х, = Д ~11;, гт ен Р„~31 ) О,,'~~ ~1 = 1, 1=1 где уь г1 — крайние точки множеств Р„Р1 и, следова- тельно, М. Но, как было установлено ранее, ю 91 чз хэ = угх1 + узхз = .1а у1а~у1 + .~1 '~!1р111й 1=1 ГЛ. Ь ВЫПУКЛЫЕ МПОЖВСТВА где — ь. л, л,— ь,' т = л,— ь,' и, как легко проверить, Ч Ча Д у1а1+ ~ угрг= 1.
1е 1 1=1 Это означает, что точка хз есть выпуклая комбинация КРайних точек из М. Если же хе1и М, хе Ф 1псзХ, то либо хв — крайняя точка, либо хе и 1псМ можно отделить п повторить рассуждения. Теорема 4.2. Для того чтобы точка хе была крайней точкой мнохсества Мш Е", заданного системой линейных неравенств <х, х1 ) ( а1, 1 ~ 1 = ($, 2,..., 1к) (х, х;) =О, имеет ненулевое решение х. Пз ства 1(хв) вытекает, что (хо ~ ех, х ) = аь (х„~ ех, х1 ) ( а1, 1 е= 1 (хв)з определения (4.4) ынохсе- 1е= 1(ха)~ 1 Ф 1 ~ 1 (хо) э при достаточно малом е ) О, так что хо+ ех ~ М, хо — ех ш ЗХ, хо = т(хо+ах) + 2 (хв — зх) еп М т.
е. хе не есть крайняя точка М. необхдимо и достаточно, чтобы многхество 1(хо) = (й (хо, х1) = ао 1еи1) (44) содерлсало иодлгножество Хе, мощности п и чтобы точки х;, 1~Хе, были линейно независимы. Доказательство. Необходимость. Пусть множество (х;, 1 ~ 1(х,)) содержит меньше чем к линейно независимых злементов. Тогда на основании известных теорем линейной алгебры система линейных относительно х уравнений о». кглпн»де точки и 3»ногогглнные множкствл 41 Достаточность. Пусть точка хо»яМ такова, что мощность 1о равна и и для 1ж1о векторы х; линейно независимы. Тогда система неравенств, описывающих множество ЛХ, может быть записана в следующем виде: (хо х,') =ам 1ее1о (4.5) (то, х» ) ( (а», д ее 1',1,. (4.6) Допустим, что хо = ~ хд+ 2 хг хд~ ЛХ~ хое- =ЛХт хдчьхм (4.7) 1 1 Так как х», хг»нМ, то по определению М справедливы неравенства (х„, х»)(»г», »ен1, й = 1, 2.
(4.8) В силу условий (4.5), (4.8) соотношение (4.7) выполняется, только если (х„, х,*) = и», 1~1„й= Х, 2. (4.9) Итак, две различные точки удовлетворяют системе уравнений (4.9), в которой уравнения линейно независимы п число их, совпадающее с мощностью множества 1о, равно и — размерности пространства. Это невоаможно в силу известных теорем о разрешимости систем лпнейных уравнений. Теорема доказана. Из двух вышеприведенных теорем следует Теорема 4.3. Пусть М есть ограниченное мноасество, заданное конечной системой линейных неравенств (х, х;)(а», » я1. (4.»О) Тогда М есть выиуклал оболочка своих крайних точек, число которых конечно.
Доказательство. В силу условия (4ЛО) множество ЛХ компактно. На основании теорем 4Л, 4.2 множество ЛХ есть выпуклая оболочка множества своих крайних точек, причем каждая крайняя точка множества М есть единственное решение незырожденной системы и уравнений с и неизвестнымп (4.5) и поэтому однозначно определяется множеством 1,. Так как нз конечной системы индексов 1 подмноя»ество пз и индексов можно выбрать лишь конечным числом способов, то число крайних точек конечно.
ГЛ. Х ВЫПУКЛЫЕ МНОЖЕСТВА 42 2. Выпуклые многогранники. Предыдущая теорема мотивирует следующее Определение 4.2. Вьвпуклым лвногогранником называется выпуклая оболочка конечного числа точек. Из теоремы 4.3 теперь сразу вытекает Теорема 4.4. Ограниченное множество, заданное конечной системой линейных неравенств, есть многогранник. Итак, если М вЂ” многогранник, то любая его точка х есть выпуклая комбинация конечного числа точек хн ...,х,.: ;~', Л;=1. 1=1 Легко вычислить опорную функцию многогранника: И'м(х') = зпр (х, х*> = ивах (хв, х*>. енм 1«влгв Пусть Пх*) = (11 <хь х*> = Иг (х*), 1= 1, ..., т) есть множество индексов 1, для которых скалярное произведение <хв, х*> достигает максимума. Определение 4.3.
Гиперплоскость <х, х*> И'„(хз) называется опорой. Если 1 ы Пхь) и среди векторов х,— хь вю1(х*), имеется и — 1 линейно независимых, то опора называется крайней. Теорема 4.5. Пусть многогранник М содержит внутренние точки. Тогда любую точку хгФМ можно отделить при помощи крайней опоры, т.
е. найдется вектор х*, опреде яющий крайнюю опору и такой, что <х, х*> «<х„хь>, хви М. Доказательство. Без ограничения общности можно считать, что Овк(п$М. По теореме 2.1 существует такой вектор х*,что <х, х*> « <хг, хг> — е (4.11) для всех х ви М. Ясно, что Итвв(х*) «<хг, х >.
(4.12) 5 Ь КРАЙНИЕ ТОЧКН Н МНОГОГРАННЫЕ МНОЖЕСТВА 43 Предположим, что хх не определяет крайнюю опору. Тогда среди векторов х; — х; ()ш1(хх), 1 — фиксированный элемент 1(х*)) имеются не более и — 2 линейно незавпсппыл. Выберем теперь вектор х* так, чтобы выполнялись соотношения <х; — хь хх> = О, 11и1(хх), <хо — хах*> =О, (4ЛЗ) (хо хх) ~ О. Это всегда можно сделать, так как среди векторов хо— — хь х» — хь (шЕ(хе), имеютсЯ не более и — 4 линейно независимыл. Покажем, что найдется такой индекс д шЕ, что <х„хх> ) О.
В самом деле, так как по предположению 0 1и(пзЛХ, то 0 < И'м(х*) = 1пах (хр ха>, 1<1<я откуда следует существование д. В силу условий (4.(3) <хь хх> < 0 для 11а Пх*), поэтому д Ф Пх*). Для (1и Е(х*) из этпл же соотношений получаем (хь х*+ ахх> = <хь х*> + и(хь хх> = = И'„(х"') + а(хз, хх>. (4.14) Определим а; для 1 Ф1(х*) равенством <хь х*+ихх> =И' (х')+а(хе, хх>, т.
е. (х,х~> Числитель в выражении для а, всегда положителен, поэтому а,зьО. Так как <хз, х*> <О, а <х„хх> ) О, то а,)0. Выберем среди положительных аь 1ФЕ(хх), наименьшее: а,. Так как <хь х"> < И'„(хх), (ФПх*), ГЛ. Ь ВЫПУКЛЫЕ МНОЖЕСТВА то <х„х*+арх") (И'л(хо)+а„<хо, х*), (ФХ(хе), прячем <хр, х* + арх*> =ИХ (х") + а,(хо, хе).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
