Угловые точки выпуклого множества

Определение 3.5. Точка ZÎ Х называется угловой (крайней) точкой, если на множестве Х она не может быть представлена в виде выпуклой комбинации каких-либо точек х и у (для х¹ у) из Х: z(a)¹ (1-a)x+ay

Теорема 3.10. Любая точка замкнутого выпуклого и ограниченного множества Х может быть представлена в виде выпуклой комбинации конечного числа угловых точек этого множества.

Доказательство. Теорема доказывается методом математической индукции.

Рассмотрим пространство Е_n, содержащее множество Х.

Пусть при n =1 Х является некоторым отрезком [х₁, х₂]. В нем х₁, х₂- угловые точки. Любая точка xÎ [х₁, х₂] может быть представлена в виде

х = a₁x₁ + a₂ х₂, (3.20)

где a₂ = 1 - a₁, a₁=(х-х₁ )/(х₁ – х₂).

Пусть для пространства Е_n-1 теорема верна. Покажем, что она верна и для пространства Е_n. Итак, пусть х₀ Î Х Ì Е_n. Рассмотрим два случая.

1. Пусть х₀ – граничная точка множества Х. Построим опорную гиперплоскость p = {x/ < c, x> = < c, х₀> }. Множество Y=XÇ p является ограниченным, замкнутым, выпуклым множеством, как пересечение ограниченного замкнутого выпуклого множества Х а выпуклым, замкнутым множеством p. Кроме того YÌ Е_n-1 определяется гиперплоскостью p, поэтому в Y найдутся угловые точки х_i такие, что

х₀= a_i x_i, a_I ³ 0, (i= ), a_i=1. (3.21)

Покажем, что x_i (i= ) являются угловыми точками и для множества Х. Тогда существуют х' и х'' такие, что:

x_i= (1-a) x' + a х'', x', x'' Î X, aÎ (0, 1) (3.22)

По крайней мере одна из этих точек не принадлежит p, в противном случае x_i не угловая для Y.

Пусть x' Ï p тогда, так как p - опорная гиперплоскость к Х, а x'Î X, то

< c, x'> < < c, x₀> (3.23)

Вычислим значение < c, x_i>:

< c, x_i> = < c, (1-a) x'+ a х'' > = (1-a)< c, x' > + a< c, x''> (3.24)

Откуда следует

< c, x_i> < < c, x₀>, (3.25)

то есть x_i Ï p, что противоречит тому, что x_i Î Y=XÇ p. Этим мы доказали, что угловые точки множества Y являются и угловыми точками множества Х. Таким образом, для граничной точки теорема верна.

2. Пусть x₀Î X ⁰. Проведем через x₀ произвольную прямую l. Так как Х – ограниченное множество, то найдутся точки х' и х'', являющиеся пересечением границы Х с l. Тогда найдется g Î (0, 1) такая, что

x₀= (1-g) x'+ g х'' (3.26)

Для граничных точек х' и х'' теорема верна, поэтому

x’= a_i x_i, х'' = b_j y_j (3.27)

где x_i (i= ), y_j (j = ) – угловые точки множества X.

a_I ³ 0, (i= ), a_i=1, b_j ³ 0, (j= ), b_j=1. (3.28)

Заметим, что среди точек x_i, y_j могут быть совпадающие, отсюда получим

x₀= (1-g) x' + g х'' = a_i x_i./ (1-g)^-1+ b_j y_j /g^--1 (3.29)

Здесь a_i./ (1-g)^-1³ 0, i= , b _j /g^--1³ 0, j = .

Выполнив несложные преобразования, получим

a_i / (1-g)^-1+ b_j /g^--1 =1 (3.30)

Таким образом, получаем, что x₀ является выпуклой комбинацией конечного числа угловых точек x_i (i= ), y_j (j = ) множества Х и теорема полностью доказана.