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

Question

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.

Answer 1

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 < 1$, so you use the following:

• For each index $i$ such that $a_i<b_i$:
  • Let $c_i = 1-a_1-\dots-a_{i-1}-a_{i+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.

Answer 2

The polymake tool/library can do exactly what you asked for, if you are interested in a practical solution. See here for a brief tutorial.

Answer 3

In the following I will call $C:=\{x:\forall i.a_i\le x_i\le b_i\}$ the cuboid and $H:=\{x:\sum_i x_i=1\}$ the hyperplane. I claim that all defining vertices of the polytope $C\cap H$ lie on the intersection of the $1$-dimensional skeleton $S:=\{x:\exists j.\forall i\neq j.x_i\in\{a_i,b_i\}\}$ with $H$, which can be evaluated by $\mathcal{O}(2^{d-1})$ operations (not very good, but still something, I guess).

A point $x$ is defining vertex of the polytope $P$ if and only if there is no non-zero $y$ and $\epsilon>0$ with $(x-\epsilon y,x+\epsilon y)\subseteq P$ (i.e. there is no axis along which $x$ can be moved in a small neighbourhood without leaving $P$).

Assume $x\in P$ doesn't lie in $S$, then w.l.o.g. $a_0<x_0<b_0$ and $a_1<x_1<b_1$. So $e_1-e_0$ is an axis along which we can move $x$ without leaving $P$ and $x$ is no defining vertex of $P$.

On the other hand, assume $x\in P$ lies in $S$. If $a_j<x_j<b_j$ then $e_j$ is the only axis along which we can move without leaving $S$, but moving along $e_j$ immedeately places us out of $H$, so $x$ is a defining vertex of $P$. If all $x_i$ lie in $\{a_i,b_i\}$ then $x$ is even defining vertex of $C$ hence defining vertex of $P$ as well.