**Minkowski’s representation theorem** is a fundamental result on how polyhedra can be represented.

Preliminary definitions

- In , a
**polyhedron** is a set which can be described as , where and .
- is an
**extreme point** of a polyhedron if there do not exist such that .
- is a
**ray** of a polyhedron if is non-zero and . Let denote the set of rays of .
- is an
**extreme ray** of a polyhedron if there do not exist linearly independent such that .

It can be shown that for any polyhedron, the number of extreme points and extreme rays is finite (proof in Reference 1).

Minkowski’s representation theorem

**Minkowski’s representation theorem** essentially says that a polyhedron can be described by its extreme points and extreme rays.

**Theorem:** If is non-empty and , then

where and are the set of extreme points and extreme rays of respectively.

A proof of this theorem can be found in Reference 1. As a special case, if the polyhedron is bounded, then it does not have any extreme rays and so any point in the polyhedron can be described as a convex combination of its extreme points.

Minkowski representation & projection

The theorem tells us that a polyhedron can be expressed as the set of convex combination of its extreme points and rays. For notational convenience, let denote the extreme points and extreme rays of the polyhedron , and let if is an extreme point, and otherwise. The **Minkowski representation** of the polyhedron consists of variables , one for each extreme point/ray:

and the **Minkowski projection** defined by

You can think of the Minkowski representation as expressing each point in the polyhedron in terms of “coordinates” associated with the extreme points/rays.

Note that these coordinates are not unique: each point in the polyhedron may be associated with more than one set of coordinates. For example, consider the bounded triangle in with coordinates , and . The point can be written as

or

References:

- Nemhauser, G., and Wolsey, L. (1988). Integer and Combinatorial Optimization. (Chapter I.4).
- Tebboth, J. R. (2001). A Computational Study of Dantzig-Wolfe Decomposition. (Section 3.3).

### Like this:

Like Loading...

*Related*