[jira] [Created] (MATH-621) BOBYQA is missing in optimization

classic Classic list List threaded Threaded
96 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

[jira] [Created] (MATH-621) BOBYQA is missing in optimization

AD_LB (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


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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)

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

Dr. Dietmar Wolz updated MATH-621:
----------------------------------

    Attachment: BOBYQA.math.patch

Initial code contribution (BOBYQAOptimizer.java + Unit tests)

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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

Oops, this is indeed FORTRAN code in Java clothes. There is quite _a lot_ of work to make it look like Java... :(
Personally, I'd rather not commit it as is, because it is unmaintainable (it does not match anything in CM in terms of design and programming style).


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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

Dr. Dietmar Wolz updated MATH-621:
----------------------------------

    Attachment: BOBYQA.v02.math.patch

Tests with the original code confirmed a problem of BOBYQA with
DiffPow and SsDiffPow. But the tests revealed a problem with the
Java code: Initialization of the bounds with Double.MIN_VALUE and
Double.MAX_VALUE (representing no bounds)
caused trouble, I changed the values to -1e300, 1e300.
The old performance numbers a not valid, BOBYQA
changed the initial guess because of the bounds problem.

Adjusted accuracy level for PowellOptimizer and the new
BOBYQA code - now initialized correctly, lead to the
following 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 = 9831 / 1404
MinusElli = 183 / 115
Elli = 399 / 147
ElliRotated = 8964 / 7165
Cigar = 348 / 56
TwoAxes = 223 / 70
CigTab = 513 / 61
Sphere = 223 / 56
Tablet = 223 / 57
DiffPow = 308 / 10139
SsDiffPow = 667 / 4520
Ackley = 814 / 458
Rastrigin = 327 / 167

Essentially the same picture as before.

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

       
Reply | Threaded
Open this post in threaded view
|

Re: [jira] [Commented] (MATH-621) BOBYQA is missing in optimization

Luc Maisonobe
In reply to this post by AD_LB (Jira)
Hi Gilles,

Le 15/07/2011 15:05, Gilles (JIRA) a écrit :
>
>      [ https://issues.apache.org/jira/browse/MATH-621?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13065905#comment-13065905 ]
>
> Gilles commented on MATH-621:
> -----------------------------
>
> Oops, this is indeed FORTRAN code in Java clothes. There is quite _a lot_ of work to make it look like Java... :(
> Personally, I'd rather not commit it as is, because it is unmaintainable (it does not match anything in CM in terms of design and programming style).

Yes, but committing it this as is with an objective to "javaize" it
would allow to:

  - have a reference test harness to check changes do not introduce
    regressions
  - allow non-committer to help by providing small patches instead
    of always reworking the complete code (Dietmar is not a committer
    yet)
  - allow monitor what changes are introduced slightly
  - avoid delaying to much the availability of the feature so most
    people can test it
  - avoid delaying release to much as once the API is fixed (and in
    fact it depends on the optimization framework which is already
    defined), the implementation can be changed afterwards in 3.1

I agree the last point can lead to the code never been changed at all,
but the other points are important too.

best regards,
Luc

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

Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

"FORTRAN code in Java clothes" was the best I could do so far.
Perhaps someone else voluteers to transfer the code into a more
readable version using the commons.math matrix operations?
The problem is that the original code heavily relies on pointers and gotos.
It is indeed probably only maintainable by the author.
The current code could simplify the development of a "clean" version
by enabling parallel debugging using only a Java development environment.
I started with embedding a C++ port via JNI treating the optimizer
as a "black box". Since JNI is not possible in commons.math, I tried
to convert the code to Java.
Unfortunately there is nothing publicly available which
has comparable qualities in terms of usability.
From the developer perspective we have a maintanance problem, but from
the user perspective, it is not very satisfactory to abandon BOBYQA.  

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

       
Reply | Threaded
Open this post in threaded view
|

Re: [jira] [Commented] (MATH-621) BOBYQA is missing in optimization

Gilles Sadowski
In reply to this post by Luc Maisonobe
Hello.

> >Oops, this is indeed FORTRAN code in Java clothes. There is quite _a lot_ of work to make it look like Java... :(
> >Personally, I'd rather not commit it as is, because it is unmaintainable (it does not match anything in CM in terms of design and programming style).
>
> Yes, but committing it this as is with an objective to "javaize" it
> would allow to:
>
>  - have a reference test harness to check changes do not introduce
>    regressions
>  - allow non-committer to help by providing small patches instead
>    of always reworking the complete code (Dietmar is not a committer
>    yet)
>  - allow monitor what changes are introduced slightly
>  - avoid delaying to much the availability of the feature so most
>    people can test it
>  - avoid delaying release to much as once the API is fixed (and in
>    fact it depends on the optimization framework which is already
>    defined), the implementation can be changed afterwards in 3.1
>
> I agree the last point can lead to the code never been changed at
> all, but the other points are important too.

The point of view of a maintainer will be that your last point will swamp
any other considerations.
It is not consistent that we "nit-pick" some small pieces of code while it
would be OK to commit that big scary one. [No offense to Dietmar, as this
was an important first step: It is really invaluable to be able to run the
tests as one is going through incremental changes.]

I'm willing to start adapting the code. If there are other candidates,
that's fine too. But I certainly do not want to spend time converting it
while somebody else is working on overlapping changes.

It is understandable that people would be happy to play with a new toy. But
they can also live without it (as they did until now) for some more time.
[Or they can patch their local copy.]


Best,
Gilles
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

No problem, as I said on the ML. Thanks for the contribution.

{quote}
[...] the tests revealed a problem with the Java code [...]
{quote}

This is another reason why I don't like a diff/patch for the initial version. I've already made small changes so that it doesn't apply. Could you please attach the Java file itself (so that I don't have to work out the diff between diffs...)? Thanks.


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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

Dr. Dietmar Wolz updated MATH-621:
----------------------------------

    Attachment: bobyqa.zip

As requested the source files of the second patch.

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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

It seems that none of the tests exercise the "rescue" method.


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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

Confirmed - this also happens with the original code, I will ask Mike Powell to provide us with a function exercising rescue. You are probably suspicious whether the Java rescue works, as am I.

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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

In fact I'm more worried about introducing bugs that will go unnoticed. ;)


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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

Now I remember that I debugged rescue (and removed a nasty infinite loop) testing MinusElli with GoalType.MAXIMIZE before I fixed the
GoalType.MAXIMIZE handling. Testing MinusElli with GoalType.MINIMIZE still calls rescue:

  @Test
    public void testRescue() {
        double[] startPoint = point(DIM,1.0);
        double[][] boundaries = null;
        RealPointValuePair expected =
            new RealPointValuePair(point(DIM,0.0),-7.5072566333E53);
        doTest(new MinusElli(), startPoint, boundaries,
                GoalType.MINIMIZE,
                1e45, 1e24, 1000, expected);
    }
But parallel testing with the original revealed a problem, so please wait a few hours before working on rescue, I will fix it soon.

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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

There's no hurry. I'm not going to stop sleeping until the conversion is done; there is so much to do...
I've also started reading the reference [paper|http://www.optimization-online.org/DB_FILE/2010/05/2616.pdf] in the hope to figure the algorithm bits out of the Fortran gigantic functions.


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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

Dr. Dietmar Wolz updated MATH-621:
----------------------------------

    Attachment: bobyqav0.3.zip

rescue was as I feared not correct, the fixed version v0.3 behaves exactly as the original.

A breakup of the working area in separate double arrays should be straightforward, but still some work because of the nasty loop counting starting with 1.

Something like
     double[] xbase = new double[n];
        double[] xpt = new double[n * npt];
        double[] fval = new double[npt];
        double[] xopt = new double[n];
        double[] gopt = new double[n];
        double[] hq = new double[n * np / 2];
        double[] pq = new double[npt];
        double[] bmat = new double[ndim * n];
        double[] zmat = new double[npt * (npt - np)];
        double[] sl = new double[n];
        double[] su = new double[n];
        double[] xnew = new double[n];
        double[] xalt = new double[n];
        double[] d__ = new double[n];
        double[] vlag = new double[ndim];
        double[] w = new double[?];

Class ScopePtr could then be removed and the code should get even faster.

The "gotos"/ switches are much harder to eliminate.

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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

Luc Maisonobe commented on MATH-621:
------------------------------------

The Software Grant from prof. M.J.D. Powell has been filed in Apache Software Foundation records.
So this administrative step is over, we can include the code as soon as we want to.

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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

Dr. Dietmar Wolz updated MATH-621:
----------------------------------

    Attachment: bobyqaoptimizer0.4.zip

The attached new version contains three variants of BOBYQA implementing the
MultivariateRealOptimizer together with their associated unit tests:

BOBYQAOptimizerOld - essentially the previous version 0.3 with minor adaptions
in the unit tests added for comparison.

BOBYQAOptimizer - the actual version I use myself - all "pointers" are replaced
by Java arrays. This version is much easier to read and faster than the old
one. Nevertheless the "finite state machine logic" realized by the original
code using gotos is still there - in Java realized using switch/case statements.

BOBYQAOptimizerC - a version showing how MultivariateRealOptimizer can be implemented using the C-port of BOBYQA from the dlib library. The C++-code doing the mapping from Java to C++ to Java via JNI is also included.

Some remarks:

- all three versions are semantically equivalent - at least from the point of
the actual unit test coverage.

- the new Java version is about 30% faster than the old one - array access is
cheaper than method calls simulating pointer arithmetic.

- I observed a significant change of behaviour when statements like
a = a+(b...) are replaced by a += (b...). Subtle accuracy differences add up
during the optimization process.

- The C version was tested both on Mac (Snow Leopard) and Windows7,
both for 32 and 64-bit Java. For 64bit the Microsoft C++-compiler produced correct
results only if optimization is switched off completely, on the Mac the
gnu compiler works correctly using -O3.

- On the Mac (a Macbook pro with a new sandy bridge processor) the C-version
performs the unit tests three times faster than the (new) Java version.
The difference on Win7 is much smaller, since I couldn't use compiler optimization
there yet. The performance difference is not significant for my own application of the algo (space flight trajectory optimization) because of the high cost for the eval function. But this is perhaps not true for all other applications.

So if we want to include BOBYQA in commons.math in my opinion we shouldn't
neglect performance issues generally. Even a direct port of the code has a significant
performance disadvantage, any refactoring should try to avoid adding too much
additional performance bottlenecks.

> 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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

{quote}
BOBYQAOptimizer - the actual version I use myself - all "pointers" are replaced
by Java arrays. This version is much easier to read and faster than the old
one.
{quote}

:( It's a pity that you didn't mention this version earlier; I already spent quite a few hours replacing the "ScopedPtr" variables. Only a few of them remains in my working version: namely, those that are created as offsets in "w" before calling "trsbox", "rescue", "altmov" and "update".
Since I also made a few other changes along the way, I don't feel like starting all (almost) over again...
Hence, I'll continue with my incremental changes; but, at some point, I could use some help to convert the state machine code into proper function calls.

IMO, we should first arrive at a clearer code before worrying about performance (the more so that, as you pointed out, this algorithm will probably be put to use when function evaluation is expensive, overwhelming the optimizer's code running time).

The refactoring from efficient Fortran to (very probably less efficient) Java is a big effort but it's indispensable: If it were not to become understandable and maintainable, I don't see the point in including it in CM; you could just provide the straight translation in a JAR file and people would use it as a black box.



> 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

Phil Steitz commented on MATH-621:
----------------------------------

I agree strongly with Gilles comment on maintainability.  At apache, our goal is to develop software that can be maintained by a group of volunteers that changes over time.  In [math], that means algorithms need to be documented and it has to be possible for a Java developer with sufficient mathematical knowledge to read the references and javadoc and make sense of the code.

> 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

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-621) BOBYQA is missing in optimization

AD_LB (Jira)
In reply to this post by AD_LB (Jira)

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

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


> 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

       
12345