Оптимальная разделяющая гиперплоскость

4.1. Существование и единственность

Пусть $$X$$ и $$\overline{X}$$ - конечные множества точек в евклидовом пространстве $$R^l$$.

Определение. $$X$$ и $$\overline{X}$$ разделимы гиперплоскостью, если существует единичный вектор $$\varphi$$ и число $$c$$, что $$(x,\varphi)>c$$ при $$x\in X$$, $$(\overline{x},\varphi)<c$$ при $$\overline{x}\in\overline{X}$$.

Обозначим $$c_1(\varphi)=\min_{x\in X}(x,\varphi)$$, $$c_2(\varphi)=\max_{\overline{x}\in\overline{X}}(\overline{x}\varphi)$$. Тогда $$(x,\varphi)>c_1(\varphi)$$ при $$x\in X$$, $$(\overline{x},\varphi)<c_2(\varphi)$$ при $$\overline{x}\in\overline{X}$$. Если $$c_1(\varphi)\geq c_2(\varphi)$$, то гиперплоскость$$(x,\varphi)=\frac{c_1(\varphi)+c_2(\varphi)}{2}$$ разделяет $$X$$ и $$\overline{X}$$.

В силу непрерывности $$c_1(\varphi)$$ и $$c_2(\varphi)$$ существует множество разделяющих гиперплоскостей, если существует (4.1).

Определение. Оптимальной называется разделяющая гиперплоскость (4.1), соответствующая вектору $$\varphi^*$$, при котором достигается максимум $$\Pi(\varphi)$$.

Теорема. Если два множества $$X$$ и $$\overline{X}$$ разделимы гиперплоскостью, то оптимальная разделяющая гиперплоскость существует и единственна.

Доказательство. Функция $$\Pi(\varphi)$$ непрерывна на сфере $$|\varphi|\leq 1$$. Значит, $$\max_{|\varphi|\leq 1}\Pi(\varphi)$$ существует и достигается при некотором значении $$\varphi^*$$. Предположим, что он достигается внутри сферы, т.е. $$|\varphi^*|<1$$. Тогда для $$\varphi^{**}=\frac{\varphi^*}{|\varphi^*|}$$ получаем$$\begin{gathered} \Pi(\varphi^{**})=c_1(\varphi^{**})-c_2(\varphi^{**})= \\ = \min_{x\in X}(x,\varphi^{**})-\max{\overline{x}\in\overline{X}}(\overline{x},\varphi^{**})= \\ = \frac{1}{|\varphi^*|}\Pi(\varphi^*)>\Pi(\varphi^*), \end{gathered}$$ что противоречит предположению о том, что $$\varphi^*$$ - точка максимума $$\Pi(\varphi)$$.

Следовательно, максимум достигается на границе сферы, т.е. $$|\varphi^*|=1$$.

Докажем единственность максимума. Предположим, что это не так и существуют различные $$\varphi^*$$ и $$\varphi^{**}$$ такие, что $$\Pi(\varphi^*)=\Pi(\varphi^{**})=\Pi_{\max}$$. Рассмотрим значение $$\varphi=\alpha\varphi^*+\beta\varphi^{**},\; \alpha+\beta=1, \; \alpha>0,\;\beta>0$$, не совпадающее ни с $$\varphi^*$$, ни с $$\varphi^{**}$$.$$\begin{gathered} c_1(\varphi)=\min_{x\in X}(x,\alpha\varphi^*+\beta\varphi^{**})= \\ =\min_{x\in X}\lfloor\alpha(x,\varphi^*)+\beta(x,\varphi^{**})\rfloor\geq \\ \geq\alpha\min_{x\in X}(x,\varphi^*)+\beta\min_{x\in X}(x,\varphi^{**})= \\ =\alpha\cdot c_1(\varphi^*)+\beta\cdot c_1(\varphi^{**}). \end{gathered}$$ Аналогично $$c_2(\varphi)\leq\alpha\cdot c_2(\varphi^*)+\beta\cdot c_2(\varphi^{**})$$.

Тогда$$\begin{gathered} \Pi(\varphi)=c_1(\varphi)-c_2(\varphi)\geq \\ \geq\alpha\cdot c_1(\varphi^*)+\beta\cdot c_1(\varphi^{**})-\alpha\cdot c_2(\varphi^*)+\beta\cdot c_2(\varphi^{**})=\\ =\alpha\cdot\Pi(\varphi^*)+\beta\cdot\Pi(\varphi^{**})= \\ =\alpha\cdot\Pi_{\max}+\beta\cdot\Pi_{\max}=\Pi_{\max} \end{gathered}$$ и $$\varphi$$ - тоже значение, на котором достигается максимум.$$\begin{gathered} |\varphi|^2=|\alpha\varphi^*+\beta\varphi^{**}|^2=\alpha^2|\varphi^*|^2+2\alpha\beta(\varphi^*,\varphi^{**})+\beta^2|\varphi^{**}|^2<1,\\ \text{т.к. }|\varphi^*|^2=1,\; |\varphi^{**}|^2=1 \text{ и } (\varphi^*,\varphi^{**})<1\text{ при }\alpha+\beta=1,\;\alpha>0,\;\beta>0. \end{gathered}$$

Но $$\varphi$$ лежит внутри сферы $$|\varphi|\leq1$$ и поэтому не может быть точкой максимума. Следовательно, предположение о существовании двух максимумов неверно и максимум единственный.

Таким образом, если максимум функции $$\Pi(\varphi)$$ достигается при значении $$\varphi=\varphi_{опт}$$, то гиперплоскость $$(x,\varphi_{опт})=\frac{c_1(\varphi_{опт})+c_2(\varphi_{опт})}{2}$$ максимально удалена от $$X$$ и $$\overline{X}$$ и разделяет их.

4.2. Построение оптимальной разделяющей гиперплоскости

Теорема. Если два множества $$X$$ и $$\overline{X}$$ разделимы гиперплоскостью, $$\Conv(X)$$ и $$\Conv(\overline{X})$$ – выпуклые оболочки этих множеств, а $$x^*\in Conv(X)$$ и $$\overline{x}^*\in Conv(\overline{X})$$ – пара ближайших точек в выпуклых оболочках, то$$\max_{|\varphi|=1}\Pi(\varphi)=|x^*-\overline{x}^*|,$$ где $$|x^*-\overline{x}^*|$$ – обозначает евклидово расстояние между точками $$x^*$$ и $$\overline{x}^*$$.

Доказательство. Положим $$\varphi^*=\frac{(x^*-\overline{x}^*)}{|x^*-\overline{x}^*|}$$. Из условий $$c_1(\varphi)=\min_{x\in X}(x,\varphi), \; c_2(\varphi)=\min_{\overline{x}\in \overline{X}}(\overline{x},\varphi)$$, следует, что $$c_1(\varphi^*)\leq;(x^*,\varphi^*),\; c_2(\varphi^*)=(\overline{x}^*,\varphi^*)$$ и, следовательно,$$\Pi(\varphi)=c_1(\varphi)-c_2(\varphi)\leq(x^*,\varphi^*)-(\overline{x}^*,\varphi^*)= (x^*-\overline{x}^*,\varphi^*)=|x^*-\overline{x}^*|$$ Следовательно $$\max_{\varphi=1}\Pi(\varphi)\leq|x^*-\overline{x}^*|$$ и для доказательства теоремы нужно показать, что справедливо неравенство$$\Pi(\varphi^*)\geq|x^*-\overline{x}^*|$$

Пусть точки $$y\in X$$ и $$\overline{y}\in\overline{X}$$ такие, что $$c_1(\varphi^*)=(y,\varphi^*)$$ и $$c_2(\varphi^*)=(\overline{y},\varphi^*)$$. Тогда$$\begin{gathered} \Pi(\varphi^*)=c_1(\varphi^*)-c_2(\varphi^*)=(y-\overline{y},\varphi^*)= \\ =(x^*+(y-x^*)-\overline{x}^*-(\overline{y}-\overline{x}^*),\varphi^*)= \\ =(x^*-\overline{x}^*,\varphi^*)+(y-\overline{x},\varphi^*)-(\overline{y}-\overline{x}^*,\varphi^*)=\\ =|x^*-\overline{x}^*|+(y-x^*,\varphi^*)-(\overline{y}-\overline{x}^*,\varphi^*). \end{gathered}$$

Теперь покажем, что $$(y-x^*,\varphi^*)\geq 0$$, а $$(\overline{y}-\overline{x}^*,\varphi^*)\leq 0$$, или, что то же самое:$$(y-x^*,x^*-\overline{x}^*)\geq 0,\;(\overline{y}-\overline{x}^*,x^*-\overline{x}^*)\leq 0$$ Пусть $$z=\lambda y+(1-\lambda)x^*,\;0<\lambda<1$$ – точка в $$R^l$$. Очевидно, что она лежит в выпуклой оболочке $$X$$, т.е. $$z\in Conv(X)$$. Тогда имеем$$\begin{gathered} |z-\overline{x}^*|^2=|\lambda(y-\overline{x}^*)+(1-\lambda)(x^*-\overline{x}^*)|^2=\\ =|\lambda(y-x^*)+(x^*-\overline{x}^*)|^2=\\ =|x^*-\overline{x}^*|^2+2\lambda(x^*-\overline{x}^*,y-\overline{x}^*)+\lambda^2|y-x^*|^2 \end{gathered}$$ Поскольку точки $$x^*$$ и $$\overline{x}^*$$ – ближайшие в выпуклых оболочках $$Conv(X)$$ и $$Conv(\overline{X})$$, получаем, что $$|z-\overline{x}^*|^2\geq|x^*-\overline{x}^*|^2$$. Тогда из (4.5) следует, что$$2\lambda(x^*-\overline{x}^*,y-x^*)+\lambda^2|y-x^*|^2\geq 0,$$ или $$2(x^*-\overline{x}^*,y-x^*)+\lambda|y-x^*|^2\geq 0\;\forall\lambda>0$$, что возможно лишь при $$(x^*-\overline{x}^*,y-x^*)\geq 0$$. Таким образом, первое из неравенств (4.4) доказано. Второе неравенство (4.4) доказывается аналогично.

Тем самым доказано неравенство (4.3), а из него (4.2) и утверждение теоремы.

Оптимальная разделяющая гиперплоскость ортогональна отрезку, соединяющему ближайшие точки выпуклых оболочек множеств $$X$$ и $$\overline{X}$$, и проходит через середину этого отрезка. Задача поиска пары ближайших точек сводится к задаче квадратичного программирования следующим образом.

Каждая точка $$y$$, лежащая в выпуклой оболочке $$Conv(X)$$, представима в виде $$y=\sum_{x\in X}\alpha_x x,\; \sum_{x\in X}\alpha_x=1,\; \alpha_x\geq 0$$. Аналогично, точка $$\overline{y}\in Conv(\overline{X})$$ представима в виде $$\overline{y}\sum_{\overline{x}\in\overline{X}}\beta_{\overline{x}}\overline{x},\; \sum_{\overline{x}\in\overline{X}}\beta_{\overline{x}}=1,\;\beta_{\overline{x}}\geq 0$$. Нужно найти пару точек $$y$$ и $$\overline{y}$$, обеспечивающих минимум выражения:$$|y-\overline{y}|^2= \left( \sum_{x\in X}\alpha_x x-\sum_{\overline{x}\in\overline{X}}\beta_{\overline{x}}\overline{x}, \sum_{x\in X}\alpha_x x-\sum_{\overline{x}\in\overline{X}}\beta_{\overline{x}}\overline{x} \right)$$ при условиях:$$\sum_{x\in X}\alpha_x=1,\;\alpha_x\geq 0,$$ $$\sum_{\overline{x}\in\overline{X}}\beta_{\overline{x}}=1,\;\beta_{\overline{x}}\geq 0.$$ Задача математического программирования (4.6-4.8) имеет два ограничения и квадратичную целевую функцию.

4.3. Алгоритм Гаусса-Зейделя

Задача состоит в нахождении наименьшего расстояния между множествами $$X$$ и $$\overline{X}$$.

1. В качестве начальных значений берем произвольную пару $$x_0$$ и $$\overline{x}_0$$. Другими словами в начальный момент $$t=0\;z_t=x_0\in X$$ и $$\overline{z}_t=\overline{x}_0\in\overline{X}$$.

2. Необходимо найти точку $$x_{t+1}$$ ближайшую к $$\overline{z}_t$$ на отрезке $$[z_t,x_t]$$. Обозначаем $$z_{t+1}=\overline{z}_t$$. Напишем условие ортогональности векторов $$(z_{t+1}-\overline{z}_t)$$ и $$(z_t-y_k)$$:$$(z_{t+1}-\overline{z}_t,z_t-x_k)=0.$$ Т.к. $$z_{t+1}=\lambda z_t+(1-\lambda)x_k=x_k+\lambda(z_t-x_k)$$, то$$\begin{gathered} (z_{t+1}-\overline{z}_t,z_t-x_k)=(x_k+\lambda(z_t-x_k)-\overline{z}_t,z_t-x_k)=\\ =\lambda(z_t-x_k,z_t-x_k)+(x_k-\overline{z}_t,z_t-x_k)=0 \end{gathered}$$ Следовательно, $$\lambda=\frac{(\overline{z}_t-x_k,z_t-x_k)}{|z_t-x_k|^2}$$. Если $$\lambda\leq 0$$, то $$z_{t+1}=x_k$$. Если $$\lambda\geq 1$$, то $$z_{t+1}=z_t$$. Если $$0\lt;\lambda<1$$, то $$z_{t+1}=\lambda z_t+(1-\lambda)x_k$$.

3. Далее необходимо найти точку $$\overline{z}_{t+1}$$ ближайшую к $$z_t$$ на отрезке $$[\overline{z}_t,x_r]$$. Обозначаем $$z_{t+1}=\overline{z}_t$$.

Данную процедуру необходимо повторять, пока не найдутся две ближайшие точки множеств $$X$$ и $$\overline{X}$$.