MDM ALGORITHM AND SYLVESTER’S PROBLEM

When developing numerical methods for solving nonlinear minimax problems, the following auxiliary problem arose: in the convex hull of some finite set in Euclidean space, find the point with the lowest norm. In 1971, B. Mitchell, V. Demyanov and V. Malozemov proposed a non-standard algorithm for solving this problem, which later became known as the MDM algorithm (based on the capital letters of the authors’ surnames). This article discusses a specific minimax problem: to find a ball of the smallest volume containing a given finite set of points. It is called the Sylvester problem and is a special case of the Chebyshev center of the set problem. The convex quadratic programming problem with simplex constraints is compared to the Sylvester problem. To solve this problem, the article suggests using a variant of the MDM algorithm. With its help, a minimizing sequence of plans is built, such that only two components differ from neighboring plans. The numbers of these components are selected based on certain optimality conditions. The weak convergence of the obtained sequence of plans is proved, from which follows the norm convergence of the corresponding sequence of vectors to the only solution of the Sylvester problem. Four typical examples on the plane are given.

Sylvester’s problem, quadratic programming, MDM algorithm