Theoretical background

A nonempty set $C$ of points in a Euclidean space is called a (convex) cone if $\lambda x + \mu y\in C$ whenever $x,y\in C$ and $\lambda ,\mu \geq 0$. A cone $C$ is polyhedral if

$$C=\{x \vert Ax\leq 0\}$$

for some matrix $A$, i.e. if $C$ is the intersection of finitely many linear half-spaces. Results from the linear programming theory [SCH86] shows that the concepts of polyhedral and finitely generated are equivalent.

Theorem 1   (Farkas-Minkowski-Weyl) A convex cone is polyhedral if and only if it is finitely generated.

A short definition of a polyhedra may be a finitely generated convex cone but in fact we are talking about the geometric representation of a list of constraints provided as a linear system of equations and inequalities.

Definition 1   (Polyhedron) A convex polyhedron if it is the set of solutions to a finite system of linear inequalities. It is called a convex polytope if it is a convex polyhedron and it is bounded. When a convex polyhedron (or polytope) has dimension $k$, it is called a $k$-polyhedron ($k$-polytope).

Hence, a set $P$ of vectors in $R^{n}$ is called a (convex) polyhedron if:

$$P=\{x\vert Ax\leq b\}$$

for some matrix $A$ and a vector $b$, i.e $P$ is the intersection of finitely many affine half-spaces. The concept of polyhedron and polytope are related by the means of the decomposition theorem for polyhedra.

Theorem 2   (Decomposition theorem for polyhedra) A set $P$ of vectors in a Euclidean space is a polyhedron, if and only if $P=Q+C$ for some polytope $Q$ and some polyhedral cone $C$.

For a set of vectors $a_{1},\cdots,a_{n}$, if a vector $b$ does not belong to the cone generated by these vectors, then there exists a hyperplane separating $b$ from from $a_{1},\cdots,a_{n}$. This result has also been formulated in the Farkas' lemma. A variant of this result is the following:

Lemma 1   Let $A$ be a matrix and let $b$ be a vector. Then the system $A x\leq b$ of linear inequalities has a solution $x$, if and only of $y b\geq 0$ for each row vector $y \geq 0$ with $y A = 0$.

In Polylib the decomposition theorem is extensively used (in its extended form for polyhedra). A polyhedron $P$ can be represented by a set of inequalities (usually, implicit equalities are represented in a separate matrix): $P=\{x\vert Ax=b, Cx\geq d\}$, this representation is called implicit. From the Minkovski characterization, we know that $P$ has a dual representation, called the parametric representation.

$$P=\{x \vert x=L\lambda +R\mu +V\nu, \mu, \nu \geq 0, \sum \nu=1\}$$

Hence, each point of $P$ can be expressed as a sum of:

• a linear combination of so called lines (columns of matrix $L$),
• a convex combination of vertices (columns of matrix $V$), and
• a positive combination of extremal rays (columns of matrix $R$).

Although the polyhedra theory cannot be detailed here, we review a set of important concepts that are used when manipulating polyhedra. For a more precise description, please refer to [SCH86,Wil93].

• The characteristic cone of a polyhedron $P=\{x \vert Ax\leq b\}$ is the polyhedral cone

  
  

  $$char.cone(P)=\{y\vert x+y\in P, \forall x\in P\}=\{y\vert Ay\leq 0\}\quad .$$
  
  

  Sometimes the characteristic cone is called the recession cone of $P$. If $P=Q+C$, with $Q$ a polytope an $C$ a polyhedral cone, then $C=char.cone(P)$ .

• The lineality space of $P=\{x \vert Ax\leq b\}$ is the linear space

  
  

  $$lin.space(P)=char.cone(P)\cap -char.cone(P)=\{y\vert Ay=0\}\quad .$$
  
  
  If the lineality space has dimension zero, $P$ is said to be pointed.

• A supporting hyperplane of $P=\{x \vert Ax\leq b\}$ is the affine hyperplane described by $\{x\vert cx=\delta \}$ where $c$ is a nonzero vector and $\delta =\max\{cx\vert Ax\leq b\}$.

• A subset $F$ of a polyhedron $P=\{x \vert Ax\leq b\}$ is called a face if $F=P$ or if $F$ is the intersection of $P$ with a supporting hyperplane of $P$. In other words $F$ is a face if and only if there is a vector $c$ for which $F$ is the set of vectors attaining $max\{cx\vert x\in P\}$ provided that this maximum is finite.

  A alternative description of a face is the nonempty subset $F$:
  

  $$F=\{x\in P\vert A' x=b'\}$$
  
  
  for some subsystem $A' x\leq b'$ of $A x\leq b$.

• The faces of a polyhedron $P$ have the following important properties:
  • $P$ has finitely many faces;
  • each face is a nonempty polyhedron;
  • if $F$ is a face of $P$ and $F' \subseteq F$, then: $F'$ is a face of $P$ if and only if $F'$ is a face of $F$.
• A facet of $P$ is a maximal face distinct from $P$. In other words if there is no redundant inequality in the polyhedron definition system: $A x\leq b$ then there exists a one-to-one correspondence between the facets of $P$ and the inequalities given by
  
  $$F=\{x\in P\vert a_{i}x=b_{i}\}$$
  
  
  for any facet $F$ of $P$ and any inequality $a_{i}x\leq \beta_{i}$ from $A x\leq b$ .

  The faces of dimension $0$, $1$, $k-2$ and $k-1$ are called the vertices, edges, ridges and facets, respectively. The vertices coincide with the extremal points of the polyhedron, that are also defined as points which cannot be represented as convex combinations of two other points in the polyhedron. When an edge is not bounded, there are two cases: either it is a line or a half-line starting from a vertex. A half-line edge is called an extremal ray.

• The convex hull of a set $P$ is the convex combination of all points in $P$. It is the smallest convex set which contains all of $P$.

Polylib implements procedures to compute, from one representation of a polyhedron $P$ (implicit of parametric), its dual representation of $P$, given the implicit on. The algorithms was proposed by Chernikova [Che65] which rediscovered the double description representation introduced by Motzkin. Important improvements were made in the conversion process between these representations by Fernandez [FQ88] and Le Verge [Le 92].

Based on this kernel algorithm, Polylib propose many computational function on polyhedra. More precisely, Polylib manipulates domains which are finite unions of polyhedra ^3.1.

Polylib manipulates mixed inhomogeneous system of equations. The terms inhomogeneous stands for the fact that it manipulates objects of an affine space (not a linear space). To transform the inhomogeneous affine space of dimension $n$ into an homogeneous linear space of dimension $n+1$, we use the following mapping:

$${\cal M}: x \longrightarrow \left(\begin{array}{c} \xi x \\ \xi \end{array}\right), \ \ \ \ \ \xi >0 \quad .$$

With this mapping, a system ${\cal P}=\{ x~\vert~ Ax=b,\ Cx\geq d \}$ in the original inhomogeneous space is transformed into ${\cal C}=\{ \tilde{x}~\vert~\tilde{A}\tilde{x}=0,\ \tilde{C}\tilde{x}\geq 0 \}$ where

$$\tilde{A}=(A\ \ -b),\ \ \tilde{x}= \left( \begin{array}{c} \... ...t( \begin{array}{cc} C & -d \\ 0 & 1 \end{array}\right) \quad .$$

In the internal representation of Polylib, object manipulated are cones (the Chernikova algorithm works on cones), but this is transparent for the user which naturally manipulates polyhedra (or union of polyhedra). As many Polylib functions refer to domain, we precisely define what a domain is:

Definition 2   (Domain) A polyhedral domain of dimension $n$ is defined as:

$$D:\{i\vert i\in Z^n, i\in P \}=Z^n \cap P$$ (3.1)

where $P$ is a union of polyhedra of dimension $n$.