There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \begin{bmatrix} 1 & 1 & 1 \\ -1 & 0& 0\\ 0 & -1 & 0 \\ 0 & 0 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \le \begin{bmatrix} 3 \\ 0 \\ 0 \end{bmatrix}$$ and we would like to find the decomposition as the direct sum of a

(i) linearity space,

(ii) cone,

(ii) polytope.

(iv) List the generators of each component and list the facets and minimal faces of each polyhedron.

By definition the linearity space is synonymous to the null space of the coefficient matrix which is easy.

The cone by definition is given as $\{x: x + y \in P, \ \forall y \in P\}\ldots (\alpha_1)\ \ $ or $\ \ \{x: Ax \le 0\} \ldots (\alpha_2)$ where $A, P$ are some matrix and polydrea respectively. Applying $(\alpha_1)$, I realized that $x \in \mathbb{R}^3$ and so each $y's \in P$ (column vectors) is in $\mathbb{R^4}$ so since the dimensions of $x$ and $y$ are not compatible, how can $(\alpha_1)$ be use in our problem above?

For $(\alpha_2)$ how do find $x$ such that $Ax \le 0$ holds? It looks like a null space but so far as I can remember, we don't have any inequality null space. A help here will be appreciated.

For the polytope, it is stated as $P = cov.hull\{ x' \ldots \ x^m \}$ for some $A^{m \times n}.$ Is the convex hull of $P$ the same as finding all submatrices of dimension $3\times 3$ from our given matrix and find the unknown variables so that the constraints are satisfy? When I did that I got a set of four linearly independent vectors in $\mathbb{R}^3.$ Is this also correct? Could there be any better way of finding the convex hull?

For generators, I have not come across a clear cut definition of it and it kind of confuses me with the vectors in the convex hull. Are they the same?

The definition of a facet is such that it is the maximal face of $P$ not equal to $P$. That means we cannot find the facet without knowing all the possible faces of $P$. Thus, is there any formula or tool available in finding the face and facets of $P$? If so what are the faces and facets of our coefficient matrix above?

  • 1
    $\begingroup$ Your problem statement has the product of a 4x3 matrix and a 3x1 vector $x$ less than or equal to a 3x1 vector. The dimensions don't match. Also, it's unclear what you mean by "each $y's \in P$". Is that an inner-product? Did you mean "each $y\in P$? $\endgroup$ – prubin Feb 4 at 19:17
  • $\begingroup$ By the definition of the cone given, I mean $y's$ is each column in $P$ $\endgroup$ – holala Feb 4 at 21:40

Your Answer

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

Browse other questions tagged or ask your own question.