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