Отделимость выпуклых множеств

Опр. 1: Множества отделимы, если существует вектор , что (1) строго отделимы, если и сильно отделимы, если в (1) знак неравенства строгий.

Замечание: Геометрический смысл О.1 в существовании гиперплоскости, что А и В лежат в разных полупространствах по отношению к ней. Гиперплоскость отделяющая (строго, сильно).

Теорема 1: Пусть непустые, выпуклые и = . Тогда существует гиперплоскость , отделяющая и . Если и , то

Доказательство: Пусть . выпукло (Т.2, П.2.1). . , что (Т.3, П.2.3). Тогда (2)

Пусть .

Из (2) , и при (3) что означает выполнение (1). Пусть . Тогда из и (3) следует, что , а из и (3) следует, что ч.т.д.

Теорема 2. Пусть A,B ; A,B ,выпуклые замкнутые, одно из них ограничено и A B= . Тогда A и B строго отделимы. Если они оба ограничены, то отделимость будет сильной.

Пусть заданы матрица B размерности s n и вектор , причем .

Теорема 3 (Фаркаша). Неравенство <y,x> выполняется ,если , что .

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

Необходимость. Пусть <y,x> . Докажем, что . Пусть Y- замкнуто и выпукло (замкнутость следует из непрерывности линейных функций). По Т.2 , что

(4)

. Из (4) => , и . Но

Значит и

(5)

Т.к. , то

(6)

Положив из (5) и (6) получаем противоречие условиям теорем.

Достаточность. Пусть . Тогда . ч.т.д.