Feasible region unbounded

Question

How do we prove that if a linear programming problem is unbounded, then its feasible region is necessarily an unbounded set as well? It kind of seems intuitive but how do I rigorously show this?

@angryavian yes. For every real $x$, there's a feasible objective value whose value is smaller/larger than $x$ (depending on if the problem is minimizing/maximizing) — sedrick, Sep 29 '19 at 02:13
Is the feasible region closed? (Specified using $\le, \ge$ constraints rather than $<,>$ constraints.) — angryavian, Sep 29 '19 at 02:20

score 3 · Accepted Answer · answered Sep 29 '19 at 02:25

We prove the contrapositive. Suppose the feasible region is bounded. We already know it is closed, by assumption. The objective function is continuous (because it is linear). Therefore the extreme value theorem applies: it implies that the maximum (or minimum) of the objective function on the feasible region is attained at some point in the region. Thus the LP problem is bounded.

score 0 · Answer 2 · answered Sep 29 '19 at 02:37

Here is a topological argument.

The feasible region is closed. If it were bounded, it would be compact, by Heine Borel. The objective is a continuous function so the image of the feasible set would be compact as well, and therefore bounded, by Heine Borel again. But that's a contradiction to the objective being unbounded.

Feasible region unbounded

2 Answers2