# Why are corner points of feasible region candidates in solving linear programming problem?

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?

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.

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.

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

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:

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:

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.