Find description of convex set by equations

Question

I have given the polyhedron $P$ which is given by the convex hull of the points $v_1 = (0,0,0), v_2 = (1,0,0), v_3 = (0,1,0), v_4 = (0,1,1)$. I want to find the representation of $P$ as the intersection of closed half-spaces, i.e. I want to find a Matrix $A$ and a vector $b$, such that $P = \{ x \in \mathbb{R}^3: Ax \leq b \}$.

In our lecture notes there is a similar example where a rhombus $Q$ is given by the convex hull of the points $(1,0), (-1,0), (0,1), (0,-1)$. It was said $Q$ can be described as the set \begin{align} Q = \{ x \in \mathbb{R}^2 ~|~ \exists \lambda_1, \dots, \lambda_4 \geq 0, \sum\limits_{i=1}^{4} \lambda_i = 1, x = (\lambda_1 - \lambda_2) e_1 + (\lambda_3 - \lambda_4) e_2 \} \end{align} with $e_1$ and $e_2$ being the standard unit vectors. Once we find this description we can use Fourier-Motzkin Elimination to find the Matrix $A$. So I was trying to find an analogous description of $P$ given by the vertices I mentioned above, but I failed. My first try was \begin{align} P = \{ x \in \mathbb{R}^3 ~|~ \exists \lambda_1, \lambda_2, \lambda_3 \geq 0, \sum\limits_{i=1}^{3} \lambda_i = 1, x = \lambda_1 e_1 + \lambda_2 e_2 + \lambda_3 (e_2 + e_3)\}, \end{align} but this set does not contain the point $(0,0,0)$. I had some other attempts but they all did not work out. So my question is, if there is a certain way to find the correct equations to describe the polyhedron or is it rather a kind of "smart-guessing" ?

Answer 1

• $v_1, v_2, v_3$ belong to $x_3=0$
• $v_1, v_2, v_4$ belong to $x_2=x_3$
• $v_1, v_3, v_4$ belong to $x_1=0$
• $v_2, v_3, v_4$ belong to $x_1+x_2=1$

ain't it?

--- rk

Answer 2

In the method that you propose to use, the expression that defines the set is a convex combination of the vertices of the polyhedron. It’s a bit unfortunate that it was presented to you in simplified form since that obscures the simple construction: It’s just a linear combination $\sum_i \lambda_iv_i$ of the vertices with the constraints $\lambda_i\ge0$ and $\sum_i\lambda_i=1$. So, for this tetrahedron, we would have the combination $$\lambda_1(0,0,0)+\lambda_2(1,0,0)+\lambda_3(0,1,0)+\lambda_4(0,1,1) = \lambda_2e_1+(\lambda_3+\lambda_4)e_2+\lambda_4e_3.$$ Even though it doesn’t appear in the final expression, you still need to account for $\lambda_1$ in the constraint $\sum_i\lambda_i=0$. Leaving $\lambda_1$ out of that constraint amounts to fixing it at $0$, in which case all of the points lie on the plane defined by the second through last vertices: the tetrahedron collapses into the triangle $\triangle{v_2v_3v_4}$.

For a small problem like this one, you could take a more direct approach instead. Take the vertices three at a time and find the equation of the corresponding plane, choosing the direction of the normal $n$ so that if the equation of the plane is $n\cdot x=b$ the remaining vertex $v$ satisfies $n\cdot v\le b$. You then stack the coefficients of the resulting equations into the augmented matrix $[A\mid b]$. For example, taking $v_2$, $v_3$ and $v_4$, we can obtain the normal $(1,1,0)$, so an equation of the plane is $x+y=1$. Comparing this to the remaining vertex, we see that the appropriate half-space is $x+y\le1$, so the first row of $A$ is $(1,1,0)$ and the first element of $b$ is $1$. Continuing with the other faces will give you the other three rows.