On the Kozinec Algorithm

In 1964, at the onset of machine learning, Kozinec proposed a simple numerical method (algorithm) for solving the following extremum problem. “In n-dimensional Euclidean space, two finite sets P1 and P2 are given. It is assumed that the corresponding convex hulls C1 and C2 of these sets have no common points. It is required to construct a hyperplane separating the sets P1 and P2, i.e., such a hyperplane that does not have common points with the sets C1 and C2 and, in addition, the sets C1 and C2 lie on opposite sides of this hyperplane. In fact, it is desirable to find, among all hyperplanes separating the sets P1 and P2, such a hyperplane whose distance to the set P1 ∪ P2 has the maximum value. Obviously, this hyperplane will be a hyperplane passing through the middle of the vector connecting any two nearest points of the sets C1 and C2, perpendicular to it.” Later this problem was called the problem of strict SVM separation of two finite sets (SVM is an abbreviation for Support Vector Machine). The Kozinec algorithm uses a natural geometric version of the optimality criterion for the problem under consideration. This paper provides a detailed analysis of the Kozinec algorithm in a modern light. In particular, a correct proof of its convergence is given. A working scheme algorithm is proposed. Two examples are considered in which the effectiveness of the conceptual and working schemes is compared.