Выпуклые множества

Рассмотрим множество вида

[x, y]={z/z=(1-a)x+ay, aÎ [0, 1], zÎ E_n}. (3.1)

Это отрезок прямой, проходящей через точки x и y, так как уравнение прямой, проходящей через точки x и y имеет вид:

z(a)=x+a(y-х)=(1-a)x+ay, (3.2)

причемпри a =0 Z(a)=x, при a=1 Z(a)=у.

Если a пробегает значения между 0 и 1, то Z(a) пробегает значения по прямой между x и y.

Определение 3.1. Множество ХÎ Е_n называется выпуклым, если для любых

х точек х, уÎ Х отрезок [х, y ]Î Х.

Если при этом (х, y)Ì X⁰ (X⁰- множество

z(a) внутренних точек множества Х), то Х называется строго выпуклым множеством.

y Из этого определения следует, что у выпуклого множества для любых х, уÎ Х и aÎ [0, 1] точка z(a) = (1-a)x + a y Î Х, если Х – строго выпуклое множество, то

Рис. 3.1. при aÎ (0, 1) z(a) является внутренней точкой множества Х.

На рис. 3.2. приведен пример выпуклого множества, а на рис. 3.3 пример множества, не являющегося выпуклым.

 

 

Рис. 3.2 Рис. 3.3.

Для выпуклых множеств справедливы следующие теоремы:

Теорема 3.1. Пересечение любого числа выпуклых множеств выпукло.

Доказательство. Пусть Z = Ç Х_l Возьмем х, уÎ Z и aÎ [0, 1].

^{lÎ L}

Покажем, что z(a)= (1-a)x + a y. Действительно, т. к. х, уÎ Z, то для любого lÎ L х, уÎ Х_l. Из выпуклостимножеств Х_l следует, что z(a)Î Х_l для всех lÎ L, поэтому z(a)Î Z, откуда следует выпуклость множества Z.

Теорема 3.2. Множество Х={x / < a, x> £ b, xÎ E_n }, где а – заданный вектор, b - скаляр, является выпуклым множеством.

Доказательство.

Пусть х, уÎ Z и aÎ [0, 1], докажем, что z(a)= (1-a)x + ay. Действительно

< z(a), a> = < (1-a)x + a y, a> = (1-a)< x, a> + a < y, a>

Так как

х, уÎ Х_, то есть < x, a> £ b, < у, a> £ b, то < z(a), a> £ b, т.е. z(a)Î Х.

Следствие 3.1. Множество Х={x / Ах £ b, xÎ E_n }, где А – матрица размерности m× n, bÎ E_n выпукло.

Определение 3.2. Точка z = a_i x_i называется выпуклой комбинацией точек х₁, х₂, …, х_n Î E_n, если a_i ³ 0, i = , a_i = 1.

Теорема 3.3. Выпуклое множество содержит любые выпуклые комбинации любых своих точек.

Доказательство. Пусть Х – выпуклое множество, содержащее элементы х_i,, i= , Произвольная система точек a_i ³ 0 такова, что a _i = 1. Покажем, что Z = a_ix_i Î X.. Доказательство будем проводить методом математической индукции. При n=2 утверждение следует из определения 3.1, если положить:

a₂ = a, a₁ = 1- a.

Пусть утверждение верно для некоторого n ³ 2, покажем его справедливость для n+1.

Пусть Z= a_i x_i, где x_i Î X, a_i ³ 0, i= , +1, a_i=1,

Z= a_ix_i+a_n+1 x_n+1 = = (1 - a_n+1 ) x_i + a_n+1 x_n+1.

По предположению точка x' = x_i Î X, т. к. x_i Î X,,

³ 0, i = , =1.

В силу выпуклости Х и определения 3.1 следует, что ZÎ X.

Теорема 3.4. Замыкание выпуклого множества Х выпукло.

Доказательство. Пусть х, у Î , a Î [0, 1]. Из определения замыкания множества следует, что в Х существуют последовательности {x_k}, {y_k} такие, что x_k x, y_k y при k ¥. В силу выпуклости множества Х точка z_k(a)= (1-a)x_k + a y_k. Î X для любого целого k. Переходя к пределу при k ¥ в силу определения замыкания множества, получаем, что

z(a)= (1-a)x + a y Î (3.3)