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}$

$\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:

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

Statistical Odds & Ends

What is Minkowski’s Representation Theorem?

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply