Questions about some of the simplex method properties

Question

In the 5th page of this book: Principles of Autonomy and Decision Making, I found that these properties are somewhat confusing.

• Most often, the optimal point is located at a vertex (corner) of the feasible region.

Question 1: Is "most often" referring to the cases where the feasible region is bounded, and only that?

• If there is a single optimum, it must be a corner of the feasible region. If there are more than one, two of them must be adjacent corners.

Question 2: How do you know that there is a single optimum prior?

• If a corner does not have any adjacent corner that provides a better solution, then that corner is in fact the optimum.

Question 3: I understand this graphically, but is there a concrete proof I can look up?

Answer 1

Question 1: Is "most often" referring to the cases where the feasible region is bounded, and only that?

Not really. It's referring to the explanation that follows - if an optimal point exists (which always happens if the feasible region is bounded suitably), then there will be an optimal point at a corner, but there may also be multiple such points, which will form an edge, face, or higher dimensional region. However, that only happens if the feasible region is oriented in a certain way relative to the constant-cost loci.

Question 2: How do you know that there is a single optimum prior?

You can partially test for it by comparing the constant-cost loci with the constraints. If none of them are parallel, then you're probably fine. If one of the constraints is parallel to the loci, then you might have multiple solutions but it's still hard to know for sure without further information.

Question 3: I understand this graphically, but is there a concrete proof I can look up?

You can look up a lot of variations of proofs of the correctness of the simplex algorithm, which gives you this result as part of it, but the basic idea is something like this:

• The feasible region is convex (i.e. the line segment joining two points of the region always stays within the region), and hence the optimum must occur at an extreme point (i.e. a corner).

• Assume you're at a corner where no adjacent corner improves the cost function.

• Also assume that you're not at the optimum, and show that the line segment joining your current corner to the optimum has to leave the feasible region, causing a contradiction.