2
$\begingroup$

I have been tasked with finding the equations defining the convex hull of a set of points in $\mathbb{R}^4$. Specifically, my set of points are all of the vertices of the 4-dimensional unit cube except $\{(1,0,1,1), (1,1,0,1), (1,1,1,0), (1,1,1,1)\}$. Call this set the cut set. In other words, I want to find the convex hull of the set $$S = \{(a_1,a_2, a_3, a_4): a_i = 0 \text{ or } 1\}\backslash \{((1,0,1,1),(1,1,0,1),(1,1,1,0),(1,1,1,1)\} $$

My thoughts

Because $\mathbb{R}^4$ is difficult to picture geometrically, I have tried considering how this works in $\mathbb{R}^3$. One observation that I've made is that all points neighboring the points in the cut set contribute in some way to the equations of the planes defining the convex hull.

For example, in $\mathbb{R}^3$, if the cut set is $\{(1,1,1)\}$, then one equation confining the convex hull of the remaining points can be defined by $\{(0,1,1), (1,0,1), (1,1,0)\}$.

However, it is possible that more than one plane may be necessary to confine the convex hull of a set of points. Think for example if the cut set in $\mathbb{R}^3$ is $\{(1,1,1),(0,1,1),(1,0,1)\}$.

I'm struggling to figure out how to generalize the idea in $\mathbb{R}^3$, and predictably in $\mathbb{R}^4$ as well. I know that the definition for a convex hull is $$C = \left\{ \sum_{j=1}^N \lambda_j p_j : \lambda_j \ge 0 \ \forall j, \sum_{j=1}^N \lambda_j =1\right\}$$ where $\{p_j\}_{j=1}^N$ is our set of points. I'm not sure how to use this information either, though.

$\endgroup$
0
1
+50
$\begingroup$

According to Porta, which uses Fourier-Motzkin elimination, the facets are as follows:

(  1) - x1          <= 0
(  2)     -x2       <= 0
(  3)        -x3    <= 0
(  4)           -x4 <= 0
(  5)           +x4 <= 1
(  6)        +x3    <= 1
(  7)     +x2       <= 1
(  8) + x1          <= 1
(  9) + x1   +x3+x4 <= 2
( 10) + x1+x2   +x4 <= 2
( 11) + x1+x2+x3    <= 2
( 12) +2x1+x2+x3+x4 <= 3

The first eight inequalities are just the $0$-$1$ bounds.

To obtain a valid formulation (not necessarily the convex hull) by hand, you can impose "no-good" constraints $$\sum_{j\in\{1,\dots,n\}:\ a_j=0} x_j + \sum_{j\in\{1,\dots,n\}:\ a_j=1} (1-x_j) \ge 1$$ that cut off each point $(a_1,a_2,a_3,a_4)$ of the cut set. For example, to exclude $(1,0,1,1)$, the no-good constraint is \begin{align} (1-x_1)+x_2+(1-x_3)+(1-x_4) \ge 1 \end{align}

$\endgroup$

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.