Algorithm for checking if a polyhedron is bounded.

Question

Given a polyhedron in the form $Ax \leq b$, I need to know a way to determine if the polyhedron is bounded.

I need an algorithm for which given a matrix $A$ and a vector $b$ as input, it should output True if the polyhedron thus formed is bounded, otherwise output False.

Answer 1

A naive (but deterministic) algorithm is to check if the support function of the polyhedron is bounded for each of the $2n$ canonical basis directions $\pm e_i$, for $i = 1, \ldots, n$. In the worst case this requires solving $2n$ linear programs.

I'm aware of a better approach that uses Stiemke's theorem of alternatives, which requires just 1 LP:

Proposition 1. If $\ker(A) \neq \{ 0\}$ => $P$ is unbounded.

Proposition 2. Assume that $\ker(A) = \{0\}$ and $P$ is non-empty. Then $P$ is bounded if and only if the following linear program admits a feasible solution: $\min \Vert y \Vert_1$ subject to $A^T y = 0$ and $y \geq 1$.

---

The naive method is available in the Julia library LazySets.jl (which i'm coauthor) and you can use it as isbounded(P) where P is the polyhedron. The second method is waiting to be implemented :) -- see LazySets#1136.

EDIT: the method in question is now available since LazySets release v1.37.4.

Answer 2

Linear programming is (in practice, with readily available software) fast. Take a random unit vector $c$ and maximize and minimize $c \cdot x$ subject to $A x \le b$. If the polyhedron is nonempty and bounded, both problems will have optimal solutions. If it is unbounded, then with probability $1$ one or both problems will be unbounded.