Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
feasible point solving has a logic error w.r.t. properties of smooth-max #1
Attempting to add some new constraints for erikerlandson/snowball#1 has turned up a bug in my feasible point algorithm. Specifically, the problem is that I designed this algorithm assuming that smooth-max preserved the location of minima over convex functions. That is to say, if you find the minimum of the maximum over some convex functions, and then find the minimum of the smooth-max over those functions, those two minima will have the same location. This isn't true, as this example with simple 1D functions shows (the green smooth-max curve has its minimum to the right of the corresponding minimum over the true max):
Under some circumstances, this discrepancy will cause the current algorithm to find its minimum outside the actual feasible region and so it will report failure on constraints that actually have a non-empty feasible region.
I have to re-think the way that the
referenced this issue
Dec 5, 2018
Plan for fixing this problem: alpha starts at 1.0 - minimization is done using this value. If the resulting minimum point is not < 0, then double alpha, and try again, etc, until some halting condition. Either alpha exceeds some threshold, or perhaps if two consecutive minimums differ by < epsilon.
That is the default logic for alpha. However, it may be the case that the circular constraint Hessian can underflow - the current logic for detecting and preventing underflow can override the value for alpha (set it lower). If this happens, then alpha begins doubling from this corrected value next iteration
Tangentially I think the logic around the circular constraint can be simplified a little, by just declaring radius (r) to be something like 2x(maximum positive value over all constraint functions), as this is likely to overlap at least one constraint surface. In this scheme, scaling the function can be done to make its minimum some standard value, like 1.