Thomas Weise created MATH-1375:
----------------------------------
Summary: BOBYQAOptimizer Seems to Sometimes Enter Endless Loop
Key: MATH-1375
URL: https://issues.apache.org/jira/browse/MATH-1375
Project: Commons Math
Issue Type: Bug
Affects Versions: 3.6.1
Environment: Java 8 JDK, OpenJDK, Ubuntu
Reporter: Thomas Weise
Priority: Minor
I am using BOBYQAOptimizer to solve some numerical problems related to
nonlinear function fitting. BOBYQAOptimizer is provided with close-to-optimal
solutions which it is supposed to refine. In some cases, BOBYQAOptimizer seems
to enter an endless loop, or at least an extremely long loop. The problem is
almost impossible to reproduce as it occurs maybe once every 1000 runs.
>From what I can see with the debugger, the source of the problem is probably
>method trsbox which is called by bobyqb. In trsbox, some values of a vector
>(sorry, forgot which one) grow extremely large (>=1e250). Either way, I
>noticed that both mentioned methods feature a for(;;) loop.
Now that algorithm looks quite mathematical to me and seemingly has been
translated from FORTRAN or something. I think fixing and finding mathematical
issues might be complicated (see also the caveats reported in the release
notes) and overall, the algorithm is working.
How about you also count the iterations of the for(;;) loops in bobyqb and
trsbox and throw an exception if they exceed some limit? In the easiest case,
instead of for(;;) you can do something like
for(int maxRemainingSteps=100; (--maxRemainingSteps)>=0;) {
...
}
throw new MaxCountExceededException(100);
// or TooManyEvaluationsException(100);
// or MathIllegalStateException(LocalizedFormats.SIMPLE_MESSAGE, "Huh?");
Since the original for loops are always left via "return", that would already
do the trick. Or you could use an Incrementor object for this purpose. Either
way, I think with the very simple fix above, you would prevent endless loops,
add only a tiny bit of very easy-to-understand code, and would not break the
algorithm contract, since such exceptions could be thrown sometimes even
without the fix.
In summary: BOBYQAOptimizer needs some work. Fixing the issue I observed
properly (i.e., by fixing the special cases causing it) is probably very
complex and is probably not feasible. Preventing it, however, seems to be
rather easy, as I have shown above.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
