§ 8. Двойственная задача
Точно так же как при нахождении
обобщенного портрета, здесь оказывается удобным перейти к двойственной задаче.
Воспользуемся условиями Куна – Таккера. Согласно теореме 14.4, для того чтобы
величина 
,
рассматриваемая как функция 
и 
, достигала минимума при ограничениях
(14.20) в точке 
необходимо
и достаточно, чтобы
а)
точка удовлетворяла
(14.20) и
б)
градиент функции в этой точке раскладывался с положительными коэффициентами по
градиентам ограничений, которые достигаются в точке .
Иными словами, необходимо и
достаточно, чтобы существовали такие числа 
и 
, что
, (14.25)
и,
кроме того,
,
причем
,
. (14.26)
Рассмотрим теперь функцию
,
где
положено
.
Будем искать максимум этой
функции при ограничениях
,
,
. (14.27)
Согласно
условиям Куна – Таккера, для того чтобы максимум функции 
при ограничениях (14.27)
достигался в точке 
,
необходимо и достаточно, чтобы:
а) точка
удовлетворяла
условиям (14.27) и
б) существовали
числа 
;
такие, что
,
и
, 
, где положено 
.
Ввиду произвольности
положительных чисел 
, 
условие б) равносильно существованию
числа такого,
что
,
(14.28)
и
,
. (14.29)
Сопоставляя условия Куна –
Таккера для минимума функции при ограничениях (14.20) и для
максимума функции при
ограничениях (14.27), получаем следующую теорему.
Теорема 14.10. Точка , в которой достигается
максимум функции при
ограничениях (14.27), и вектор 
, доставляющий минимум функции при ограничениях
(14.20), связаны соотношением
. (14.30)
Таким образом, для нахождения
оптимальной разделяющей гиперплоскости достаточно найти максимум функции при ограничениях
(14.27), определить из (14.30) и задать гиперплоскость
уравнением
.
Отметим, что функция имеет, вообще
говоря, не единственный максимум. Но все точки , доставляющие максимум этой функции при
ограничениях (14.27), соответствуют одному и тому же вектору .
Значение максимума функции позволяет судить о
расстоянии между выпуклыми оболочками множеств 
и 
, которое равно
.
Действительно,
.
Напомним, что значения 
и 
отличны от нуля
только для тех векторов 
, для которых
, 
.
Поэтому
с учетом (14.27)
.
Следовательно,
.
Наконец,
.
Последнее соотношение позволяет в
ходе практического вычисления оптимальной разделяющей гиперплоскости оценивать
зазор между разделяемыми множествами. А именно, если найдена точка 
, удовлетворяющая
условиям (14.27), и значение функции в этой точке равно 
, то «зазор» не превосходит 
.
Для множеств, не разделимых
гиперплоскостью, т. е. таких, выпуклые оболочки которых пересекаются, функция в области,
определяемой соотношениями (14.27), возрастает неограниченно.
