An Algorithm for Identifying the Frame of a Pointed Finite Conical Hull

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.