12/20/04 - The "Slater Condition" gives us the optimality
condition that we want. Note that we need to treat our constraints as
less-than-or-equal-to constraints (which is what they really are).
So, if KKT conditions are satisfied and the gradient of the function
corresponding to each constraint has a negative inner product with the
constraint, then we are done. Ah, but we are only done with that
region... We must still consider adjacent regions. Important
question: how do regions relate to each other that touch at a point?
Can there be "cycles"? Is it possible that we would move from region
to region, following the direction of the gradient, but not moving
anywhere? Maybe we need to check the gradient of all regions that
overlap at a point, not just the ones we've decided to activate.
I.e. in this diagram, if the "active" region is #1, we might need to
check the gradient of region #3. | |