# 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.

• I sampled and plotted the d=3 case, and it seems to support my argument.
– ls.
Jan 16 '20 at 10:03
• Also I'm not really an expert on this topic, but my idea for enumerating the vertices would be that in a vertex, at most one $x_i$ is strictly between $a_i$ and $b_i$, and for all other $i$ it is that $x_i = a_i$ or $x_i = b_i$. Now you could fix the $i$ where $a_i < x_i < b_i$, and use some recursion with pruning to set other values to either $a_i$ or $b_i$. Jan 16 '20 at 10:14

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:
• 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.

• You changed the question in such a way that it changed the problem. I require $\sum_i x_i = 1$ and not $\sum_i x_i \le 1$. You can not change the question just so you are able to answer it.
– ls.
Jan 17 '20 at 10:59
• @ls., I apologize for that - it appears that I misunderstood what you were asking for.
– D.W.
Jan 17 '20 at 19:24
• @ls., I have revised my answer, and I believe it now answers the question you were asking, taking into account your comment.
– D.W.
Jan 17 '20 at 19:38
• As far as I understand it, this does not seem to be valid if $b_i<1$. Assume the following $\mathbb{R}^3$ case: $a_i=0$, $b_1<1$ and $b_{i≠1}=1$. Then $c_1 > b_1$. Therefore you would proceed with replacing replace $a_i$ and $b_i$ with $c_i=1$. Reducing the polytope onto the hyperplane $H:=\{x: x_1=c_1\}$. However, I would expect two "new" vertices (new compared to the "default" $b=1$ case) on the hyperplane $H:=\{x: x_1=b_1\}$. I feel like I misunderstood your answer somewhere.
– ls.
Jan 20 '20 at 12:53
• @ls., oops! I had an error. Try the revised answer. You didn't misunderstand anything; I just wrote the wrong thing. Now this projects onto the hyperplane $H := \{x:x_1=b_1\}$, exactly as you say. Also, I hope the revised answer makes clear that this could potentially output far more vertices than the dimension (it could output exponentially many vertices, due to the recursion).
– D.W.
Jan 20 '20 at 17:31

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.

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 and $$a_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 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.

• But those points lie at the skeleton, e.g. for $x=(0,0,1)$ we have with $j=2$ that $\forall i\neq j.x_i\in\{0,2\}$, or do I oversee something? Jan 17 '20 at 23:21
• You're right. I don't know what I was thinking. Sorry.
– D.W.
Jan 17 '20 at 23:32
• I think this is true and would work. However, the scaling of $\mathcal{O}(2^{d-1})$ makes it infeasible (for my) higher dimensional problem.
– ls.
Jan 20 '20 at 12:58