3
$\begingroup$

Having read the link:

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.

$\endgroup$
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Keneth Adrian Nov 2 '14 at 7:19
  • $\begingroup$ @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. $\endgroup$ – RRL Nov 2 '14 at 7:31
  • 2
    $\begingroup$ 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$". $\endgroup$ – bubba Nov 2 '14 at 7:39
  • $\begingroup$ so really instead of $\frac{\epsilon}{2}$, they could chosen $\alpha \epsilon$ as long as $\alpha < 1$. $\endgroup$ – Kiran K. Feb 7 '16 at 16:47
  • $\begingroup$ @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^*$. $\endgroup$ – RRL Feb 7 '16 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.