Strict polynomial separation of two sets

Abstract

Одной из основных задач математической диагностики является строгое отделение двух конечных множеств в евклидовом пространстве. Широко известно строгое линейное отделение, которое сводится к решению задачи линейного программирования. Мы вводим понятие строгого полиномиального отделения и показываем, что строгое полиномиальное отделение двух множеств также сводится к решению задачи линейного программирования. Целевая функция предложенной в статье задачи линейного программирования имеет следующую особенность: ее оптимальное значение может равняться только нулю или единице - нулю, если множества допускают строгое полиномиальное отделение, и единице в противном случае. Приведены наглядные примеры строгого отделения двух множеств на плоскости с помощью алгебраических полиномов четвертой степени от двух переменных. Анализируется эффективность применения строгого полиномиального отделения при решении задач бинарной классификации данных.