Linear Programming and Geometry Question

Question

I have a question that involves some linear programming and linear algebra, and I really don't have a clue how to approach this question. Could someone give me some hints and ideas as to how to attack this problem. Thanks.

Answer 1

The "if" direction is easier, and so I will focus on the "only if" direction, which if you understand it should probably provide you with enough understanding to tackle the "if" direction on your own.

The key geometrical observation that one needs is:

• For each $z \not\in \text{Cone}(V)$ there exists a hyperplane $P$ through the origin such that $z$ is on one side of $P$ and $V$ is on the other side.

This has to be proved rigorously, but with a little visualization and by drawing some pictures or looking at some examples you can convince yourself that it is true. Once you believe this, simply take $w$ to be a vector orthogonal to $P$ and pointing into the side of $P$ away from $V$.

To prove the above statement rigorously you need the fact that $\text{Cone}(V)$ is a convex set, which should be obvious from its definition: for any $z_1,z_2 \in \text{Cone}(V)$ the entire line segment $\{(1-t)z_1 + t z_2 \mid 0 \le t \le 1\}$ is in $\text{Cone}(V)$. Then you use a general property of any convex set: if $z \not\in \text{Cone}(V)$ then there exists a hyperplane $P'$ (not necessarily through the origin) such that $z$ is on one side of $P'$ and $\text{Cone}(V)$ is on the other side of $P'$. If $P' \cap \text{Cone}(V) \ne \emptyset$ then you prove that $P=P'$ does indeed pass through the origin. Otherwise, if the intersection is empty, you move $P'$ parallel to itself until the first moment that it touches $\text{Cone}(V)$ and the resulting plane is the desired $P$.