Теоремы отделимости

Гиперплоскостью в Е_n называют множество вида: p = {x: < c, x> ³ < c, v> }, где с¹ 0. В пространстве Е_n гиперплоскость определяют два полупространства (подмножества):

Е_n ⁺ (p)= {x: < c, x> £ < c, v> } и(3. 11)

Е_n ^- (p)= {x: < c, x> ³ < c, v> } (3.12)

Будем исследовать возможности построения такой гиперплоскости p, чтобы заданное множество целиком содержалось в Е_n ^- (p), а также случаи, когда возможно построение гиперплоскости, разделяющей два заданных множества.

Теорема отделимости 3.7. Для любого выпуклого и замкнутого множества Х и любой точки v, не принадлежащей множеству Х, существует такая гиперплоскость

p = {x: < c, x> ³ < c, v> }, что ХÌ Е_n ^- (p). (3.13)

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

Пусть р – проекция точки v на множестве Х. Положим с = v - p, т. е.

p={x/< v-p, x> =< v-p, v> } (3.14)

и докажем, что для любой точки xÎ Х

< v - p, x> < < v - p, v> (3.15)

Пусть xÎ Х. Рассмотрим разность

< v - p, x> - < v - p, v> = < v - p, x-v> = < v - p, (x-p)+(p-v)> = (3.16)

= < v - p, x-p> - || v – p||².

По теореме 3.6. первое слагаемое отрицательное, так как vÏ , то второе слагаемое строго отрицательно.

Следовательно разность < v - p, x> - < v - p, v> < 0, откуда следует

< v - p, x> < < v - p, v>;.

Замечание. Нетрудно видеть, что ни одна из точек xÎ Х не принадлежит p, т.е. для всех xÎ Х < v - p, x> < < v - p, v>. Более того

< v - p, x> £ < v - p, v> -|| v – p||², где || v – p||²> 0.

Для множеств, не являющихся выпуклыми, теорема 3.7, вообще говоря, не верна. Так, для множества X и точки v рисунка 3.6 отделяющую гиперплоскость p построить нельзя.

. v

X

 

 

Рис.3.6.

Определение 3.4. Опорной гиперплоскостью в граничной точке n множества Х называется гиперплоскость p ={x / < c, x> ³ < c, p> }, для которой ХÌ Е_n ^- (p).

Теорема 3.8. В любой граничной точке р выпуклого множества Х существует опорная гиперплоскость.

Доказательство. Так как р граничная точка для Х, то в Е_n\ можно выделить последовательность {v_k}, для которой v_k р при k ¥. По теореме 3.7 для каждой точки v_k можно построить отделяющую гиперплоскость p_k={x/< c_k, x_k> = < c_k, v_k > }, где с_k=(v_k - p_k)/|| v_k – p_k||. Так как || с_k|| =1, то из последовательности {с_k } выделим сходящуюся к некоторому с последовательность {c_ki}. В силу предыдущего замечания для всякого xÎ Х можно записать неравенство

< c_ki , x> < < c_ki, v_ki >.

Переходя к пределу при i ¥, получаем

< c, x> £ < c, р >. Таким образом, ХÌ Е_n ^- (p). для p = {x: < c, x> = < c, р> }, что и требовалось доказать.

На рисунке 3.7 приведены примеры опорных гиперплоскостей. Заметим, что гиперплоскость p₁ является одновременно и касательной, чего нельзя сказать о p₂ и p_3.

 

p_3.

p₁ p₂

р ₂

р₁

X

Рис. 3.7.

 

Теорема 3.9 (о разделяющей гиперплоскости).

Если множество Х⁰ внутренних точек выпуклого множества Х не пусто и не пересекается с выпуклым множеством Y (Х⁰Ç Y=Æ), то для множеств Х и Y существует разделяющая гиперплоскость p, т. е. существует вектор с¹ 0, такой, что < c, у> £ < c, х> для всех у Î Y и х Î Х.

Доказательство. Множество Z = {Z/Z= y-x, xÎ Х⁰, yÎ Y} выпукло и Z=0_n. Из теорем 3.7 и 3.8 следует существование с¹ 0_n, такого, что

< c, z > £ < c, y-x> £ < c, 0> = 0 (3.17)

для всех xÎ Х⁰, yÎ Y. Это неравенство также справедливо для всех xÎ Х, так как xÎ X \ Х⁰ являются предельными точками Х⁰, а предельный переход не нарушает нестрогих неравенств. Отсюда

< c, y > £ < c, x>, xÎ Х, yÎ Y (3.18)

Зафиксируем некоторое y₀Î Y. Тогда из предыдущего неравенства следует ограниченность снизу < c, x> на множестве Х. Отсюда нетрудно показать существование точки pÎ такой, что

< c, y > = min < c, x> для xÎ (3.19)

Положим

p = {x/ < c, x> = < c, р> }, тогда ХÌ Е_n ⁺ (p).

Так как рÎ , то для всех yÎ Y справедливо неравенство

< c, y > £ < c, р>, т. е. YÎ Е_n ^- (p).

Теорема доказана полностью.