# On the Proof of Fundamental Theorem of Linear Programming.

Why maximum/minimum of linear programming occurs at a vertex?

I understand why the optimal solution of any linear programming problem must be on the corner or lies on a face of a convex polygon. But my question is about a proof given below:

http://en.wikipedia.org/wiki/Fundamental_theorem_of_linear_programming

I do not know why the next argument was

$$x^\ast - \frac{\epsilon}{2} \frac{c}{||c||} \in P$$

Sorry to ask this question, but I can't imagine where the term

$$\frac{\epsilon}{2} \frac{c}{||c||}$$

is coming from. Anyone, please enlighten me. Thanks.

Isn't it the contradiction will still be true even if we have, $$x^\ast - \frac{c}{||c||}$$.

The problem may be this construction may not be in $P$. Now, I really want to visualize the expressions $\frac{\epsilon}{2} \frac{c}{||c||}$ and $\frac{c}{||c||}$. Thanks.

In the proof, the assumption that $x^\ast$ is in the interior of $P$ is shown to lead to a contradiction.

Let

$$z = x^\ast - \frac{\epsilon}{2} \frac{c}{||c||}$$

Then

$$||z - x^\ast|| = \frac{\epsilon}{2} \frac{||c||}{||c||}= \frac{\epsilon}{2} < \epsilon,$$

and

$$z \in B_{\epsilon}(x^\ast) \subset P.$$

This was chosen to obtain a feasible point $z \in P$, such that $c^Tz < c^Tx^\ast$

Since $x^\ast$ is optimal we have a contradiction, implying that $x^\ast$ cannot lie in the interior of $P$.

• thanks for the explanation, but can I clarify what is the difference between c and ||c|| ? is that the modulus? and $z$ must be in the interior of the ball centered at x* with radius $\epsilon$? ( I think I somehow get it) – Keneth Adrian Nov 2 '14 at 7:19
• @KenethAdrian: Yes, $||c||$ is the norm (magnitude) of the vector c. With that choice we get a point in the ball where the objective function is smaller than the minimum at $x^{\ast}$, a contradiction. – RRL Nov 2 '14 at 7:31
• Yes, $\|c\|$ is the norm (or length) of the vector $c$. So $\frac{c}{\|c\|}$ as just a fancy way of saying "a unit vector in the direction of $c$". – bubba Nov 2 '14 at 7:39
• so really instead of $\frac{\epsilon}{2}$, they could chosen $\alpha \epsilon$ as long as $\alpha < 1$. – Kiran K. Feb 7 '16 at 16:47
• @Kiran K: Yes you just need to get a contradiction by producing a point that is both in the interior of $P$ and such that $c^Tz < c^Tx^*$. – RRL Feb 7 '16 at 23:01