3 Convex geometry

3.1 Cones

3.1.1 Convex Polyhedral Cones

Fix a pair of dual real vector spaces $M$ and $N$.

Definition 3.1.1 Convex cone generated by a set

✓

For a set $S \subseteq N$, the cone generated by $S$, aka cone hull of $S$, is

\[ \operatorname{Cone}(S) := \left\{ \sum _{u \in S} \lambda _u u | \lambda _u \ge 0\right\} \]

Definition 3.1.2 Convex polyhedral cone

✓

A polyhedral cone is a set that can be written as $\operatorname{Cone}(S)$ for some finite set $S$.

Definition 3.1.3 Convex hull

✓

For a set $S \subseteq N$, the convex hull of $S$ is

\[ \operatorname{Conv}(S) := \left\{ \sum _{u \in S} \lambda _u | \lambda _u \ge 0, \sum _u \lambda _u = 1\right\} \]

Definition 3.1.4 Polytope

✓

A polytope is a set that can be written as $\operatorname{Conv}(S)$ for some finite set $S$.

3.1.2 Dual Cones and Faces

Definition 3.1.5 Dual cone

✓

Given a polyhedral cone $\sigma \subseteq N$, its dual cone is defined by

\[ \sigma ^\vee = \{ m \in M | \forall u \in \sigma , \langle m, u\rangle \ge 0\} \]

Proposition 3.1.6 Dual of a polyhedral cone

✓

If $\sigma $ is polyhedral, then its dual $\sigma ^\vee $ is polyhedral too.

Proof ▶

Classic, use Fourier-Motzkin eliminiation.

Proposition 3.1.7 Dual cone of a sumset

If $\sigma _1, \sigma _2$ are two cones, then

\[ (\sigma _1 + \sigma _2)^\vee = \sigma _1^\vee \cap \sigma _2^\vee . \]

Proof ▶

Classic. See [ 3 ] maybe.

Proposition 3.1.8 Double dual of a polyhedral cone

If $\sigma $ is polyhedral, then $\sigma ^{\vee \vee } = \sigma $.

Proof ▶

Classic. See [ 3 ] maybe.

Given $m \ne 0$ in $M$, we get the hyperplane

\[ H_m = \{ u \in N | \langle m, u\rangle = 0\} \subseteq N \]

and the closed half-space

\[ H_m^+ = \{ u \in N | \langle m, u\rangle \ge 0\} \subseteq N. \]

Definition 3.1.9 Face of a cone

✓

If $\sigma $ is a cone, then a subset of $\sigma $ is a face iff it is the intersection of $\sigma $ with some halfspace. We write this $\tau \preceq \sigma $. If furthermore $\tau \ne \sigma $, we call $\tau $ a proper face and write $\tau \prec \sigma $.

Definition 3.1.10 Edge of a cone

A dimension 1 face of a cone is called an edge.

Lemma 3.1.12 Face of a polyhedral cone

If $\sigma $ is a polyhedral cone, then every face of $\sigma $ is a polyhedral cone.

Lemma 3.1.13 Intersection of faces

If $\sigma $ is a polyhedral cone, then the intersection of two faces of $\sigma $ is a face of $\sigma $.

Proof ▶

Classic. See [ 3 ] maybe.

Lemma 3.1.14 Face of a face

A face of a face of a polyhedral cone $\sigma $ is again a face of $\sigma $.

Proof ▶

Classic. See [ 3 ] maybe.

Lemma 3.1.15

Let $\tau $ be a face of a polyhedral cone $\sigma $. If $v, w \in \sigma $ and $v + w \in \tau $, then $v, w \in \tau $.

Proof ▶

Classic. See [ 3 ] maybe.

Proposition 3.1.16 Dual cone of the intersection of halfspaces

If $\sigma = H_{m_1}^+ \cap \dots \cap H_{m_s}^+$, then

\[ \sigma ^\vee = \operatorname{Cone}(m_1, \dots , m_s). \]

Proof ▶

Classic. See [ 3 ] maybe.

Proof ▶

Classic. See [ 3 ] maybe.

Proof ▶

Classic. See [ 3 ] maybe.

Definition 3.1.19 Dual face

Given a cone $\sigma $ and a face $\tau \preceq \sigma $, the dual face to $\tau $ is

\[ \tau ^* := \sigma ^\vee \cap \tau ^\perp \]

Proposition 3.1.20 The dual face is a face of the dual

If $\tau \preceq \sigma $, then $\tau ^* \preceq \sigma ^\vee $.

Proof ▶

Classic. See [ 3 ] maybe.

Proposition 3.1.21 The double dual of a face

If $\tau \preceq \sigma $, then $\tau ^{**} = \tau $.

Proof ▶

Classic. See [ 3 ] maybe.

Proposition 3.1.22 The dual of a face is antitone

If $\tau ' \preceq \tau \preceq \sigma $, then $\tau ' \preceq \tau $.

Proof ▶

Classic. See [ 3 ] maybe.

Proposition 3.1.23 The dimension of the dual of a face

If $\tau \preceq \sigma $, then

\[ \dim \tau + \dim \tau ^* = \dim N. \]

Proof ▶

Classic. See [ 3 ] maybe.

3.1.3 Relative Interiors

Definition 3.1.24 Relative interior

✓

The relative interior, aka intrinsic interior, of a cone $\sigma $ is the interior of $\sigma $ as a subset of its span.

Lemma 3.1.25 The relative interior in terms of the inner product

For a cone $\sigma $,

\[ u \in \operatorname{Relint}(\sigma ) \iff \forall m \in \sigma ^\vee \setminus \sigma ^\perp , \langle m, u\rangle {\gt} 0 \]

Proof ▶

Classic. See [ 3 ] maybe.

Lemma 3.1.26 Relative interior of a dual face

If $\tau \preceq \sigma $ and $m \in \sigma ^\vee $, then

\[ m \in \operatorname{Relint}(\tau ^*) \iff \tau = H_m \cap \sigma \]

Proof ▶

Classic. See [ 3 ] maybe.

Lemma 3.1.27 Minimal face of a cone

If $\sigma $ is a cone, then $W := \sigma \cap (-\sigma )$ is a subspace. Furthermore, $W = H_m \cap \sigma $ whenever $m \in \operatorname{Relint}(\sigma ^\vee )$.

Proof ▶

Classic. See [ 3 ] maybe.

3.1.4 Strong Convexity

Definition 3.1.28 Salient cones

✓

A cone $\sigma $ is salient, aka pointed or strongly convex, if $\sigma \cap (-\sigma ) = \{ 0\} $.

Proposition 3.1.29 Alternative definitions of salient cones

The following are equivalent

$\sigma $ is salient
$\{ 0\} \preceq \sigma $
$\sigma $ contains no positive dimensional subspace
$\dim \sigma ^\vee = \dim N$

Proof ▶

Classic. See [ 3 ] maybe.

3.1.5 Separation

Lemma 3.1.30 Separation lemma

Let $\sigma _1, \sigma _2$ be polyhedral cones meeting along a common face $\tau $. Then

\[ \tau = H_m \cap \sigma _1 = H_m \cap \sigma _2 \]

for any $m \in \operatorname{Relint}(\sigma _1^\vee \cap (-\sigma _2)^\vee )$.

Proof ▶

See [ 1 ] .

3.1.6 Rational Polyhedral Cones

Let $M$ and $N$ be dual lattices with associated vector spaces $M_{\mathbb R}:= M \otimes _{\mathbb Z}{\mathbb R}, N_{\mathbb R}:= N \otimes _{\mathbb Z}{\mathbb R}$.

Definition 3.1.31 Rational cone

A cone $\sigma \subseteq N_{\mathbb R}$ is rational if $\sigma = \operatorname{Cone}(S)$ for some finite set $S \subseteq N$.

Lemma 3.1.32 Faces of a rational cone

If $\tau \preceq \sigma $ is a face of a rational cone, then $\tau $ itself is rational.

Proof ▶

Classic. See [ 3 ] maybe.

Lemma 3.1.33 The dual of a rational cone

$\sigma ^\vee $ is a rational cone iff $\sigma $ is.

Proof ▶

Classic. See [ 3 ] maybe.

Definition 3.1.34 Ray generator

If $\rho $ is an edge of a rational cone $\sigma $, then the monoid $\rho \cap N$ is generated by a unique element $u_\rho \in \rho \cap N$, which we call the ray generator of $\rho $.

Definition 3.1.35 Minimal generators

The minimal generators of a rational cone $\sigma $ are the ray generators of its edges.

Lemma 3.1.36 A rational cone is generated by its minimal generators

A salient convex rational polyhedral cone is generated by its minimal generators.

Proof ▶

Classic. See [ 3 ] maybe.

Definition 3.1.37 Regular cone

A salient rational polyhedral cone $\sigma $ is regular, aka smooth, if its minimal generators form part of a ${\mathbb Z}$-basis of $N$.

Definition 3.1.38 Simplicial cone

A salient rational polyhedral cone $\sigma $ is simplicial if its minimal generators are ${\mathbb R}$-linearly independent.

3.1.7 Semigroup Algebras and Affine Toric Varieties

Definition 3.1.39 Dual lattice of a cone

If $\sigma \subseteq N_{\mathbb R}$ is a polyhedral cone, then the lattice points

\[ S_\sigma := \sigma ^\vee \cap M \]

form a monoid.

Proposition 3.1.40 Gordan’s lemma

$S_\sigma $ is finitely generated as a monoid.

Proof ▶

See [ 1 ] .

Definition 3.1.41 Affine toric variety of a rational polyhedral cone

$U_\sigma := \operatorname{Spec}{\mathbb C}[S_\sigma ]$ is an affine toric variety.

Theorem 3.1.42 Dimension of the affine toric variety of a rational polyhedral cone

\[ \dim U_\sigma = \dim N \iff \text{ the torus of $U_\sigma $ is } T_N = N \otimes _[{\mathbb Z}] {\mathbb C}^* \iff \sigma \text{ is salient}. \]

Proof ▶

See [ 1 ] .

Proposition 3.1.43 The irreducible elements of the dual lattice of a cone

If $\sigma \subseteq N_{\mathbb R}$ is salient of maximal dimension, then the irreducible elements of $S_\sigma $ are precisely the minimal generators of $\sigma ^\vee $.

Proof ▶

See [ 1 ] .