[
https://issues.apache.org/jira/browse/MATH-1375?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15325827#comment-15325827
]
Thomas Weise commented on MATH-1375:
------------------------------------
Hi. Yes, MATH-1282 is definitely related, probably the same problem.
I am using BOBYQA in combination with other optimizers. I found that in my
particular problem, Levenberg-Marquardt + Nelder/Mead + BOBYQA in combination
often give the best performance/runtime results.
I did not test other implementations of BOBYQA. I see where you are getting at:
This problem seems to only occur rarely, it might actually already be present
in the original algorithm.
>From this perspective, my suggested fix may be the best option for the time
>being: Limiting the loops to a reasonable, generous maximum number of
>iterations. The main issue is this: The problem does not occur often, the
>other issue confirms that. If the problem occurs, this is an endless loop. So
>for a productive system, this is a real show stopper. Since the problem does
>not occur often, it would even be acceptable if BOBYQA would run quite a bit
>longer, as long as it does not run forever. Thus the idea with the generous
>upper limit. trsbox could simply return null is the limit is exceeded, which
>could be checked in the calling method, which could then simply return
>immediately as well. One could even allow the user to specify the limit number.
The resulting changes in code would be minimal and they would not violate the
contract of the methods. BOBYQA cannot guarantee to find the global optimum
anyway. If in some very rare cases it would be terminated "early" after quite
some time while it was actually not in an endless loop, it could return the
best-so-far solution, which would then probably not be very different from what
it would return anyway.
> 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
> Original Estimate: 4h
> Remaining Estimate: 4h
>
> 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
> {code}
> for(int maxRemainingSteps=100; (--maxRemainingSteps)>=0;) {
> ...
> }
> throw new MaxCountExceededException(100);
> // or TooManyEvaluationsException(100);
> // or MathIllegalStateException(LocalizedFormats.SIMPLE_MESSAGE, "Huh?");
> {code}
> 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)
