Analysis of algorithms for a class of continuous partition problems (Q1842452)

We consider a class of continuous problems of optimal partition of sets in the \(n\)-dimensional Euclidean space into nonintersecting subsets. Continuous optimal set partition problems arise in connection with some covering problems, global optimization problems seeking the attraction domains of local extrema, problems that find the nodes of optimal quadrature formulas for evaluation of integrals, computation of decision rules in nonlinear integer stochastic programming problems, and problems of statistical decision theory in which the criterion space is partitioned into disjoint classes. Moreover, a large body of important applied optimization problems are reducible to continuous optimal partition problems. These include, for instance, multicommodity plant location problems required to satisfy a continuously distributed demand, regional service planning problems, oil field outfitting problems, etc. Algorithm 1 proposed below solves continuous problems of optimal partition of sets in the \(n\)-dimensional Euclidean space \(E_n\) into nonintersecting subsets with determination of the center coordinates of the subsets. These are infinite-dimensional integer programming problems. The algorithm reduces the infinite-dimensional optimization problem to a finite-dimensional problem with a nonsmooth objective function, which is then solved by one of the modern methods of nondifferentiable optimization -- the \(r\)-algorithm. For the given class of partition problems, algorithm 1 generates a sequence that in general converges to local minima. We experimentally explore the efficiency of the algorithm and its ability to find the global minimum for the given class of partition problems, which in general are multiextremum optimization problems. Computational results are reported for some model of continuous optimal partition problems.