# Removing redundant half-spaces that bound a convex polytope

I am computationally representing a convex polytope in $\mathbb{R}^n$ as a set $A$ of half-spaces that bound it; each such half-space is represented by a row vector $\mathbf{v} = \begin{bmatrix}v_1 & v_2 & \cdots & v_n & b\end{bmatrix}$ such that the half-space is the set $$\{(x_1, x_2, \dotsc, x_n) \in \mathbb{R}^n\ |\ v_1x_1 + v_2x_2 + \dotsb + v_nx_n \geq b\}.$$

The set $A$ then represents the convex polytope that is the intersection of all half-spaces in $A$.

Question: What algorithm can find the smallest subset of $A$ that represents the same convex polytope as $A$? This may depend on detecting if a half-space is "redundant", so how do you do that as well? Hopefully, the algorithms make use of the vectors $\mathbf{v}$.

-
You might want to check out convex hull algorithms. – Tunococ Jan 28 '13 at 14:56

The polytope can be written as $Ax \geq b$ (where rows of $A$ contain your $v$ vectors). For each row $v = [v_1 v_2 \ldots v_n]$ of $A$, solve the LP $$\begin{array}{c} \min v^T x \\ Ax \geq b \end{array}$$

The half-space defined by this $v$ is not redundant if and only if the optimum value obtained above is equal to the corresponding $b$ value.

-
The "if and only if" in your claim is not true. Counterexample: Let $A=\begin{pmatrix}-1&0\\1&0\\0&-1\\0&1\\-1&-1\end{pmatrix}$ and $b=\begin{pmatrix}-1&-1&-1&-1&-2\end{pmatrix}^T$. The system $Ax \geq b$ describes a two dimensional box and the last row is redundant. (It is the sum of the first and the third row). Anyhow, your proposed LP yields the optimal value $-2$. – Willem Hagemann Jun 4 '15 at 13:13
Or even more intuitive: In the system $x\geq 1, 2x\geq 2$ clearly $2x\geq 2$ is redundant. However, $\min\ 2x$ over the system yields $2$. – Willem Hagemann Jun 4 '15 at 13:46

Let $Ax\leq b$ a system of linear inequalities. We denote the rows of $A$ by $A_k$ and the $k$th component of $b$ by $b_k$. Further, let $I$ be the set of all row indices of $Ax\leq b$. The $k$th row of $Ax \leq b$ is not redundant if and only if the LP

maximize $A_k$x subject to $A_ix \leq b_i$ $\forall i\in I\setminus\{k\}$ and $A_kx \leq b_k-1$

has an optimal value strictly greater than $b_k$.

(See http://stat.ethz.ch/ifor/teaching/lectures/poly_comp_ss11/lecture_notes page 52 and following Clarkson algorithm for more efficient methods.)

-