Recession cone of a polyhedron

Let \(P \subseteq \mathbb{R}^n\) be a nonempty polyhedron. The recession cone (or characteristic cone) of \(P\), denoted by \(\operatorname{recc}(P)\), is the set \[\left\{ \mathbf{d} \in \mathbb{R}^n : \mathbf{x} + \lambda \mathbf{d} \in P \text{ for all } \mathbf{x} \in P \text{ and for all } \lambda \geq 0\right\}.\]

Proposition 10.4. Let \(P = \left\{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right\}\) where \(\mathbf{A} \in \mathbb{R}^{m\times n}\) and \(\mathbf{b} \in \mathbb{R}^m\). Then \(\operatorname{recc}(P) = \left\{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{0} \right\}\).

Let \(P \subseteq \mathbb{R}^n\) be a nonempty polyhedron. A nonzero \(\mathbf{d} \in \mathbb{R}^n\) is called an extreme ray of \(P\) if \(\mathbf{d}\) is an extreme ray of \(\operatorname{recc}(P)\).

Theorem 10.5. Let \(P = \left\{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right\}\) be nonempty and pointed. Let \(\mathbf{c} \in \mathbb{R}^n\). The linear programming problem \(\min\{ \mathbf{c}^\mathsf{T} \mathbf{x} : \mathbf{x} \in P\}\) is unbounded if and only if there exists an extreme ray \(\mathbf{d}\) of \(P\) such that \(\mathbf{c}^\mathsf{T}\mathbf{d} \lt 0\).

Corollary 10.6. Let \(P\) be a pointed polyhedron. Let \(\mathbf{d}^1,\ldots, \mathbf{d}^k\) be a complete set of extreme rays of \(\operatorname{recc}(P)\). Then \(\operatorname{recc}(P) = \operatorname{cone}\left( \left\{\mathbf{d}^1,\ldots, \mathbf{d}^k \right\} \right)\).

The proof of this corollary is left as an exercise.

Note that the assumption that \(P\) be pointed cannot be dropped. For example, let \(P = \left\{ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} : x_1 \geq 0,~x_2\in \mathbb{R}\right\}\). Note that \(\operatorname{recc}(P) = P\). A complete set of extreme rays of \(\operatorname{recc}(P)\) is given by \(\mathbf{d}^1 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\) and \(\mathbf{d}^2 = \begin{bmatrix} 0 \\ -1 \end{bmatrix}\). However, \(\operatorname{cone}\left(\left\{\mathbf{d}^1, \mathbf{d}^2 \right\}\right) = \left\{ \begin{bmatrix} 0 \\ x_2 \end{bmatrix} : x_2\in \mathbb{R}\right\} \neq \operatorname{recc}(P)\).

Worked examples

1. Prove that for a polyhedron \(P\), \(\operatorname{recc}(P)\) is also given by \(\left\{ \mathbf{d} \in \mathbb{R}^n : \mathbf{x} + \mathbf{d} \in P \text{ for all } \mathbf{x} \in P\right\}.\)

   Let \(C = \left\{ \mathbf{d} \in \mathbb{R}^n : \mathbf{x} + \mathbf{d} \in P \text{ for all } \mathbf{x} \in P\right\}.\) It suffices to show that \(C \subseteq \operatorname{recc}(P)\).

   Let \(P\) defined by a minimal system \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\). That is, for each inequality \(\mathbf{a}^\mathsf{T}\mathbf{x} \geq \beta\) in the system \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\), there is some element of \(P\) at which it is active. (If an inequality \(\mathbf{a}^\mathsf{T}\mathbf{x} \geq \beta\) is active at no element of \(P\), we can change \(\beta\) to the optimal value of \(\min \{ \mathbf{a}^\mathsf{T} \mathbf{x} : \mathbf{x} \in P\}\).

   Let \(\mathbf{d} \in C\). Consider an inequality \(\mathbf{a}^\mathsf{T}\mathbf{x} \geq \beta\) in \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\). Say it is active at \(\mathbf{x}^* \in P\). Now, \(\mathbf{x}^* + \mathbf{d} \in P\). Thus, we must have \(\mathbf{a}^\mathsf{T}\mathbf{d} \geq 0\), implying that \(\mathbf{A}\mathbf{d} \geq \mathbf{0}\). Hence, if \(\mathbf{x}\) and \(\mathbf{x} + \mathbf{d}\) are in \(P\), then \(\mathbf{x} + \lambda\mathbf{d} \in P\) for all \(\lambda \geq 1\). Furthermore, by convexity of \(P\), the line segment between \(\mathbf{x}\) and \(\mathbf{x}+\mathbf{d}\) also lie in \(P\). It follows that if \(\mathbf{x} \in P\), then \(\mathbf{x} + \lambda \mathbf{d}\in P\) for \(\lambda \geq 0\). Hence, \(\mathbf{d} \in \operatorname{recc}(P)\) as desired.

2. Show that if \(P\subseteq \mathbb{R}^n\) is a nonempty polytope, then \( \operatorname{recc}(P) = \{ \mathbf{0}\}.\)

   Suppose that there exists nonzero \(\mathbf{d} \in \operatorname{recc}{P}\). The linear programming problem \(\max \{\mathbf{d}^\mathsf{T}\mathbf{x} : \mathbf{x} \in P\}\) cannot be infeasible nor unbounded since \(P\) is a nonempty polytope, Hence, by the Fundamental Theorem of Linear Programming, it has an optimal solution. In addition, \(P\) has at least one extreme point by Theorem 9.1. It follows from Theorem 8.4, that there is an optimal solution \(\mathbf{x}^*\) that is an extreme point of \(P\). Then \(\mathbf{x}^* + \mathbf{d} \in P\). But \(\mathbf{x}^* + \mathbf{d}\) is a feasible solution with objective function value \(\mathbf{d}^\mathsf{T} \mathbf{x}^* + \mathbf{d}^\mathsf{T}\mathbf{d} > \mathbf{d}^\mathsf{T} \mathbf{x}^*\), contradicting the optimality of \(\mathbf{x}^*\).

3. Prove Corollary 10.6.

   Since \(\mathbf{d}^i \in \operatorname{recc}(P)\) for \(i = 1,\ldots,k\) and \(\operatorname{recc}(P)\) is a cone, \(\operatorname{cone}\left( \left\{\mathbf{d}^1,\ldots, \mathbf{d}^k \right\} \right) \subseteq \operatorname{recc}(P)\).

   For the reverse inclusion, let \(P\) be given by \(\left\{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right\}\). Suppose that there exists \(\mathbf{d} \in \operatorname{recc}(P) \setminus \operatorname{cone}\left( \left\{\mathbf{d}^1,\ldots, \mathbf{d}^k \right\} \right)\). Then the system \begin{align*} \sum_{i=1}^k \lambda_i \mathbf{d}^i & = \mathbf{d} \\ \lambda_1,\ldots,\lambda_k & \geq 0 \end{align*} has no solution. By Corollary 2.2, there exist \(\mathbf{y}\) such that \(\mathbf{y}^\mathsf{T}\mathbf{d}^i \geq 0\) for \(i = 1,\ldots,k\) and \(\mathbf{y}^\mathsf{T}\mathbf{d} \lt 0\). The linear programming problem \begin{align*} \min \ & \mathbf{y}^\mathsf{T}\mathbf{d} \\ \text{s.t.} \ & \mathbf{d} \in \operatorname{recc}(P) \end{align*} is then unbounded. By Theorem 10.5, there is an extreme ray \(\mathbf{d}'\) of \(\operatorname{recc}(P)\) such that \(\mathbf{y}^\mathsf{T}\mathbf{d}' \lt 0\). As \(\mathbf{d}^1,\ldots,\mathbf{d}^k\) form a complete set of extreme rays of \(\operatorname{recc}(P)\), \(\mathbf{d}'\) must be a positive scalar multiple of \(\mathbf{d}^i\) for some \(i \in \{1,\ldots,k\}\). This contradicts that \(\mathbf{y}^\mathsf{T}\mathbf{d}^i \geq 0\).

4. Let \(P\subseteq \mathbb{R}^n\) be a polyhedron. Show that \(P + \operatorname{recc}(P) = P\) where the sum denotes Minkowski addition; i.e. \(U+V = \{ \mathbf{x}+\mathbf{y} : \mathbf{x} \in U,\, \mathbf{y} \in V\}.\)

   Let \(P\) be given by \(\left\{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right\}\). By Proposition 10.4, \(\operatorname{recc}(P) = \left\{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{0} \right\}\). Since \(\mathbf{0} \in \operatorname{recc}(P)\), we have \(P \subseteq P + \operatorname{recc}(P).\)

   For the reverse inclusion, consider \(\mathbf{x} \in P + \operatorname{recc}(P).\) Then \(\mathbf{x} = \mathbf{p} + \mathbf{d}\) for some \(\mathbf{p} \in P\) and \(\mathbf{d} \in \operatorname{recc}(P)\). Hence, \[\mathbf{A}\mathbf{x} = \mathbf{A}\left(\mathbf{p} + \mathbf{d}\right) = \mathbf{A}\mathbf{p} + \mathbf{A}\mathbf{d} \geq \mathbf{b} + \mathbf{0} = \mathbf{b},\] implying that \(\mathbf{x} \in P\). Hence, \(P + \operatorname{recc}(P) \subseteq P.\)