User:MWinter4/Minkowski-Weyl theorem

In geometry, the Minkowski-Weyl theorem asserts that the two natural ways of defining convex polytopes are in fact equivalent. The intuitive notion of a convex polytope (has a convex set with piecewise linear boundary) is usually formalized in one of the following two ways:

1. as a V-polytope, which is the convex hull of finitely many points.
2. as an H-polytope, which is a bounded set obtained as the intersection of finitely many halfspaces.

The Minkowski-Weyl theorem states that V-polytopes and H-polytopes describe the exact same class of convex sets. It is therefore justified and more common to use the term polytope without a V- or H-prefix and speak of their V-representations (or vertex representations) and H-representations (or halfspace representations) instead.

Despite its intuitive character and apparent simplicity, the Minkowski-Weyl theorem is not trivial to prove. One usually distinguishes the "easy" and the "hard" direction of the theorem. Given an H-representation, constructing a corresponding V-representation is possible from first principles rather directly. In contrast, to go from an H-representation to a V-representation requires a level of familiarity with certain standard tools, such as either Farkas' lemma, Fourier-Motzkin elimination, the finite-dimensional Krein-Milman theorem or a pre-developed theory of polar duality.

The three versions of the theorem (for cones, polytopes and polyhedra) can be proven in very similar ways, and usually it is sufficient to establish one of them and obtain the others as corollaries. Often the version for cones is proven first.

While the convex hull of finitely many points is always bounded, this is not the case for the intersection of finitely many halfspaces. Without the extra assumption of boundedness, such an intersection is also known as an H-polyhedron. The corresponding notion of V-polyhedron is defined as the Minkowski sum of a V-polytope with a convex cone. A corresponding version of the Minkowski-Weyl theorem asserts that V- and H-polyhedra define the exact same class of polyhedra. Likewise, there are versions of the theorem for cones.

For cones

A convex cone $C\subset {\mathbb {R}}^{d}$ is a V-cone if it is generated from finitly many vectors $v_{1},...,v_{n}$:

$C=\operatorname {cone} (v_{1},...,v_{n})={\Big \{}\sum _{i}\lambda _{i}v_{i}\,{\Big \vert }\,\lambda _{i}\geq 0{\Big \}}.$

In contrast, $C$ is an H-cone if it is the intersection if finitely many halfspaces $H_{i}:=\{\langle x,a_{i}\rangle \leq 0\}$, that is, can be written in the form

$C=\bigcap _{i}H_{i}={\big \{}x\in {\mathbb {R}}^{d}\,{\big \vert }\,\langle x,a_{i}\rangle \leq 0{\text{ for all }}i\in \{1,...,m\}{\big \}}.$

Polar duality

Given that V-cones are also H-cones, the other direction follows via polar duality. In fact, if $C$ is an H-cone, then the polar cone $C^{\vee }$ is a V-cone, and hence an H-cone by the already established direction. The double-polar $C^{\vee \vee }=C$, which is the original cone, is then a V-cone.

Proof using Fourier-Motzkin elimination

• Fourier-Motzkin elimination

Proof using Farkas' lemma

• Farkas' lemma