commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gilles (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (MATH-1375) BOBYQAOptimizer Seems to Sometimes Enter Endless Loop
Date Thu, 09 Jun 2016 10:13:21 GMT

     [ https://issues.apache.org/jira/browse/MATH-1375?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Gilles updated MATH-1375:
-------------------------
    Description: 
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.

  was:
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.


> 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)

Mime
View raw message