A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space
A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space
复制标题
DOI：
10.1016/0377-2217(94)00366-1
复制
发表时间：
1996-07-19
影响因子：
6.4
通讯作者：
Helgason, RV
中科院分区：
文献类型：
--
作者：
Dula, JH;Helgason, RV
考虑m维空间中由n个点组成的集合A。这些点的凸包是R(M)中的多面体P。F子集等于或等于A的多面体P的极值点集合中的框架。确定框架的问题在最优化理论(线性规划和随机规划中的冗余)、经济学(数据包络分析)、计算几何(多面体的面分解)和统计学(Gastwirth估计)中发挥着核心作用。求F的元素的标准方法包括求解m行n-1列的线性规划；A的每个元素对应一个线性规划，只是右侧的向量不同。虽然已知减少最终必须解决的线性规划的总数以及减少技术矩阵中的列数的增强，但这种方法的实用性受到其繁琐和计算要求的严重限制。我们介绍了一个新的程序，也是基于求解线性规划，但有一个重要的和明显的区别。线性规划开始时很小，但逐渐变大，但列的数量永远不会超过P的极值点的数量。实验结果表明，使用新程序找到框架的时间大约是目前使用的已有方法增强实现的三分之一到三分之二。
Consider a set, A, of n points in m-dimensional space. The convex hull of these points is a polytope, P, in R(m). The frame, F of these points in the set of extreme points of the polytope P with F subset of or equal to A. 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 F consists of solving linear programs with m rows and n - 1 columns; one for each element of A, 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 P. 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.