Minkowski’s representation theorem is a fundamental result on how polyhedra can be represented.
- 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
- 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).