| Consider a finite set of points or vectors in dimension m. The set containing all the convex combinations of these points is a polytope and the set containing all the positive combinations is a cone. One more object results from combining a finitely generated polytope and a finitely generated cone. It is a finitely generated unbounded polyhedron. In this dissertation we use polyhedral set theory, convex analysis, and linear programming to study unbounded polyhedra defined by a finite number of generators. We are interested in finding the most essential subset of its elements: its frame. The main contribution of this work is the development of two algorithms to efficiently obtain the frame of an unbounded polyhedron. In addition to these two algorithms, we describe a naive approach to solve the problem. The three approaches are based on a linear program especially formulated for this purpose. This work includes comparisons of the performance of the three algorithms and an example that illustrate how to obtain the frame employing each algorithm. This research extends and generalizes previous work on polytopes and cones, and has applications in statistics (robust estimation), computational geometry (facial decomposition), redundancy in linear programming, stochastic programming (recourse function estimation), and efficiency and productivity analyses (Data Envelopment Analysis). |
