H-Polyhedron Boundedness

This is another question from quora. Not only is the question interesting in its own right, but the answer also reveals a nice application of a fundamental idea in linear algebra.


Can an h-polyhedron be checked for boundedness efficiently? How?



Our polytope is the intersection of a collection of half-spaces in Rn\mathbb{R}^n. These half-spaces are given by inequalities of the form

a1x1+a2x2++anxnb1.a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b_1.

Assume we have a total of mm half-spaces which define our polytope. Then the polytope can be more compactly written as the set of all solutions to

AxbAx \leq b

where AA is an m×nm \times n matrix.

It turns out that our polytope is bounded if and only if Ax=0Ax = 0 has only the trivial solution.

Consider what happens if Ax=0Ax = 0 has a nontrivial solution x0x_0. Then for any solution xx to AxbAx \leq b and any ε>0\varepsilon \gt 0 we have

A(x+εx0)=Ax+εAx0=Ax+0b.A(x + \varepsilon x_0) = Ax + \varepsilon A x_0 = Ax + 0 \leq b.

So, x+εx0x + \varepsilon x_0 can increase in magnitude arbitrarily and will always remain in the polytope.

Thankfully, checking whether Ax=0Ax = 0 has only the trivial solution can be computed using Gaussian elimination in polynomial time.