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 $\{{\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_m\}$ be a finite set of points. Then

$$C=\mathrm{cone}\{{\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_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 $\mathbf{0}$ on their boundary.

2. A cone $C$ is polyhedral if there is some matrix $\mathbf{A}$ such that $C=\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}⪰\mathbf{0}\}$.

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 ${\mathbb{R}}^n$. Let $\mathbf{A}\in {\mathbb{R}}^{m\times n}$. Let

$$C=\{\mathbf{x}\in {\mathbb{R}}^n|\mathbf{A}\mathbf{x}⪯\mathbf{0}\}.$$

Then

$$C^{\circ }=\{{\mathbf{A}}^T\mathbf{t}|\mathbf{t}\in {\mathbb{R}}_{+}^m\}.$$

We note that the set $C$ is a convex cone. It is known as the convex polyhedral cone.

Proof. We note that $\mathbf{y}\in C^{\circ }$ if and only if ${\mathbf{x}}^T\mathbf{y}\le 0$ for every $\mathbf{x}$ satisfying $\mathbf{A}\mathbf{x}⪯\mathbf{0}$.

1. Thus, for every $\mathbf{x}\in {\mathbb{R}}^n$, the statement $\mathbf{A}\mathbf{x}⪯\mathbf{0}⟹{\mathbf{x}}^T\mathbf{y}\le 0$ is true.

2. By Farkas’ lemma (Theorem 10.55), it is equivalent to the statement that there exists $\mathbf{t}⪰\mathbf{0}$ such that ${\mathbf{A}}^T\mathbf{t}=\mathbf{y}$.

3. Thus,

   $$C^{\circ }=\{{\mathbf{A}}^T\mathbf{t}|\mathbf{t}\in {\mathbb{R}}_{+}^m\}.$$