Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

As the topics, why the optimized point always appear in the interception in LP problem? I think there should be a proof but i am not sure about it.

share|cite|improve this question

In LP we deal with linear constraints and a linear target function. Along any edge, face and so on, the target function will either be constant (hence you may use a vertex as optimal point just like any other point on that face/edge); or it is still a linear function, hence grows as long as you move along a fixed direction and hit a lowerdimensional face/edge and ultimately a vertex. Therefore it is sufficient to consider the vertices of the polyhedron given by the constraints.

share|cite|improve this answer
Is there exist any proof? – Mathematics Sep 28 '12 at 11:01
Was this not proof enough? You may also note that the polyhedron is convex. A nonconstant linear function on a convex set has extrema only on the boundary. – Hagen von Eitzen Sep 28 '12 at 11:07
what about in the same dimension, says 2 D, what you mean by lower dimension? – Mathematics Sep 28 '12 at 11:13
The constraints define a convex polytope. Its "faces" are convex polytopes of one dimension less, this goes finally down to faces in 2D, then edges in 1D and ultimately vertices in 0D. – Hagen von Eitzen Sep 28 '12 at 11:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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