A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space

摘要

Consider a set, of n points in m-dimensional space. The convex hull of these points is a polytope, , in . The frame, , of these points in the set of extreme points of teh polytope with . The problem of identifying the frame plays a central role in optimization theory (redundancy in linear programming and stochastic programming), economics (data envelopment analysis), computational geometry (facial decomposition of polytopes) and statistics (Gastwirth estimators). The standard approach for finding the elements of consists of solving linear programs with m rows and n ? 1 columns; one for each element of , differing only in the right-hand side vectors. Although enhancements to reduce the total number of linear programs which must ultimately be solved as well as to reduce the number of columns in the technology matrix are known, the utility of this approach is severely limited by its laboriousness and computational demands. We introduce a new procedure also based on solving linear programs but with an important and distinguishing difference. The linear programs begin small and grow larger, but never have more columns than the number of extreme points of . Experimental results indicate that the time to find the frame using the new procedure is between about one-third and two-thirds that of an enhanced implementation of the established method currently in use.