# 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.

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

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

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

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$.

What this means is that checking whether an LP is unbounded is not much easier that checking whether the solution set of an LP is feasible; in turn, that is not much easier than solving the LP itself.

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.

-
But unboundedness with an LP doesn't refer to the feasible set; it refers to the objective function. You can have an unbounded feasible region without the LP itself being unbounded. –  Mike Spivey Jul 25 '12 at 20:31
I added an edit in case that is what was meant. If I'm still misunderstanding the question, presumably the OP can state it in precise language for those of us not familiar with what unboundendess of an LP refers to. –  alex Jul 25 '12 at 20:36