7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I sampled and plotted the d=3 case, and it seems to support my argument. $\endgroup$ – ls. Jan 16 at 10:03
  • $\begingroup$ 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$. $\endgroup$ – Laakeri Jan 16 at 10:14
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ls. Jan 17 at 10:59
  • $\begingroup$ @ls., I apologize for that - it appears that I misunderstood what you were asking for. $\endgroup$ – D.W. Jan 17 at 19:24
  • 1
    $\begingroup$ @ls., I have revised my answer, and I believe it now answers the question you were asking, taking into account your comment. $\endgroup$ – D.W. Jan 17 at 19:38
  • $\begingroup$ 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. $\endgroup$ – ls. Jan 20 at 12:53
  • 1
    $\begingroup$ @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). $\endgroup$ – D.W. Jan 20 at 17:31
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – fweth Jan 17 at 23:21
  • 1
    $\begingroup$ You're right. I don't know what I was thinking. Sorry. $\endgroup$ – D.W. Jan 17 at 23:32
  • $\begingroup$ 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. $\endgroup$ – ls. Jan 20 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.