9.6. Cones III#

9.6.1. Polyhedral Cones#

Definition 9.37 (Polyhedral cone)

The conic hull of a finite set of points is known as a polyhedral cone.

In other words, let \(\{ \bx_1, \bx_2, \dots, \bx_m \}\) be a finite set of points. Then

\[ C = \cone \{ \bx_1, \bx_2, \dots, \bx_m \} \]

is known as a polyhedral cone.

Theorem 9.65

A polyhedral cone is nonempty, closed and convex.

Proof. Since it is the conic hull of a nonempty set, hence it is nonempty and convex.

Theorem 9.131 shows that the conic hulls of a finite set of points are closed.

Remark 9.7 (Polyhedral cone alternative formulations)

Following are some alternative definitions of a polyhedral cone.

  1. A cone is polyhedral if it is the intersection of a finite number of half spaces which have \(\bzero\) on their boundary.

  2. A cone \(C\) is polyhedral if there is some matrix \(\bA\) such that \(C = \{ \bx \in \RR^n \ST \bA \bx \succeq \bzero \}\).

  3. A cone is polyhedral if it is the solution set of a system of homogeneous linear inequalities.

9.6.1.1. Polar Cones#

Theorem 9.66 (Polar cone of a polyhedral cone)

Let the ambient space by \(\RR^n\). Let \(\bA \in \RR^{m \times n}\). Let

\[ C = \{\bx \in \RR^n \ST \bA \bx \preceq \bzero \}. \]

Then

\[ C^{\circ} = \{ \bA^T \bt \ST \bt \in \RR^m_+ \}. \]

We note that the set \(C\) is a convex cone. It is known as the convex polyhedral cone.

Proof. We note that \(\by \in C^{\circ}\) if and only if \(\bx^T \by \leq 0\) for every \(\bx\) satisfying \(\bA \bx \preceq \bzero\).

  1. Thus, for every \(\bx \in \RR^n\), the statement \(\bA \bx \preceq \bzero \implies \bx^T \by \leq 0\) is true.

  2. By Farkas’ lemma (Theorem 10.55), it is equivalent to the statement that there exists \(\bt \succeq \bzero\) such that \(\bA^T \bt = \by\).

  3. Thus,

    \[ C^{\circ} = \{ \bA^T \bt \ST \bt \in \RR^m_+ \}. \]