Documentation

Thin feasible regions

We now consider another extreme situation that can lead to unexpected results. Consider the problem defined as

and its graphical representation

It is clear from the graphical representation that the optimal solution for the problem will be at the intersection of constraints with ; and if we do the algebra, we will get that . Also note that as you decrease the feasible region stretches upwards, leaving its base unchanged. We will consider the case where is a very small, positive number (between and ).

If we perturb the right-hand side vector from to , the new solution will be . To assess the impact of this perturbation, we compute the distance between this modified solution and the previous solution, which is given by

This quantity can be either small or very large, depending on the relative magnitude between and . If is much smaller than , then this quantity will be small. However, if is larger than or even the same order of magnitude as , the opposite will be true. Very small perturbations in the input data can lead to big changes in the optimal solution.

A similar issue arises if we perturb to ; the new optimal solution becomes . But now, if , then the new solution for will change from to (a 33% relative difference). Again, small changes in the input can produce big changes in the optimal solution.

What is driving this bad behavior? The problem is that the optimal point is defined by two constraints that are nearly parallel. The smaller is, the closer to parallel the are. When the constraints are so close parallel, small changes in the slopes can lead to big movements in the point where they intersect. Mathematically speaking:

Note however that, if the original problem had an additional variable bound of the form , then neither of these bad behavior would have been possible. For any value smaller than , the optimal point would be defined by the new constraint and one of the constraints or , which would lead again to a well-behaved (i.e. stable) solutions. In summary, this sort of issue can only arise when either the feasible region is either unbounded or very large. See the Scaling section for further guidance on bounding the feasible region.