An Algorithm for Identifying the Frame of a Pointed Finite Conical Hull
J. H. Dulá, R. V. Helgason, N. Venugopal
INFORMS Journal on Computing · 1998 · Volume 10 · Issue 3
Abstract
We present an algorithm for identifying the extreme rays of the conical hull of a finite set of vectors whose generated cone is pointed. This problem appears in diverse areas including stochastic programming, computational geometry, and non-parametric efficiency measurement. The standard approach consists of solving a linear program for every element of the set of vectors. The new algorithm differs in that it solves fewer and substantially smaller LPs. Extensive computational testing validates the algorithm and demonstrates that for a wide range of problems it is computationally superior to the standard approach.
Keywords
Linear programming, convex analysis, computational geometry, Theorem of alternatives, geometry, polyhedral cones, separation
Enable JavaScript for citation tools and additional paper interactions.