What is Minkowski’s Representation Theorem?

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

Preliminary definitions

  • In \mathbb{R}^n, a polyhedron is a set which can be described as \mathcal{P} = \{ x \in \mathbb{R}^n: Ax \leq b\}, where A \in \mathbb{R}^{m \times n} and b \in \mathbb{R}^m.
  • x \in \mathcal{P} is an extreme point of a polyhedron \mathcal{P} if there do not exist x_1, x_2 \in \mathcal{P} such that x = \frac{1}{2}(x_1 + x_2).
  • r \in \mathbb{R}^n is a ray of a polyhedron \mathcal{P} = \{ x \in \mathbb{R}^n: Ax \leq b\} if r is non-zero and Ar \leq 0. Let \mathcal{P}^{ray} denote the set of rays of \mathcal{P}.
  • r \in \mathcal{P}^{ray} is an extreme ray of a polyhedron \mathcal{P} if there do not exist linearly independent r_1, r_2 \in \mathcal{P}^{ray} such that r = \frac{1}{2}(r_1 + r_2).

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 \mathcal{P} = \{ x \in \mathbb{R}^n: Ax \leq b\} is non-empty and \text{rank}(A) = n, then

\begin{aligned} \mathcal{P} = \bigg\{ x \in \mathbb{R}^n: &x = \sum_{k \in K} \lambda_k x_k + \sum_{j \in J} \mu_j r_j, \\  &\sum_{k \in K} \lambda_k = 1, \lambda_k \geq 0 \;\forall k, \mu_j \geq 0 \;\forall j  \bigg\}, \end{aligned}

where \{ x_k \}_{k \in K} and \{ r_j\}_{j \in J} are the set of extreme points and extreme rays of \mathcal{P} 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 x_1, \dots, x_K denote the extreme points and extreme rays of the polyhedron \mathcal{P}, and let \delta_k = 1 if x_k is an extreme point, and \delta_k = 0 otherwise. The Minkowski representation of the polyhedron \mathcal{P} \subseteq \mathbb{R}^n consists of variables \lambda_1, \dots, \lambda_K, one for each extreme point/ray:

\begin{aligned} \mathcal{P}^{Mk} = \left\{ \lambda \in \mathbb{R}^K : \sum_{k = 1}^K \delta_k \lambda_k = 1, \lambda \geq 0 \right\}, \end{aligned}

and the Minkowski projection \pi^{Mk}: \mathbb{R}^K \mapsto \mathbb{R}^n defined by

\begin{aligned} \pi^{Mk}(\lambda) = \sum_{k=1}^K \lambda_k x_k. \end{aligned}

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 \mathbb{R}^2 with coordinates \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \begin{pmatrix} 5 \\ 1 \end{pmatrix} and \begin{pmatrix} 1 \\ 5 \end{pmatrix}. The point \begin{pmatrix} 2 \\ 2 \end{pmatrix} can be written as

\begin{aligned} \begin{pmatrix} 2 \\ 2 \end{pmatrix} = 2 \begin{pmatrix} 1 \\ 1 \end{pmatrix} + 0 \begin{pmatrix} 5 \\ 1 \end{pmatrix} + 0 \begin{pmatrix} 1 \\ 5 \end{pmatrix}, \end{aligned}

or

\begin{aligned} \begin{pmatrix} 2 \\ 2 \end{pmatrix} = 0 \begin{pmatrix} 1 \\ 1 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 5 \\ 1 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 1 \\ 5 \end{pmatrix}. \end{aligned}

References:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s