Try our new documentation site (beta).
Next: Optimizing over the circle: Up: Instability and the geometry Previous: Dealing with epsilon-optimal solutions
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.