I have a question. How to prove that an unbounded set (not from all sides, so it would have some corner points) but with objective minimalization function bounded from some sides (for example below) has optimum at corner point? There is a theroem (about convex, closed and bounded set) with corner points and linear program: Let some convex, set F of feasible solutions of Linear Program (with objective function $c^Tx \to min$, where vector $c^T$ is row vector of some coefficients and $x$ is vector of variables of feasible solutions) be bounded. Then
- There exists min{$c^Tx$: x is from set F } = $f^\star$.
- There exists some vector $x_0$ from set of corner points of set F labeled as ex(F) for which following is true: $c^Tx_0$ = $f^\star$.
The first statement can be proved by Weierstrass (extreme point) theorem and the second statement can be proved/proven as follows: Let $c^Tx = f^\star$. Point x is convex combination of corner points labeled as $x_j$ from convex set F, but for every j the following is true (beacuse of $c^Tx = f^\star$): $c^Tx_j >= c^Tx$. Then the proof of statement is: $c^Tx = c^T(\sum_{j=1}^k \lambda_jx_j) = \sum_{j=1}^k \lambda_jc^Tx_j >= \sum_{j=1}^k \lambda_jc^Tx$ (because of the $c^Tx_j>= c^Tx$) $= c^Tx$ (because $\sum_{j=1}^k \lambda_j$ has to equal to $1$ (one) (to be a convex combination)). So there has to be equality everywhere, so that implies that every corner point in the form of point x has to be an optimal solution. So my question is how to prove that 2nd statement (There exists some vector x0 from set of corner points of set F labeled as ex(F) for which following is true: $c^Tx0$ = f* - so optimal solution is at corner point.) for unbounded set but to imagine this set, for example as we were in space with dimension 2 (plane) and that unbounded set is like intersection of the first quadrant and some half-planes defined by decreasing-like lines but above these lines (so if we had some maximalization problem then the objective would not have a finite optimum, but we have minimalization problem so there could be some corner point (like at edges of first quadrant for example (at x-axis or y-axis or some intersection of the lines). Thanks for help.
Also there is an Image to imagine the problem in 2D, where corner points are A, B and C, and the darkest blue region is that mentioned unbounded region/set, click here: click here to view the image of the mentioned situation
I am adding also some interesting facts (images) that may be useful, if somebody knows the file where there is also some theory behind, please leave a comment, and I am also writing a link to file from which the pictures I used: theorems and definitions
