§ 9. Методы вычисления оптимальной разделяющей гиперплоскости
Вычислять оптимальную разделяющую гиперплоскость на ЦВМ не многим сложнее, чем находить обобщенный портрет.
Для этого достаточно в градиентных методах максимизации функции
заменить условный градиент функции
в положительном квадранте на условный градиент функции при ограничениях
,
,
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_104.files/image006.gif)
и в качестве начальной точки выбрать точку, удовлетворяющую (14.27). В соответствии с теоремой П. 4, доказанной в приложении, условный градиент функции
на многообразии, задаваемом условиями (14.27), однозначно определяется формулой
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_104.files/image007.gif)
(14.31)
при условии
.
Теперь остается подобрать величину
так, чтобы это условие выполнялось. Будем рассматривать
,
в (14.31) как функции
и обозначим
.
Очевидно, что для нахождения условного градиента достаточно найти корень уравнения
.
Из определения следует, что функция
– монотонно возрастающая непрерывная кусочно-линейная функция. Кроме того, при
она неограниченно убывает. Поэтому корень заведомо есть. Функция
может иметь изломы (разрывы первой произвольной) только в точках
,
.
Поэтому корень
можно определить так: найти линейный кусок, на котором лежит корень, а затем найти корень линейной функции, совпадающий с
на этом куске.
Таким образом, приходим к следующему алгоритму.
1. Вычисляется значение функции
в точках
.
2. Если при всех
функция
, то корень лежит на луче
и равен
,
где
берется по всем векторам
, для которых
;
берется по всем векторам
;
– число векторов
, для которых
;
– число векторов
.
3. Если при некоторых
функция меньше нуля, то следует найти максимальное
, при котором
. Обозначим его через
.
Тогда корень уравнения
лежит на участке, прилегающем справа к точке
, и равен
,
где
берется по тем векторам
, для которых
или
;
берется по тем векторам
, для которых
, или
;
и
– соответственно числа слагаемых в сумме
и
.
4. Значение
вычисляется путем подстановки в (14.31) корня уравнения
.
Подробнее структура алгоритма построения оптимальной разделяющей гиперплоскости будет рассмотрена в главе XV.