commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Nigel Goodwin (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-621) BOBYQA is missing in optimization
Date Tue, 06 Sep 2011 23:05:10 GMT

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

Nigel Goodwin commented on MATH-621:
------------------------------------

No I would not!

I do a lot of work with positive definite symmetric matrices, and I ALWAYS store and manipulate
them as upper (or lower) triangular matrices stored as a vector or 1D array. This is the best
way to do it, and nothing would motivate me to make a retrograde step and store symmetric
matrices as a matrix or 2D array (unless maybe underlying storages was a 1 D array, and even
then I would have grave misgivings).

I have written a lot of symmetric matrix code, and it ALWAYS outperforms any Java library
I can find, simply because I use the proper 1D array form of storage. Plus i do a bit of loop
unrolling etc etc but that is another story.

I first looked at code provided by Prof Powell back in the early 1980's, his rank one (or
was it rank two) cholesky factor update, and no doubt this has influenced my tendency to always
store upper (or lower) triangular matrices as 1D arrays.

I even hate it when there is a special class for symmetric matrices, and it has a last step
which puts the lower triangular elements equal to the upper triangular elements. No, don't
do it, do it properly!

In most of my application code, cholesky factorisation and back substitution are the bottlenecks.
I do tens of thousands of back substitutions.

Now, if there was a symmetric matrix class with an underlying storage of a 1D array, and some
suitable get and set functions, you might persuade me, so long as the get and set were just
utilities to be used in non critical parts of the code.

Store a symmetric matrix as a 2d array? No, never, no!

ps soory about the capitals. But you may note I feel strongly. It is why all Java libraries
I have looked at suck for symmetric matrices, and i had to write my own.

It is late, and I may be wrong, but I think LAPACK symmetric code (or is it BLAS?) stores
symmetric matrics as 1D triangular arrays.

> 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, BOBYQAOptimizer.java.patch,
BOBYQAOptimizer0.4.zip, bobyqa.zip, bobyqa_convert.pl, 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