Brent's Principal Axis Algorithm
Dear all, I've started a Google code project (http://code.google.com/p/pypraxis/) to provide a Python interface to Brent's principal axis algorithm. It's basically a wrapper around some Fortran code from http://www.netlib.org/opt/. Brent's algorithm minimizes a function of several variables without calculating derivatives - not to be mistaken for scipy.optimize.brent, that only performs single-variable minimization. The algorithm typically outperforms other derivative- and gradient-free algorithms (Brent, 2002; http://wwwmaths.anu.edu.au/~brent/pub/pub011.html). In my experience, it converges substantially faster than fmin and fmin_powell from scipy.optimize when fitting models with 5 to 15 free parameters to experimental data. Notably, Mathematica uses this algorithm for minimization without derivatives (http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationP...). I've provided some test cases and a wrapper that allow to compare it directly to the existing algorithms from scipy.optimize. Let me know if you think that the code could be a candidate for integration into scipy.optimize. It would obviously require some work to make it conform with the other functions that are already present. Best Christoph -----WIBR-EMAIL----- This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the system management (it.support@wibr.ucl.ac.uk). --------***---------
On Tue, Sep 8, 2009 at 12:44, Christoph Schmidt-Hieber<c.schmidt-hieber@ucl.ac.uk> wrote:
Dear all, I've started a Google code project (http://code.google.com/p/pypraxis/) to provide a Python interface to Brent's principal axis algorithm. It's basically a wrapper around some Fortran code from http://www.netlib.org/opt/. Brent's algorithm minimizes a function of several variables without calculating derivatives - not to be mistaken for scipy.optimize.brent, that only performs single-variable minimization. The algorithm typically outperforms other derivative- and gradient-free algorithms (Brent, 2002; http://wwwmaths.anu.edu.au/~brent/pub/pub011.html). In my experience, it converges substantially faster than fmin and fmin_powell from scipy.optimize when fitting models with 5 to 15 free parameters to experimental data. Notably, Mathematica uses this algorithm for minimization without derivatives (http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationP...). I've provided some test cases and a wrapper that allow to compare it directly to the existing algorithms from scipy.optimize. Let me know if you think that the code could be a candidate for integration into scipy.optimize. It would obviously require some work to make it conform with the other functions that are already present.
That would be great! Unfortunately, there is no license attached to praxis.f, so it cannot be integrated into scipy until we find a suitably licensed implementation of the algorithm. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
Robert Kern wrote:
On Tue, Sep 8, 2009 at 12:44, Christoph Schmidt-Hieber<c.schmidt-hieber@ucl.ac.uk> wrote:
Dear all, I've started a Google code project (http://code.google.com/p/pypraxis/) to provide a Python interface to Brent's principal axis algorithm. It's basically a wrapper around some Fortran code from http://www.netlib.org/opt/. Brent's algorithm minimizes a function of several variables without calculating derivatives - not to be mistaken for scipy.optimize.brent, that only performs single-variable minimization. The algorithm typically outperforms other derivative- and gradient-free algorithms (Brent, 2002; http://wwwmaths.anu.edu.au/~brent/pub/pub011.html). In my experience, it converges substantially faster than fmin and fmin_powell from scipy.optimize when fitting models with 5 to 15 free parameters to experimental data. Notably, Mathematica uses this algorithm for minimization without derivatives (http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationP...). I've provided some test cases and a wrapper that allow to compare it directly to the existing algorithms from scipy.optimize. Let me know if you think that the code could be a candidate for integration into scipy.optimize. It would obviously require some work to make it conform with the other functions that are already present.
That would be great! Unfortunately, there is no license attached to praxis.f, so it cannot be integrated into scipy until we find a suitably licensed implementation of the algorithm.
http://wwwmaths.anu.edu.au/~brent/software.html This seems to imply that the code may be used freely; but it wouldn't hurt to ask the author. Eric
On Tue, Sep 8, 2009 at 7:28 PM, Eric Firing <efiring@hawaii.edu> wrote:
On Tue, Sep 8, 2009 at 12:44, Christoph Schmidt-Hieber<c.schmidt-hieber@ucl.ac.uk> wrote:
Dear all, I've started a Google code project (http://code.google.com/p/pypraxis/) to provide a Python interface to Brent's principal axis algorithm. It's basically a wrapper around some Fortran code from http://www.netlib.org/opt/. Brent's algorithm minimizes a function of several variables without calculating derivatives - not to be mistaken for scipy.optimize.brent, that only performs single-variable minimization. The algorithm typically outperforms other derivative- and gradient-free algorithms (Brent, 2002; http://wwwmaths.anu.edu.au/~brent/pub/pub011.html). In my experience, it converges substantially faster than fmin and fmin_powell from scipy.optimize when fitting models with 5 to 15 free
( http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationP... ). I've provided some test cases and a wrapper that allow to compare it
Robert Kern wrote: parameters to experimental data. Notably, Mathematica uses this algorithm for minimization without derivatives directly to the existing algorithms from scipy.optimize. Let me know if you think that the code could be a candidate for integration into scipy.optimize. It would obviously require some work to make it conform with the other functions that are already present.
That would be great! Unfortunately, there is no license attached to praxis.f, so it cannot be integrated into scipy until we find a suitably licensed implementation of the algorithm.
http://wwwmaths.anu.edu.au/~brent/software.html
This seems to imply that the code may be used freely; but it wouldn't hurt to ask the author.
No it doesn't, it implies that most of the code is GPL. ISTR looking at the random number generation code on Brent's site and coming to a stop after that bit. It may be that Brent would be open to relicensing the code, or that the code in guestion is not just free, but BSD free, but I think it would be advisable to contact Brent and find out. Chuck
Robert Kern skrev:
That would be great! Unfortunately, there is no license attached to praxis.f, so it cannot be integrated into scipy until we find a suitably licensed implementation of the algorithm.
I am not a lawyer, but --- I'd say if someone puts his own code on the netlib repository for free download, without even making a copyright notice, it can be seen as public domain. Sturla
On Tue, Sep 8, 2009 at 23:34, Sturla Molden<sturla@molden.no> wrote:
Robert Kern skrev:
That would be great! Unfortunately, there is no license attached to praxis.f, so it cannot be integrated into scipy until we find a suitably licensed implementation of the algorithm.
I am not a lawyer, but --- I'd say if someone puts his own code on the netlib repository for free download, without even making a copyright notice, it can be seen as public domain.
That is entirely contrary to copyright law. Since the Berne Convetion in 1973, works are copyrighted at the moment of creation. One does not need to specify that it is copyrighted. In order for you to distribute it, the author must explicitly give you a license. Silence does not imply consent. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
2009/9/9 Robert Kern <robert.kern@gmail.com>:
On Tue, Sep 8, 2009 at 23:34, Sturla Molden<sturla@molden.no> wrote:
Robert Kern skrev:
That would be great! Unfortunately, there is no license attached to praxis.f, so it cannot be integrated into scipy until we find a suitably licensed implementation of the algorithm.
I am not a lawyer, but --- I'd say if someone puts his own code on the netlib repository for free download, without even making a copyright notice, it can be seen as public domain.
That is entirely contrary to copyright law. Since the Berne Convetion in 1973, works are copyrighted at the moment of creation. One does not need to specify that it is copyrighted. In order for you to distribute it, the author must explicitly give you a license. Silence does not imply consent.
To return to the original question, yes, it would be great if this could be included in scipy optimize. If it needs to be rewritten, if somebody makes a clean description of how to do it by looking at the code, I'm sure some people would be willing to reimplement it in C for scipy. If Brent indicates the code is GPL, you can write a scikit that extends scipy.optimize to offer this, as inclusion in scipy is not possible, but I'm not sure GPL code really means all should be cleanly reimplemented so as to allow inclusion in scipy. (GPL can use BSD code after all, so the scikit would be GPL and independant). Benny
Benny Malengier skrev:
To return to the original question, yes, it would be great if this could be included in scipy optimize. If it needs to be rewritten, if somebody makes a clean description of how to do it by looking at the code, I'm sure some people would be willing to reimplement it in C for scipy.
I took a quick look at the code. It seems to optimize with Brent's method along one dimension, jump randomly to a point in the vicinity, optimize along conjugate dimensions, etc. I should not be too hard to reimplement with a version of brent for one dimension and a prng. S.M.
Wed, 09 Sep 2009 06:34:24 +0200, Sturla Molden wrote:
Robert Kern skrev:
That would be great! Unfortunately, there is no license attached to praxis.f, so it cannot be integrated into scipy until we find a suitably licensed implementation of the algorithm.
I am not a lawyer, but --- I'd say if someone puts his own code on the netlib repository for free download, without even making a copyright notice, it can be seen as public domain.
This is not true in practice (nor in theory as Robert notes). The netlib repository contains many pieces of code licensed for example under the ACM license (academic non-commercial use only, restrictions on modification), copyright residing with ACM. Netlib just fails to notify people about this. These source files of course don't contain any mention of copyright, but you find about it by looking at the calgo.acm.org list. (Some of them may be in public domain, being works of US government employees, but IANAL.) -- Pauli Virtanen
Dear all, thanks for all your comments. In the meantime, I've switched to a Fortran90 implementation by John Burkardt. I'm aware that this adds an additional layer of license issues, but I believe that there are some advantages outweighing this: - The code is more portable than the F77 version; I've tested on GNU/Linux 32bit and 64 bit and on Mac OS X. - The code is more readable, and it should be more straightforward to port it to C if anyone wants to follow Benny's suggestion. - Most of the code on Burkardt's page is under the LGPL, so I suppose that this particular file is just not LGPL'd because the license status of the original F77 file is unclear. Cheers Christoph P.S. The mails that I write with my default mail client (alpine) don't seem to get through to this mailing list. Any ideas what I might be doing wrong? -----WIBR-EMAIL----- This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the system management (it.support@wibr.ucl.ac.uk). --------***---------
participants (7)
-
Benny Malengier -
Charles R Harris -
Christoph Schmidt-Hieber -
Eric Firing -
Pauli Virtanen -
Robert Kern -
Sturla Molden