§ 9. Методы вычисления оптимальной разделяющей гиперплоскости

Вычислять оптимальную разделяющую гиперплоскость на ЦВМ не многим сложнее, чем находить обобщенный портрет.

Для этого достаточно в градиентных методах максимизации функции  заменить условный градиент функции  в положительном квадранте на условный градиент функции при ограничениях

,              ,

и в качестве начальной точки выбрать точку, удовлетворяющую (14.27). В соответствии с теоремой П. 4, доказанной в приложении, условный градиент функции  на многообразии, задаваемом условиями (14.27), однозначно определяется формулой

                        (14.31)

при условии

.

Теперь остается подобрать величину  так, чтобы это условие выполнялось. Будем рассматривать ,  в (14.31) как функции  и обозначим

.

Очевидно, что для нахождения условного градиента достаточно найти корень уравнения

.

Из определения следует, что функция  – монотонно возрастающая непрерывная кусочно-линейная функция. Кроме того, при  она неограниченно убывает. Поэтому корень заведомо есть. Функция  может иметь изломы (разрывы первой произвольной) только в точках

,

.

Поэтому корень  можно определить так: найти линейный кусок, на котором лежит корень, а затем найти корень линейной функции, совпадающий с  на этом куске.

Таким образом, приходим к следующему алгоритму.

1. Вычисляется значение функции  в точках .

2. Если при всех  функция , то корень лежит на луче  и равен

,

где  берется по всем векторам , для которых ;  берется по всем векторам ;  – число векторов , для которых ;  – число векторов .

3. Если при некоторых  функция меньше нуля, то следует найти максимальное , при котором . Обозначим его через .

Тогда корень уравнения  лежит на участке, прилегающем справа к точке , и равен

,

где  берется по тем векторам , для которых  или ;  берется по тем векторам , для которых , или ;  и  – соответственно числа слагаемых в сумме  и .

4. Значение  вычисляется путем подстановки в (14.31) корня уравнения .

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