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}\).
Example. The set \(C = \left\{ \begin{bmatrix} x_1 \\ x_2\end{bmatrix} : 2x_1 - x_2 = 0,\, x_1 + 3x_2 \geq 0 \right\}\) is a polyhedral cone since the constraints can be written as \(\mathbf{A}\mathbf{x} \geq \mathbf{0}\) with \(\mathbf{A} = \begin{bmatrix} 2 & -1 \\ -2 & 1 \\ 1 & 3\end{bmatrix}\). Geometrically, \(C\) is represented by a ray emanating from the origin in the two-dimensional plane.
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)\),
Proof. Suppose that 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)\).
Hence, for all \(\mathbf{x} \in C\), there exist \(\lambda_1,\ldots,\lambda_k\) such that \begin{align*} \sum_{i=1}^k \lambda_i\mathbf{d}^i & = \mathbf{x} \\ \lambda_1,\ldots,\lambda_k & \geq 0 . \end{align*} Treating this as a system of a finite number of linear constraints in the variables \(\lambda_1,\ldots,\lambda_k,x_1,\ldots,x_n\), we can apply the Fourier-Motzkin elimination method to eliminate the variables \(\lambda_1,\ldots,\lambda_k\) to obtain a system of linear inequalities, call it \((S)\), that defines the set of \(\mathbf{x} =\begin{bmatrix} x_1\\ \vdots \\ x_n\end{bmatrix}\) which are precisely the elements of \(C\). As every constraint in the original system has a zero constant term, the inequalities in \((S)\) must be of the form \(\mathbf{a}^\mathsf{T}\mathbf{x} \geq 0\). Thus \(C\) is a polyhedral cone.
Conversely, suppose that \(C = \left \{ \mathbf{x} \in \mathbb{R}^n : {\mathbf{a}^i}^\mathsf{T}\mathbf{x} \geq 0,~i=1,\ldots,m \right \}\) where \(m\) is a nonnegative integer and \(\mathbf{a}^i \in \mathbb{R}^n\) for all \(i=1,\ldots,m\). Let \(C' = \operatorname{cone} \left(\left\{\mathbf{a}^1,\ldots,\mathbf{a}^m\right\}\right)\).
By what we have just proved before, \(C'\) is a polyhedral cone. Hence, there exist a nonnegative integer \(k\) and \(\mathbf{d}^1,\ldots,\mathbf{d}^k \in \mathbb{R}^n\) such that \(C' = \left\{ \mathbf{x} \in \mathbb{R}^n : {\mathbf{d}^i}^\mathsf{T}\mathbf{x} \geq 0,~i=1,\ldots,k \right\}.\) We show that \(C = \operatorname{cone}\left(\left\{ \mathbf{d}^1,\ldots, \mathbf{d}^k\right\}\right)\).
Claim: If \(\mathbf{u} \in C\) and \(\mathbf{v} \in C'\), then \(\mathbf{u}^\mathsf{T} \mathbf{v} = \mathbf{v}^\mathsf{T} \mathbf{u} \geq 0\).
Indeed, if \(\mathbf{v} \in C'\), then \(\mathbf{v} = \lambda_1 \mathbf{a}^1 + \cdots \lambda_m\mathbf{a}^m\) for some \(\lambda_1,\ldots, \lambda_m \geq 0\). Hence, \begin{eqnarray*} \mathbf{u}^\mathsf{T} \mathbf{v} = \mathbf{v}^\mathsf{T} \mathbf{u} & = & \left(\sum_{i=1}^m \lambda_i \mathbf{a}^i\right)^\mathsf{T}\mathbf{u} \\ & = & \sum_{i=1}^m \lambda_i\left( {\mathbf{a}^i}^\mathsf{T}\mathbf{u}\right) \\ & \geq & 0 \end{eqnarray*} as desired.
Also, note that \({\mathbf{d}^j}^\mathsf{T} \mathbf{a}^i \geq 0\) for all \(i = 1,\ldots,m\) and \(j =1,\ldots,k\) since \(\mathbf{a}^i \in C'\).
Let \(\mathbf{x}'\) be given by \(\lambda_1\mathbf{d}^1 + \cdots \lambda_k \mathbf{d}^k\) for some \(\lambda_1,\ldots,\lambda_k \geq 0\). Then for each \(i \in \{1,\ldots,m\}\), \({\mathbf{a}^i}^\mathsf{T} \mathbf{x}' = \sum_{j=1}^k \lambda_j \left({\mathbf{a}^i}^\mathsf{T} \mathbf{d}^j\right) = \sum_{j=1}^k \lambda_j \left({\mathbf{d}^j}^\mathsf{T} \mathbf{a}^i\right) \geq 0\). Hence, \(\mathbf{x}'\in C\), implying that \(C \supseteq \operatorname{cone}\left(\left\{ \mathbf{d}^1,\ldots, \mathbf{d}^k\right\}\right)\).
Suppose that there exists \(\mathbf{x}' \in C\backslash \operatorname{cone}\left(\left\{ \mathbf{d}^1,\ldots, \mathbf{d}^k\right\}\right)\). Then, the following system has no solution: \begin{eqnarray*} \begin{bmatrix} \mathbf{d}^1 & \cdots & \mathbf{d}^k\end{bmatrix} \begin{bmatrix} \lambda_1\\\vdots \\\lambda_k\end{bmatrix} & = & \mathbf{x}' \\ \lambda_1,\ldots,\lambda_k & \geq & 0. \end{eqnarray*} Then by Corollary 2.2, there exists \(\mathbf{y} \in \mathbb{R}^n\) such that \(\mathbf{y}^\mathsf{T}\mathbf{d}^i \geq 0\) for \(i = 1,\ldots,k\) and \(\mathbf{y}^\mathsf{T} \mathbf{x'} \lt 0\). Thus, \(\mathbf{y} \in C'\). But \(\mathbf{x}' \in C\) and \(\mathbf{y}^\mathsf{T} \mathbf{x'} \lt 0\), contradicting the claim above. Thus, \(C\backslash \operatorname{cone}\left(\left\{ \mathbf{d}^1,\ldots,\mathbf{d}^k\right\}\right)\) must be empty and the result follows.
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\}\).
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\}\).
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)\).
Let \(C \subseteq \mathbb{R}^n\) be a pointed polyhedral cone. Show that \(\mathbf{0}\) is the only extreme point of \(C\).