TY - JOUR

T1 - On the MDM Method for Solving the General Quadratic Problem of Mathematical Diagnostics

AU - Малоземов, Василий Николаевич

AU - Соловьева, Наталья Анатольевна

PY - 2023/9/1

Y1 - 2023/9/1

N2 - Abstract: The term “mathematical diagnostics” was introduced by V. F. Demyanov in the early 2000s. The simplest problem of mathematical diagnostics is to determine the relative position of some point p and the convex hull C of a finite number of given points in n-dimensional Euclidean space. Of interest is the answer to the following questions: does the point p belong to the set C or not? If p does not belong to C, then what is the distance from p to C? In the general problem of mathematical diagnostics, two convex hulls are considered. The question is whether they have common points. If there are no common points, then it is required to find the distance between these hulls. From an algorithmic point of view, the problems of mathematical diagnostics reduce to special linear- or quadratic-programming problems, which can be solved by finite methods. However, the implementation of this approach in the case of large data arrays runs into serious computational difficulties. Such situations can be dealt with by infinite but easily implemented methods, which allow one to obtain an approximate solution with the required accuracy in a finite number of iterations. These methods include the MDM method. It was developed by Mitchell, Demyanov, and Malozemov in 1971 for other purposes, but later found application in machine learning. From a modern point of view, the original version of the MDM method can be used to solve only the simplest problems of mathematical diagnostics. This article gives a natural generalization of the MDM method, oriented towards solving general problems of mathematical diagnostics. In addition, it is shown how, using the generalized MDM method, a solution to the problem of the linear separation of two finite sets, in which the separating strip has the largest width, is found.

AB - Abstract: The term “mathematical diagnostics” was introduced by V. F. Demyanov in the early 2000s. The simplest problem of mathematical diagnostics is to determine the relative position of some point p and the convex hull C of a finite number of given points in n-dimensional Euclidean space. Of interest is the answer to the following questions: does the point p belong to the set C or not? If p does not belong to C, then what is the distance from p to C? In the general problem of mathematical diagnostics, two convex hulls are considered. The question is whether they have common points. If there are no common points, then it is required to find the distance between these hulls. From an algorithmic point of view, the problems of mathematical diagnostics reduce to special linear- or quadratic-programming problems, which can be solved by finite methods. However, the implementation of this approach in the case of large data arrays runs into serious computational difficulties. Such situations can be dealt with by infinite but easily implemented methods, which allow one to obtain an approximate solution with the required accuracy in a finite number of iterations. These methods include the MDM method. It was developed by Mitchell, Demyanov, and Malozemov in 1971 for other purposes, but later found application in machine learning. From a modern point of view, the original version of the MDM method can be used to solve only the simplest problems of mathematical diagnostics. This article gives a natural generalization of the MDM method, oriented towards solving general problems of mathematical diagnostics. In addition, it is shown how, using the generalized MDM method, a solution to the problem of the linear separation of two finite sets, in which the separating strip has the largest width, is found.

KW - MDM algorithm

KW - general problem of mathematical diagnostics

KW - machine learning

KW - mathematical diagnostics

KW - simplest problem of mathematical diagnostics

UR - https://www.mendeley.com/catalogue/d20fed9a-9479-3d6d-ab62-c9f5f638d84c/

U2 - 10.1134/s106345412303007x

DO - 10.1134/s106345412303007x

M3 - Article

VL - 56

SP - 362

EP - 372

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 3

ER -