How to transform the half-spaces that make up the convex hull to the set of extreme points?

Question

I have a convex set in Euclidean space (3D, but I would like answers for nD), which is characterized by a finite set of half-spaces (normal vector + point).

Is there a better algorithm for finding the extreme points of a convex set, in addition to computational brute force, of all points that are intersections of 3 (or, n) half-spaces and exclude those that are not extreme points?

Answer 1

The key term is to list the vertices of the polyhedron P. The idea of ​​the algorithm described below is to consider the dual polytope P *, then the vertices of P correspond to the faces of P *. The boundaries of P * are effectively calculated using Qhull , and then it remains to find the vertices by solving the corresponding subsystems of linear equations,

The algorithm is implemented in a BSD-licensed toolbox. Analyze N-dimensional polyhedra in terms of Vertex or (In) Equality for Matlab, written by Matt J , in particular, its lcon2vert component. However, in order to read the algorithm and reprogram it in another language, it is easier to work with the old and simpler con2vert file by Michael Kleder, on which the Matt J. project is built.

I will explain that he takes it step by step. Individual Matlab commands (such as convhulln ) are documented on the MathWorks website with links to basic algorithms.

---

The input consists of a set of linear inequalities of the form Ax<=b , where A is the matrix and b is the column vector.

Step 1. Try to find the interior point of the polyhedron.

The first attempt is c = A\b , which is the least square solution of the redefined linear system Ax=b . If A*c<b is performed componentwise, this is an internal point. otherwise, using multiparameter minimization, the objective function has a maximum of 0 and all numbers A*cb . If it is not possible to find the point where A*cb<0 is executed, the program exits with "inability to find the internal point".

Step 2. Translate the polyhedron so that the origin is its interior point

This is done b = b - A*c in Matlab. Since 0 is now an interior point, all elements of b are positive.

Step 3. Normalize so that the right side is 1

This is just dividing the ith row of A by b (i), done by D = A ./ repmat(b,[1 size(A,2)]); in matlab. From now on, only the matrix D is used. Note that the rows D are the vertices of the dual polyhedron P * mentioned at the beginning.

Step 4. Verify that the polyhedron P is bounded

A polyhedron P is unbounded if the vertices of its dual P * lie on one side of a certain hyperplane through the origin. This is determined using the built-in convhulln function, which calculates the volume of the convex hull of these points. The author checks whether adding the zero row to the matrix D increases the volume of the convex hull; if this happens, the program will exit with "Constraint Constraints Discovered."

Step 5. Vertex Calculation

It's a cycle

 for ix = 1:size(k,1) F = D(k(ix,:),:); G(ix,:)=F\ones(size(F,1),1); end 

Here, the matrix k encodes the faces of the double polyhedron P *, with each row listing the vertices of the facet. The matrix F is a submatrix of D consisting of the vertices of the faces P *. The backslash calls a linear solver and finds the vertex P.

Step 6: Cleaning

Since the polyhedron was translated in step 2, this translation is canceled using V = G + repmat(c',[size(G,1),1]); . The remaining two lines try to eliminate duplicate vertices (not always successfully).

Answer 2

I am the author of polco , a tool that implements the "double description method". The dual description method is known to work well for many degenerate problems. It was used to calculate tens of millions of generators, mainly for the problems of the biology of computer systems.

The tool is written in Java, runs in parallel on multi-core processors and supports various input and output formats, including text and Matlab files. You will find additional information and publications about the software and the double-description method using this link to the university department of ETH Zurich.