Extreme rays

Let $C\subseteq {\mathbb{R}}^n$ be a polyhedral cone. A nonzero $\mathbf{d}\in C$ is an extreme ray of $C$ if there do not exist linearly independent $\mathbf{u},\mathbf{v}\in C$ and positive scalars $\lambda$ and $\gamma$ such that $\mathbf{d}=\lambda \mathbf{u}+\gamma \mathbf{v}$.

Note that if $\mathbf{d}$ is an extreme ray, then $\lambda \mathbf{d}$ is also an extreme ray for all $\lambda >0$. We say that two extreme rays are equivalent if one is a positive scalar multiple of the other. Hence, when enumerating extreme rays of a polyhedral cone, we often enumerate one representative from each equivalent class of extreme rays. One way to achieve this is to impose a normalization condition such as restricting to unit vectors with respect to some vector norm.

Proposition 10.2. Let $C\subseteq {\mathbb{R}}^n$ be given by $\{\mathbf{x}\in {\mathbb{R}}^n:\mathbf{A}\mathbf{x}\ge \mathbf{0}\}$ for some $\mathbf{A}\in {\mathbb{R}}^{m\times n}$. Let $\mathbf{d}\in C$ be nonzero. Let ${\mathbf{A}}^{=}\mathbf{x}\ge \mathbf{0}$ denote the subsystem of $\mathbf{A}\mathbf{x}\ge \mathbf{0}$ consisting of all the inequalities active at $\mathbf{d}$. Then $\mathbf{d}$ is an extreme ray of $C$ if and only if $\mathrm{rank}({\mathbf{A}}^{=})=n-1$.

Corollary 10.3. The number of nonequivalent extreme rays of a polyhedral cone is finite.

We say that ${\mathbf{d}}^1,\dots ,{\mathbf{d}}^k$ form a complete set of extreme rays of $C$ if ${\mathbf{d}}^i$ is an extreme ray of $C$ for $i=1,\dots ,k$ and every extreme ray of $C$ is equivalent to ${\mathbf{d}}^i$ for some $i\in \{1,\dots ,k\}$.

Worked examples

1. Let $C=\{\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\in {\mathbb{R}}^2:\begin{array}{r}{x}_1+2x_2\ge 0\\ -3x_1+x_2\ge 0\end{array}\}$. Find all extreme rays of $C$ of unit length.

   Solving this problem graphically is certainly an option.

   Since $C\subseteq {\mathbb{R}}^2$, we only need to consider subsystems consisting of a single inequality.

   Setting the inequality $x_1+2x_2\ge 0$ to equality, we obtain the general solution $\lambda \left[\begin{array}{c}-2\\ 1\end{array}\right]$. Since $\left[\begin{array}{c}-2\\ 1\end{array}\right]$ also satisfies the other inequality, normalizing it to a unit vector gives the extreme ray $\left[\begin{array}{c}-\frac{2}{\sqrt{5}}\\ \frac{1}{\sqrt{5}}\end{array}\right]$.

   Setting the inequality $-3x_1+x_2\ge 0$ to equality, we obtain the general solution $\lambda \left[\begin{array}{c}1\\ 3\end{array}\right]$. Since $\left[\begin{array}{c}1\\ 3\end{array}\right]$ also satisfies the other inequality, normalizing it to a unit vector gives the extreme ray $\left[\begin{array}{c}\frac{1}{\sqrt{10}}\\ \frac{3}{\sqrt{10}}\end{array}\right]$.

2. Let ${\mathbf{d}}^1,\dots ,{\mathbf{d}}^k\in {\mathbb{R}}^n$ be such that $C=\mathrm{cone}\left(\{{\mathbf{d}}^1,\dots ,{\mathbf{d}}^k\}\right)$ is pointed. Prove that if for some $\overline{i}\in \{1,\dots ,k\}$, ${\mathbf{d}}^{\overline{i}}$ is not an extreme ray of $C$, then $C=\mathrm{cone}\left(\{{\mathbf{d}}^i:i\in \{1,\dots ,k\}\setminus \{\overline{i}\}\}\right)$.

   Without loss of generaliy, we may assume that $\overline{i}=k$.

   Since ${\mathbf{d}}^k$ is not an extreme ray, there exist linearly independent $\mathbf{u},\mathbf{v}\in C$ and scalars $\lambda ,\gamma >0$ such that $${\mathbf{d}}^k=\lambda \mathbf{u}+\gamma \mathbf{v}.$$ Let ${\alpha }_1,\dots ,{\alpha }_k\ge 0$ be scalars such that $\mathbf{u}=\sum _{i=1}^k{\alpha }_i{\mathbf{d}}^i$ and let ${\beta }_1,\dots ,{\beta }_k\ge 0$ be scalars such that $\mathbf{v}=\sum _{i=1}^k{\beta }_i{\mathbf{d}}^i$. Then, $$(1-\lambda {\alpha }_k-\gamma {\beta }_k){\mathbf{d}}^k=\sum _{i=1}^{k-1}(\lambda {\alpha }_i+\gamma {\beta }_i){\mathbf{d}}^i.$$ If $1-\lambda {\alpha }_k-\gamma {\beta }_k>0$, then $${\mathbf{d}}^k=\sum _{i=1}^{k-1}\frac{\lambda {\alpha }_i+\gamma {\beta }_i}{1-\lambda {\alpha }_k-\gamma {\beta }_k}{\mathbf{d}}^i,$$ implying that ${\mathbf{d}}^k\in \mathrm{cone}\left(\{{\mathbf{d}}^1,\dots ,{\mathbf{d}}^{k-1}\}\right)$. It follows that $C=\mathrm{cone}\left(\{{\mathbf{d}}^1,\dots ,{\mathbf{d}}^{k-1}\}\right)$.

   Suppose that $1-\lambda {\alpha }_k-\gamma {\beta }_k\le 0$. Then $$\sum _{i=1}^k{\zeta }_i{\mathbf{d}}^k=\mathbf{0}$$ where ${\zeta }_i=\lambda {\alpha }_i+\gamma {\beta }_i$ for $i=1,\dots ,k-1$, and ${\zeta }_i=1-\lambda {\alpha }_k-\gamma {\beta }_k$. The important point is that ${\zeta }_i\ge 0$ for $i=1,\dots ,k$. Note that we cannot have ${\zeta }_i=0$ for $i=1,\dots ,k-1$. Otherwise, we will have that $\mathbf{u}$ and $\mathbf{v}$ are both scalar multiples of ${\mathbf{d}}^k$, contradicting that they are linearly independent. Without loss of generality, we may assume that ${\zeta }_1>0$. Thus $$-{\zeta }_1{\mathbf{d}}^1=\sum _{i=2}^k{\zeta }_i{\mathbf{d}}^k.$$ Dividing both sides by ${\zeta }_1$ gives $$-{\mathbf{d}}^1=\sum _{i=2}^k\frac{{\zeta }_i}{{\zeta }_1}{\mathbf{d}}^k,$$ implying that $-{\mathbf{d}}^1\in C$. Since we also have ${\mathbf{d}}^1\in C$, it follows that $C$ contains the line $\{\lambda {\mathbf{d}}^1:\lambda \in \mathbb{R}\}$. By Theorem 8.6. cannot be pointed, which is a contradiction.