Describing Polyhedra by Extreme Points and Extreme Rays
John Mitchell

Let $P:=\{x \in \Re^n: Ax \leq b\}$, where $A$ is an $m \times n$ matrix, $x$ is an $n$-vector, and $b$ is an $m$-vector. Assume rank($A$)=$n$ and $P \neq \emptyset$. We look at the extreme points and extreme rays of $P$.

Definition 1   A point $x\in P$ is an extreme point of $P$ if there do not exist points $x^1$ and $x^2$ in $P$ and a scalar $\lambda$ (with $x^1\neq x^2$ and $0<\lambda < 1$) such that $x=\lambda x^1 + (1-\lambda) x^2$.

Proposition 1   $x$ is an extreme point of $P$ if and only if $x$ is a zero-dimensional face of $P$.

Definition 2   Let $P^0:= \{r \in \Re^n : Ar \leq 0\}$. Any $r \in P^0 \setminus \{0\}$ is a ray of $P$.

Note: $P^0$ is a convex cone. A set $K$ is a cone if $x \in K$, $\lambda >0$ implies $\lambda x \in K$.

A point $r\in \Re^n$ is a ray of $P$ if and only if for any point $x\in P$ the set $\{y \in \Re^n: y = x+\lambda r, \lambda \geq 0\} \subseteq P$.

Definition 3   A ray $r$ of $P$ is an extreme ray if there do not exist rays $r^1,r^2 \in P^0$ and a scalar $\mu$ (with $r^1 \neq \lambda r^2$ for any $\lambda >0$ and $0<\mu <1$) such that $r = \mu r^1 + (1-\mu) r^2$.

Proposition 2   A vector $r$ is an extreme ray of $P$ if and only if $\{ \lambda r : r \geq 0\}$ is a one-dimensional face of $P^0$.

Theorem 1   If $\max\{c^Tx : x\in P\}$ is finite then there is an optimal solution that is an extreme point.

Theorem 2   If $\max\{c^Tx : x\in P\}$ is unbounded then $P$ has an extreme ray $r^*$ with $c^Tr^*>0$.

Theorem 3 (Minkowski Resolution Theorem.)   The polyhedron $P$ can be represented as

$$P = \{x \in \Re^n: x = \sum_{i \in K} \lambda_k x^k + \sum_... ...\; \forall k \in K, \;\; \mu_j \geq 0 \;\; \forall j \in J\},$$

where $\{x^k\}_{k\in K}$ is the set of extreme points of $P$ and $\{r^j\}_{j\in J}$ is the set of extreme rays of $P$.

This theorem is the basis for decomposition algorithms for linear programming.

Note that if we drop the assumption about the rank of $A$, we get the following proposition:

Proposition 3   If $P \neq \emptyset$ and rank($A$)=$n-k$ then $P$ has a face of dimension $k$ and no proper face of lower dimension.