Describing Polyhedra by Extreme Points and Extreme Rays
John Mitchell

Let , where is an matrix, is an -vector, and is an -vector. Assume rank()= and . We look at the extreme points and extreme rays of .

Definition 1   A point is an extreme point of if there do not exist points and in and a scalar (with and ) such that .

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

Definition 2   Let . Any is a ray of .

Note: is a convex cone. A set is a cone if , implies .

A point is a ray of if and only if for any point the set .

Definition 3   A ray of is an extreme ray if there do not exist rays and a scalar (with for any and ) such that .

Proposition 2   A vector is an extreme ray of if and only if is a one-dimensional face of .

Theorem 1   If is finite then there is an optimal solution that is an extreme point.

Theorem 2   If is unbounded then has an extreme ray with .

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

where is the set of extreme points of and is the set of extreme rays of .

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

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

Proposition 3   If and rank()= then has a face of dimension and no proper face of lower dimension.

John E. Mitchell 2006-01-13