**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 .*

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