On the Approximation of Unbounded Convex Sets by Polyhedra

Abstract

This article is concerned with the approximation of unbounded convex sets by polyhedra. While there is an abundance of literature investigating this task for compact sets, results on the unbounded case are scarce. We first point out the connections between existing results before introducing a new notion of polyhedral approximation called ($\epsilon ,\delta$)-approximation that integrates the unbounded case in a meaningful way. Some basic results about ($\epsilon ,\delta$)- approximations are proven for general convex sets. In the last section an algorithm for the computation of ($\epsilon ,\delta$)-approximations of spectrahedra is presented. Correctness and finiteness of the algorithm are proven.

arXiv comment22 pages, 4 figures, 1 table; correction of Algorithm 2, added Proposition 5.5, added references

References in corpus (6)

• Primal and Dual Approximation Algorithms for Convex Vector Optimization Problems
• Polyhedral approximation in mixed-integer convex optimization
• Equivalence between polyhedral projection, multiple objective linear programming and vector linear programming
• A vector linear programming approach for certain global optimization problems
• Tractability of Convex Vector Optimization Problems in the Sense of Polyhedral Approximations
• A Benson-Type Algorithm for Bounded Convex Vector Optimization Problems with Vertex Selection

Cited by in corpus (1)

• Polyhedral approximation of spectrahedral shadows via homogenization