Finding restrictions and convex hull by having a set of extreme points

Question

Suppose we are given a set of extreme points. Is it possible to find out all possible restrictions of the Linear Programming problem by having those extreme points? Well, if we have a linear programming problem we might be able to find out the extreme points via certain algorithm. What I am asking is whether it is possible to reverse the process and somehow find the restrictions and convex hull from the given set of extreme points? Do you know any resources for investigating such problems?

Answer 1

I may misunderstand what you mean by "restrictions" so please correct me if I'm wrong. I'm assuming you mean "linear inequalities that define the convex hull". If so, Qhull can take a set of extreme points and spit out the linear description.

Here's a simple example: suppose you want to compute the linear description of the convex hull of the points $(0,0,0$), $(1,0,0)$, $(0,1,0)$ and $(0,0,1)$ in $\mathbb{R}^3$. First, you need a file containing those three points in the right format:

3
4
0 0 0
1 0 0
0 1 0
0 0 1

The first line indicates the dimension that the points live in (3). The second line indicates how many points there are (4). Each subsequent line contains a point.

Call this file points.dat. Then to compute the linear description of the convex hull with QHull, call

/path/to/qhull n < points.dat

The n flag tells QHull to compute the linear description (or "normals with offsets" as it's referred to in the QHull documentation). The output looks like this:

4
4
    -0     -0     -1      0 
     0     -1      0     -0 
    -1     -0     -0      0 
0.5773502691896258 0.5773502691896258 0.5773502691896258 -0.5773502691896258 

The first line contains the dimension plus one, the second line contains the number of linear inequalities (facets). Each subsequent row is an inequality. In this case, the first 3 values are the coefficients of the three variables, and the last value is the NEGATIVE of the right-hand-side. The inequalities are in $\leq$ form. So for example, the final inequality above is $$ 0.577{x_1}+0.577{x_2}+0.577{x_3}\leq0.577 $$ or, dividing away $0.577$: $$ x_1+x_2+x_3\leq1. $$

Caveats

1. This only works in pretty low dimension. The QHull website says that they do not support computation in dimension $n\geq9$. I have found that for structured polyhedra, I can sometimes get up to $n=12$, but not higher.
2. This method requires that the convex hull of the input points is full-dimensional (i.e. $n$-dimensional). If it's not, QHull will fail.
3. This will also work if you call qconvex instead of qhull. I don't think the choice makes a difference (pretty sure it's the same code under the hood).
4. I don't claim this is the best way to do this--just that it will work.