Polyhedral cones

A set \(C \subseteq \mathbb{R}^n\) is called a cone if for all \(\mathbf{x} \in C\), \(\lambda \mathbf{x} \in C\) for all \(\lambda \geq 0\).

Given \(S \subseteq \mathbb{R}^n\), the cone generated by the set \(S\), denoted by \(\operatorname{cone}(S)\), is the set \[C = \left \{ \displaystyle\sum_{i=1}^k \lambda_i\mathbf{d}^i : k \geq 0,~ \lambda_1,\ldots,\lambda_k \geq 0,~ \mathbf{d}^1,\ldots,\mathbf{d}^k \in S \right \}.\] By convention, \(\operatorname{cone}(\emptyset) = \{\mathbf{0}\}\).

A cone is polyhedral if it is given by \(\{\mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} \geq \mathbf{0}\}\) for some \(\mathbf{A} \in \mathbb{R}^{m \times n}\).

Polyhedral cones form a special class of polyhedra and they arise in structural results concerning polyhedra. Some of these results will appear later on. In the meantime, we prove the following important result.

Theorem 10.1. Let \(C \subseteq \mathbb{R}^n\). Then \(C\) is a polyhedral cone if and only if there exist a nonnegative integer \(k\) and \(\mathbf{d}^1,\ldots, \mathbf{d}^k \in \mathbb{R}^n\) such that \(C = \operatorname{cone}\left( \left\{\mathbf{d}^1,\ldots, \mathbf{d}^k\right\}\right)\),

Remark. It is clear in the proof above that if \(\mathbf{a}^1,\ldots, \mathbf{a}^m\) have only rational entries, then so do \(\mathbf{d}^1,\ldots,\mathbf{d}^k.\) In other words, we have the following refinement of the theorem: If \(C\) is given by \(\{\mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} \geq \mathbf{0}\}\) where \(\mathbf{A} \in \mathbb{Q}^{m \times n}\), then there exist \(\mathbf{d}^1,\ldots, \mathbf{d}^k\in\mathbb{Q}^n\) for some positive integer \(k\) such that \(C = \displaystyle \left\{\sum_{i=1}^k \lambda_i \mathbf{d}^i : \lambda_1,\ldots,\lambda_k\geq 0\right\}\).

Worked examples

1. Let \(C = \left \{ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \in \mathbb{R}^2: \begin{array}{r} x_1 + 2x_2 \geq 0 \\ -3x_1 + x_2 \geq 0 \end{array} \right \}\). Show that \(C = \left \{ \alpha \begin{bmatrix} -2 \\ 1 \end{bmatrix} + \beta \begin{bmatrix} 1 \\ 3 \end{bmatrix} : \alpha, \beta \geq 0\right\}\).

   One can see that the conclusion holds from a sketch of \(C\). However, that does not constitute a legitimate proof.

   One way to approach this problem is to make use of the construction in the proof of the theorem. However, we will show a different method that uses what is already given.

   Let \(Q = \left \{ \alpha \begin{bmatrix} -2 \\ 1 \end{bmatrix} + \beta \begin{bmatrix} 1 \\ 3 \end{bmatrix} : \alpha, \beta \geq 0\right\}\). Thus, \(Q\) is the set of \(\begin{bmatrix} x_1 \\ x_2\end{bmatrix}\) satisfying \begin{eqnarray*} -2 \alpha + \beta & = & x_1 \\ \alpha + 3\beta & = & x_2 \\ \alpha, \beta & \geq & 0, \end{eqnarray*} or equivalently, \begin{eqnarray*} \alpha & = & -\frac{3}{7}x_1 + \frac{1}{7} x_2 \\ \beta & = & \frac{1}{7} x_1 + \frac{2}{7} x_2 \\ \alpha, \beta & \geq & 0. \end{eqnarray*} Thus, \(Q = \left \{ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} : \begin{array}{r} -\frac{3}{7}x_1 + \frac{1}{7} x_2 \geq 0 \\ \frac{1}{7} x_1 + \frac{2}{7} x_2 \geq 0 \end{array} \right\}\). Clearly, we have \(Q = C\).

2. Let \(C = \left \{ \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \in \mathbb{R}^3: \begin{array}{r} x_1 + 2x_2 - x_3 \geq 0 \\ -3x_2 + x_3 \geq 0 \end{array} \right \}\). Find \(\mathbf{d}^1,\ldots,\mathbf{d}^k \in \mathbb{Z}^3\) for some positive integer \(k\) such that \(C = \operatorname{cone}\left(\left\{ \mathbf{d}^1,\ldots\mathbf{d}^k\right\}\right)\).

   We proceed as in the proof of the theorem. We first need to find inequalities defining \(C' = \left \{ \alpha \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ -3 \\ 1 \end{bmatrix} : \alpha, \beta \geq 0 \right \}\) by eliminating \(\alpha\) and \(\beta\) from the system \begin{eqnarray*} \alpha \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ -3 \\ 1 \end{bmatrix} & = & \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \\ \alpha, \beta & \geq &0, \end{eqnarray*} or equivalently, \begin{eqnarray*} \alpha & = & x_1 \\ 2\alpha - 3\beta & = & x_2 \\ -\alpha + \beta & = & x_3 \\ \alpha, \beta & \geq &0. \end{eqnarray*} Using the first equation to eliminate \(\alpha\), we obtain \begin{eqnarray*} - 3\beta & = & -2x_1 + x_2 \\ \beta & = & x_1 + x_3 \\ x_1 & \geq & 0 \\ \beta & \geq &0. \end{eqnarray*}

   Adding three times the second equation to the first gives \begin{eqnarray*} 0 & = & x_1 + x_2 + 3x_3 \\ \beta & = & x_1 + x_3 \\ x_1 & \geq & 0 \\ \beta & \geq &0. \end{eqnarray*}

   Eliminating \(\beta\), we obtain \begin{eqnarray*} x_1 + x_2 + 3x_3 & = & 0 \\ x_1 & \geq & 0 \\ x_1 + x_3 & \geq &0. \end{eqnarray*} Thus, \(C' = \left \{ \begin{bmatrix} x_1 \\ x_2 \\ x_3\end{bmatrix} : \begin{array}{r} x_1 + x_2 + 3x_3 \geq 0 \\ -x_1 - x_2 - 3x_3 \geq 0 \\ x_1 \geq 0 \\ x_1 + x_3 \geq 0 \end{array} \right \}\).

   Hence, \(C = \left \{ \lambda_1 \begin{bmatrix} 1 \\ 1 \\ 3\end{bmatrix} + \lambda_2 \begin{bmatrix} -1 \\ -1 \\ -3\end{bmatrix} + \lambda_3 \begin{bmatrix} 1 \\ 0 \\ 0\end{bmatrix} + \lambda_4 \begin{bmatrix} 1 \\ 0 \\ 1\end{bmatrix} : \lambda_1,\lambda_2,\lambda_3,\lambda_4 \geq 0 \right \}\)

3. Let \(C \subseteq \mathbb{R}^n\) be a pointed polyhedral cone. Show that \(\mathbf{0}\) is the only extreme point of \(C\).

   Let \(C\) be given by \(\left\{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{0}\right\}\). Since \(C\) has at least one extreme point, \(\operatorname{rank}(\mathbf{A}) = n\). Since the entire system is active at \(\mathbf{0}\), it follows that \(\mathbf{0}\) is an extreme point by Proposition 8.4..

   Now, for every subsystem \(\mathbf{A}^=\mathbf{x} \geq \mathbf{0}\) of \(\mathbf{A}\mathbf{x} \geq \mathbf{0}\) with \(\operatorname{rank}(\mathbf{A}^=) = n\), we have that \(\mathbf{0}\) is the only solution to \(\mathbf{A}^=\mathbf{x} = \mathbf{0}\). Hence, \(C\) does not have any nonzero extreme point.