Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over.
How do I see that either the problem is unbounded, that is the optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$ ($v$ is a optimal solution with optimal value $c^Tv$).
Why is it not possible to have a case similar to: minimize $1/x$ for $x \ge 1$, where the optimal value is not $-\infty$ neither does a optimal solution exist. I know $1/x$ is not a linear cost function, but I'm just making an example here.
Thanks !
If $P$ is bounded the solution must be achieved on the boundary. The solution exists because $P$ is compact and $c^Tx$ is continuous. The solution must be on the boundary because of linearity of $c^TX$. This is trivial. Let me skip the proof. If $P$ is unbounded and exists such $x\in P $ such that $c^Tx < 0$ and $kx\in P$ for all $k>1$ then of course the optimal value will be on $-\infty$. The difference with $1/x$ is that this function itself is convex and bounded even on unbounded set $[1,\infty)$.
Of course it might happen that $P$ is unbounded while the optimal value is finite. Then the solution is achieved on the boundary anyway . Example: $\min x$ for $x\ge 0$.