Optimal partitions having disjoint convex and conic hulls

Abstract

Let A1,⋯, An be distinct k-dimensional vectors. We consider the problem of partitioning these vectors into m sets so as to maximize an objective which is a quasi-convex function of the sum of vectors in each set. We show that there exists an optimal partition whose sets have (pairwise) disjoint conic hulls. We also show that if the number of vectors in each of the sets is constrained, then a weaker conclusion holds, namely, there exists an optimal partition whose sets have (pairwise) disjoint convex hulls. The results rely on deriving necessary and sufficient conditions for a point to be an extreme point of a corresponding polytope. © 1992 The Mathematical Programming Society, Inc.