МДМ-метод для решения общей квадратичной задачи математической диагностики

Термин математическая диагностика был введен В. Ф. Демьяновым в начале 2000-х годов. Простейшая задача математической диагностики заключается в выяснении взаимного положения некоторой точки $p$ и выпуклой оболочки $C$ конечного числа заданных точек в $n$-мерном евклидовом пространстве. Интерес представляет ответ на следующие вопросы: принадлежит ли точка $p$ множеству $C$ или нет? Если $p$ не принадлежит $C$, то каково расстояние от $p$ до $C$? В общей задаче математической диагностики рассматриваются две выпуклые оболочки. Решается вопрос о наличии у них общих точек. Если общих точек нет, то требуется найти расстояние между данными оболочками. С алгоритмической точки зрения задачи математической диагностики сводятся к специальным задачам линейного или квадратичного программирования, для решения которых существуют конечные методы. Однако при реализации такого подхода в случае больших массивов данных возникают серьезные вычислительные трудности. На помощь приходят бесконечные, но легко реализуемые методы, которые позволяют за конечное число итераций получить приближенное решение с требуемой точностью. К таким методам относится МДМ-метод. Он был разработан Митчеллом, Демьяновым и Малоземовым в 1971 г. для других целей, но в дальнейшем нашел применение в машинном обучении. С современной точки зрения оригинальный вариант МДМ-метода можно использовать для решения только простейших задач математической диагностики. В данной статье дается естественное обобщение МДМ-метода, ориентированное на решение общих задач математической диагностики. Дополнительно показано, как с помощью обобщенного МДМ-метода можно находить решение задачи линейного отделения двух конечных множеств, при котором отделяющая полоса имеет наибольшую ширину.