Find vertices of a convex polytope, defined by intersecting half-spaces

I am looking for a algorithm that returns the vertices of a polytope if provided with the set of intersecting half-spaces that define it.

In my special case the polytope is constructed by the following constraints on $x \in \mathbb{R}^d$:

• $\sum_i x_i = 1$ (i.e., $\|x\|_1 = 1$).

• $0 \le a_i \leq x_i\leq b_i \leq1$, where the $a_i,b_i$ are given

This can either be thought of as the intersection of the hyper-plane (defined by the first constraint, in combination with the range restriction of the second constraint) with a hyper-cube (defined by the second constraint) or as the intersection of half-spaces where the first constraint is the intersection of two half-spaces that only intersect on a hyper-plane.

This always generates a convex polytope, if I am not mistaken, as long as the intersection creates a bounded set.

I would like to have an algorithm that returns the set vertices of the polytope if provided with the set of $a_i$'s and $b_i$'s.

There is a special case where there exists no $x$ that satifies this condition. Ideally, this would be picked up on.
Therefore, I would wish for an algorithm that checks if such a polytope exists and if so returns the vertices.

Your problem is a special case of enumerating the vertices of a convex polytope, and there is an efficient (polynomial-delay) recursive algorithm for your special case, which I will describe next.

If $a_1+\dots+a_d > 1$, then there is no solution, and you can terminate. If $a_1+\dots+a_d=1$, there is a single solution $(a_1,\dots,a_d)$, so output it and terminate. Otherwise, I'll assume $a_1+\dots+a_d

• If $c_i \le b_i$, output $(a_1,\dots,a_{i-1},c_i,a_{i+1},\dots,a_d)$; it is a vertex of the original polytope.

• Otherwise, replace $a_i \le x_i \le b_i$ with $b_i \le x_i \le b_i$ (i.e., replace $a_i$ with $b_i$) and recurse to output the vertices of the resulting polytope.

To help others find this by search: it's the intersection of the unit simplex (points of L1 norm exactly one) and an axis-aligned box.

In general, if the polytope is defined by an intersection $m$ half-spaces, then a vertex is defined by choosing a combination of $d$ out of the $n$ of the corresponding hyper-planes; if their intersection is a single point, and it is in the polytope, then it is a vertex. This gives an exponential-time algorithm for enumerating all vertices for a general polytope. There are other algorithms for the general case, but that's beyond the scope of this answer.

StackExchange Computer Science Q#119562, answer score: 4