К задаче построения кусочно-линейной дискриминантной функции

Рассматривается задача численного нахождения кусочно-линейной функции, разделяющей два конечных множества A и B из Rn, трактуемых как обучающее множество в задаче дискриминантного анализа. Для целей строгой отделимости множеств подразумевается, что множества A и B не имеют общих точек, но и их наличие не является препятствием для предлагаемого алгоритма. Выпуклость дискриминантной функции или пустота пересечения выпуклых оболочек этих множеств также не предполагается. Естественным ограничением является требование принадлежности распознаваемого элемента аффинной оболочке обучающего множества. Для этих целей обобщается основной результат статьи Benchekroun B., Falk James E. [1], в которой была предложена формализация разбиений Делоне средствами линейного программирования для случая принадлежности элемента выпуклой оболочке исходных точек и при условии телесности этой оболочки. В настоящей заметке показано, что эти ограничения можно снять, сохраняя экстремальные свойства разбиений Делоне.