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.
LP unboundedness
-
1I recommend asking on Math.SE. Hopefully you already know basics like the weak duality theorem. – 2012-07-20
1 Answers
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.
-
0I 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. – 2012-07-25