Definitions

An \(H\)-polyhedron is an intersection of closed halfspaces. A set \(P \subseteq \mathbb{R}^d\) is an \(H\)-polyhedron if it can be written as \[ P=P(A,z)=\{x\in \mathbb{R}^d: Ax \leq z\} \] for some matrix \(A\in \mathbb{R}^{m\times d}\) and vector \(z\in \mathbb{R}^m\).

A cone is a nonempty set \(C\subseteq \mathbb{R}^d\) such that for any finite collection of vectors in \(C\), all linear combinations with nonnegative coefficients are also contained in \(C\). In other words, if \(y_1,\dots,y_k\in C\) and \(\lambda_i\geq0\), then \[ \lambda_1y_1+\cdots+\lambda_ky_k\in C. \] and in particular, every cone contains 0.

Given a subset \(Y\subseteq \mathbb{R}^d\), the conical hull (or positive hull) of \(Y\), denoted \(\operatorname{cone}(Y)\), is the intersection of all cones containing \(Y\). Equivalently, \[ \operatorname{cone}(Y) = \{\lambda_1y_1+\cdots+\lambda_ky_k: y_1,\dots,y_k\in Y,\ \lambda_i\geq0\}. \] If \(Y = \varnothing\), then we define \(\operatorname{cone}(Y) = \{0\}\).

Given two sets \(P,Q\subseteq \mathbb{R}^d\), the vector sum (or Minkowski sum) of \(P\) and \(Q\) is the set formed by adding every vector in \(P\) to every vector in \(Q\). It is defined as \[ P+Q=\{x+y:x\in P,\ y\in Q\}. \]

A \(V\)-polyhedron is a finitely generated convex-conical combination. A set \(P\subseteq\mathbb{R}^d\) is a \(V\)-polyhedron if it can be written as \[ P=\operatorname{conv}(V)+\operatorname{cone}(Y) \] for some finite sets of vectors \(V\subseteq\mathbb{R}^d\) and \(Y\subseteq\mathbb{R}^d\). In other words, it is the Minkowski sum of a convex hull of finitely many points and a cone generated by finitely many vectors.

A \(V\)-polytope is a \(V\)-polyhedron that is bounded. Equivalently, it is a set that can be written as the convex hull of a finite set of points: \[ P=\operatorname{conv}(V). \] A \(V\)-polytope contains no ray of the form \[ \{u+tv:t\geq0\} \] where \(v\neq0\).