commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dr. Dietmar Wolz (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-621) BOBYQA is missing in optimization
Date Tue, 02 Aug 2011 14:23:28 GMT

    [ https://issues.apache.org/jira/browse/MATH-621?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13076222#comment-13076222
] 

Dr. Dietmar Wolz commented on MATH-621:
---------------------------------------

Hi Gilles,
bug is confirmed - and it is also in the new array based version. 
Debugging the unit test reveals sum is 0 here, so for rescue the
unit tests are not sufficient at the moment. 

Creating the array based version caused a lot of these bugs initially, but I 
would favour this version
over the old one because it is much cleaner and easier to read and maintain.

My experience is that if you introduce this kind of bug in any part beside 
rescue, you
are guaranteed to see a difference in the output I put into the junit tests form 
my newest attachment.

The number of function calls will differ from the C/Fortran version. But you 
definitinely have
to compare these function call numbers with the C/Fortran version, to be sure 
everything is 

as intended. Even slight changes like a = a+b replaced by a += b can cause 
trouble
because of subtle accuracy problems accumulating over time. 

Rescue is a completely different story, therfore I asked Mike Powell whether he 
could
provide us with meaningful samples/testsm his answer was: 


---------------
Excerpt from a mail from Mike Powell:
Concerning RESCUE, it is present in BOBYQA because, in some tests
with unattainable accuracy requirements, a little more progress could
be made by invoking RESCUE. Checking the correctness of RESCUE was
possible only by modifying the package in a way that forced it to be
called in situations that were not contaminated severely by loss of
accuracy. I may decide to delete RESCUE from the Fortran package that
I send to people who ask for BOBYQA.
-------------

To make progress we have a lot of options to decide:

1) Keep rescue? May be removing it from the initial release in commons.math 
doesn't do too much harm.
When keeping it we should find useful applications before and add them to the 
unit tests.

2) Using arrays instead of pointers and don't use the large shared working 
space? I would prefer so, since the
arrays-version is faster in Java (pointers need to be emulated) and the code 
becomes much clearer. 


3) Complete redesign/refactor the code? 
A difficult issue. I would say that this is very hard to achieve. 
Instead I would try to build something equivalent from scratch. 
Problem is that Mike Powell put 50 years of experience developing optimization 
algos
into BOBYQA and you can see that comparing the number of cost function calls 
needed with other
optimization algos. So from the user perspective BOBYQA has a huge value even if 
not completely 

refactored/redesigned and it is not an easy decision to keep BOBYQA out of 
commons.math for
code-aesthetic reasons.

I would like to see other opinions on these options.

Gilles commented on MATH-621:
-----------------------------

Dietmar,

I think I've come across a bug in function "rescue". At line 2443 (of the Java 
translation I use for comparison, i.e. the one with "ScopedPtr"):
{code}
i__2 = ndim;
for (ip = npt; ip <= i__2; ip++) {
  sum += bmat.get(ip + j * bmat_dim1) * w.get(ip);
}
{code}
Whereas, in the original Fortran code (at line 1544):
{noformat}
      DO 220 IP=NPT+1,NDIM
  220 SUM=SUM+BMAT(IP,J)*W(IP)
{noformat}

Can you confirm?

If indeed, the loop should start at "npt + 1", I've made the change; but tests 
still all pass! Does this mean that the one exercising rescue is too lenient?
Trying to remove the "w" ("split" work space) from "rescue" provides many 
possibilities for my own mistakes; thus I am a little scared that they would 
also go unnoticed...



--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira


> BOBYQA is missing in optimization
> ---------------------------------
>
>                 Key: MATH-621
>                 URL: https://issues.apache.org/jira/browse/MATH-621
>             Project: Commons Math
>          Issue Type: New Feature
>    Affects Versions: 3.0
>            Reporter: Dr. Dietmar Wolz
>             Fix For: 3.0
>
>         Attachments: BOBYQA.math.patch, BOBYQA.v02.math.patch, bobyqa.zip, bobyqaoptimizer0.4.zip,
bobyqav0.3.zip
>
>   Original Estimate: 8h
>  Remaining Estimate: 8h
>
> During experiments with space flight trajectory optimizations I recently
> observed, that the direct optimization algorithm BOBYQA
> http://plato.asu.edu/ftp/other_software/bobyqa.zip
> from Mike Powell is significantly better than the simple Powell algorithm
> already in commons.math. It uses significantly lower function calls and is
> more reliable for high dimensional problems. You can replace CMA-ES in many
> more application cases by BOBYQA than by the simple Powell optimizer.
> I would like to contribute a Java port of the algorithm.
> I maintained the structure of the original FORTRAN code, so the
> code is fast but not very nice.
> License status: Michael Powell has sent the agreement via snail mail
> - it hasn't arrived yet.
> Progress: The attached patch relative to the trunk contains both the
> optimizer and the related unit tests - which are all green now.  
> Performance:
> Performance difference (number of function evaluations)
> PowellOptimizer / BOBYQA for different test functions (taken from
> the unit test of BOBYQA, dimension=13 for most of the
> tests. 
> Rosen = 9350 / 1283
> MinusElli = 118 / 59
> Elli = 223 / 58
> ElliRotated = 8626 / 1379
> Cigar = 353 / 60
> TwoAxes = 223 / 66
> CigTab = 362 / 60
> Sphere = 223 / 58
> Tablet = 223 / 58
> DiffPow = 421 / 928
> SsDiffPow = 614 / 219
> Ackley = 757 / 97
> Rastrigin = 340 / 64
> The number for DiffPow should be dicussed with Michael Powell,
> I will send him the details. 
> Open Problems:
> Some checkstyle violations because of the original Fortran source:
> - Original method comments were copied - doesn't follow javadoc standard
> - Multiple variable declarations in one line as in the original source
> - Problems related to "goto" conversions:
>   "gotos" not convertible in loops were transated into a finite automata (switch statement)
> 	"no default in switch"
> 	"fall through from previos case in switch"
> 	which usually are bad style make no sense here.

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message