§ 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), возрастает неограниченно.