§ 10. Построение оптимальной разделяющей гиперплоскости модифицированным методом Гаусса–Зайделя

Рассмотрим еще один метод построения оптимальной разделяющей гиперплоскости. Идея метода основана на том, что оптимальная разделяющая гиперплоскость ортогональна отрезку, соединяющему ближайшие точки выпуклых оболочек  и , и проходит через его середину. Точка  принадлежит выпуклой оболочке векторов , если

, , .

Аналогично точка  принадлежит выпуклой оболочке векторов , если

, , .

Поэтому, для того чтобы найти оптимальную разделяющую гиперплоскость, достаточно найти минимум квадратичной формы , где

,

в области

, ,

, .     (14.32)

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

В вычислительном плане эта задача никак не проще той, которая рассмотрена в предыдущем параграфе. Здесь ограничения задаются двумя условиями типа равенства, тогда как там входило лишь одно такое условие.

Рассмотрим модифицированный метод Гаусса – Зайделя для поиска максимума  в области (14.32). Модификация метода Гаусса – Зайделя направлена на то, чтобы при движении вдоль выбранной координаты, во-первых, не выйти за пределы положительного квадранта, а во-вторых, все время оставаться на многообразии  (или ).

Итак, пусть в -й момент времени точка  удовлетворяет условию (14.32) и совершается шаг вдоль координаты . Тогда величина шага , модифицированного метода Гаусса – Зайделя определяется из условия

,                  (14.33)

где

, .

Минимум величины (14.33) находится при шаге

.

Таким образом, рекуррентная процедура поиска оптимальной разделяющей гиперплоскости задается так:

.               (14.34)

Аналогично находится значение  в случае движения по :

,

где

                      (14.35)

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

, .

Рекуррентная процедура (14.34), по существу, есть алгоритм Б. Н. Козинца для построения оптимальной разделяющей гиперплоскости.

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