1
$\begingroup$

In a linear programming problem, when the goal is to optimize a linear combination of variables with some constraints, it is said that the corners of feasible solution (the Polyhedron determined by constraints) are candidates for optimization problem. More description is here. It seems obvious that one of the corners should be the solution (as simplex algorithm uses this fact). But is there any proof for showing this?

$\endgroup$
2
$\begingroup$

Here are a few pictures that might help. If we are working with a system that has three constraints such that our feasible space is inside this triangle.

enter image description here

Then, if we look at any point on the interior of our space

enter image description here

We see that we can improve (get a more extreme value of) our function by moving closer to one of the boundaries of our feasible space. For example:

enter image description here

But then we still have another degree (coordinate) of freedom, so we still can't do any worse if we go to one of the extremes in that dimension (along the constraint we are currently on:

enter image description here

Then we land on a corner point and we can't go any farther. This must be the best we can do in this direction. Then we reason, that we only need to check the other corners of our feasible space.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

The function you optimise is linear, so along a line it necessarily grows at constant rate in one direction. That means that a point $p$ along the line that is feasible but not a corner will always be worse (or at best equal) to one of the two corners on that line. If one corner is worse than $p$, then the other corner will be better.

And if you have a feasible point that is not even on an edge, then if you walk in any direction, the payoff / function to be optimised either increases or decreases. If it increases, walk until you meet an edge, and if it decreases, turn around and walk until you meet an edge. Then use the paragraph above.

| cite | improve this answer | |
$\endgroup$

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.