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