# LP unboundedness

Does there exist a way to check if a linear programming problem is unbounded without solving it directly? In other words, How the unboundedness of an LP can be realized from its structure. Assume the corresponding feasible area is nonempty.

-

## migrated from scicomp.stackexchange.comJul 25 '12 at 17:16

This question came from our site for scientists using computers to solve scientific problems.

I recommend asking on Math.SE. Hopefully you already know basics like the weak duality theorem. – David Ketcheson Jul 20 '12 at 13:42

Claim: Let ${\cal P}$ be the set of solutions of $$A x \leq b,$$ and suppose ${\cal P}$ is feasible. Then ${\cal P}$ is unbounded if and only if the set of solutions of $$Ax \leq 0$$ contains a nonzero point.
The ''if'' part is obvious. The only if part may be proved roughly as follows. Take $x$ to be some point in ${\cal P}$ and take $y_t$ to be a sequence in ${\cal P}$ whose norm approaches infinity. Let $d_t$ be the normalized direction vector $d_t=(y-x)/||y-x||_2$. Pick a convergent subsequence of the $d_t$ and argue that $A d_t \leq 0$.
Edit: If what is being asked about is whether the minimum of $c^T x$ over ${\cal P}$ is $-\infty$, then this has a similar answer: it is true if and only if there is a $d$ with $c^T d < 0, Ad \leq 0$. The argument is more or less the same.