Hi Everyone, it seemed to me that the folder scipy/optimize/benchmarks/ was rather lonely, with only one file in it, so I wrote a script which benchmarks the scipy minimizers. The script simpy runs all the optimizers on the Rosenbrock function and prints various information. Here's the output sorted by minimization time Optimizer benchmark on the Rosenbrock function sorted by time L-BFGS-B pass nfev 6 njev 0 nhev 0 time 0.000691891 TNC pass nfev 13 njev 0 nhev 0 time 0.00105786 Newton-CG pass nfev 17 njev 27 nhev 11 time 0.00400996 SLSQP pass nfev 41 njev 27 nhev 0 time 0.00410509 trust-ncg pass nfev 18 njev 16 nhev 15 time 0.00415802 dogleg pass nfev 16 njev 14 nhev 13 time 0.00426602 CG pass nfev 63 njev 63 nhev 0 time 0.0065279 BFGS pass nfev 44 njev 44 nhev 0 time 0.0070231 Powell pass nfev 524 njev 0 nhev 0 time 0.0262001 COBYLA fail nfev 1000 njev 0 nhev 0 time 0.026603 The results are interesting with L-BFGS-B outperforming all the others by a significant margin in both total time and total number of function calls. I have not submitted a pull request because I have no idea how to fit what I've done into an existing benchmarking framework (if there is one). I will submit the pull request if there is interest. In my opinion it would be really useful to have a long set of benchmarks to see how all the minimizers perform on different types of minimization problems. Here is the script in my scipy fork https://github.com/js850/scipy/blob/benchmarks/scipy/optimize/benchmarks/ben... Best wishes, Jake
On Mon, Nov 18, 2013 at 10:20 AM, Jacob Stevenson <jstevenson131@gmail.com> wrote:
Hi Everyone, it seemed to me that the folder scipy/optimize/benchmarks/ was rather lonely, with only one file in it, so I wrote a script which benchmarks the scipy minimizers. The script simpy runs all the optimizers on the Rosenbrock function and prints various information. Here's the output sorted by minimization time
Optimizer benchmark on the Rosenbrock function sorted by time L-BFGS-B pass nfev 6 njev 0 nhev 0 time 0.000691891 TNC pass nfev 13 njev 0 nhev 0 time 0.00105786 Newton-CG pass nfev 17 njev 27 nhev 11 time 0.00400996 SLSQP pass nfev 41 njev 27 nhev 0 time 0.00410509 trust-ncg pass nfev 18 njev 16 nhev 15 time 0.00415802 dogleg pass nfev 16 njev 14 nhev 13 time 0.00426602 CG pass nfev 63 njev 63 nhev 0 time 0.0065279 BFGS pass nfev 44 njev 44 nhev 0 time 0.0070231 Powell pass nfev 524 njev 0 nhev 0 time 0.0262001 COBYLA fail nfev 1000 njev 0 nhev 0 time 0.026603
The results are interesting with L-BFGS-B outperforming all the others by a significant margin in both total time and total number of function calls.
I have not submitted a pull request because I have no idea how to fit what I've done into an existing benchmarking framework (if there is one). I will submit the pull request if there is interest. In my opinion it would be really useful to have a long set of benchmarks to see how all the minimizers perform on different types of minimization problems.
Here is the script in my scipy fork
https://github.com/js850/scipy/blob/benchmarks/scipy/optimize/benchmarks/ben...
I think showing results for these kind of benchmarks would make a good addition to the documentation. It would be very helpful in chosing an optimizer. I'm hitting this question very often in statsmodels, both what optimizer works for me in a specific case, and what works well enough in general to use as a default for the users of statsmodels. For example a while ago Andrea Gavana linked to results for global optimizers (mostly outside scipy, unfortunately we didn't get any new ones besides basinhopping) http://infinity77.net/global_optimization/index.html Another possibility would be to turn some of the benchmark cases into unit tests. In a github issue for scipy.stats we were also discussing to add extra unit tests that are not part of a regular test run, but could test extra things. The specific case was adding "fuzz tests" that just try out many different random values for the parameters. Besides speed it would also be interesting to benchmark how robust they are. At least for some cases that I try out for statsmodels, I need to use a boring fmin (Nelder-Mead) to get around bad behavior or bad starting values. For example, which optimizers in which scipy version survive a `nan` or an `inf` in some range of the parameter space? (My impression is that this is improving with each scipy version.) Josef
Best wishes, Jake _______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-dev
On Mon, Nov 18, 2013 at 10:20 AM, Jacob Stevenson <jstevenson131@gmail.com> wrote:
Hi Everyone, it seemed to me that the folder scipy/optimize/benchmarks/ was rather lonely, with only one file in it, so I wrote a script which benchmarks the scipy minimizers. The script simpy runs all the optimizers on the Rosenbrock function and prints various information. Here's the output sorted by minimization time
Optimizer benchmark on the Rosenbrock function sorted by time L-BFGS-B pass nfev 6 njev 0 nhev 0 time 0.000691891 TNC pass nfev 13 njev 0 nhev 0 time 0.00105786 Newton-CG pass nfev 17 njev 27 nhev 11 time 0.00400996 SLSQP pass nfev 41 njev 27 nhev 0 time 0.00410509 trust-ncg pass nfev 18 njev 16 nhev 15 time 0.00415802 dogleg pass nfev 16 njev 14 nhev 13 time 0.00426602 CG pass nfev 63 njev 63 nhev 0 time 0.0065279 BFGS pass nfev 44 njev 44 nhev 0 time 0.0070231 Powell pass nfev 524 njev 0 nhev 0 time 0.0262001 COBYLA fail nfev 1000 njev 0 nhev 0 time 0.026603
The results are interesting with L-BFGS-B outperforming all the others by a significant margin in both total time and total number of function calls.
I have not submitted a pull request because I have no idea how to fit what I've done into an existing benchmarking framework (if there is one). I will submit the pull request if there is interest. In my opinion it would be really useful to have a long set of benchmarks to see how all the minimizers perform on different types of minimization problems.
Here is the script in my scipy fork
https://github.com/js850/scipy/blob/benchmarks/scipy/optimize/benchmarks/ben...
Best wishes, Jake
I'll make a couple of comments, before I forget everything I learned about Rosenbrock and about the scipy optimization framework when I implemented the dogleg and trust-ncg functions from the Nocedal and Wright book... First, thanks for adding these benchmarks! This seems like a natural comparison to have available in scipy, and I suspect that this has not been done earlier because Denis has only recently created a general framework that allows interchangeable minimization functions. I hope that something like this will go into scipy. I've written similar one-off benchmarking code for algopy https://github.com/b45ch1/algopy/tree/master/documentation/sphinx/examples/m... before I'd started contributing to scipy. This includes the Rosenbrock function as well as a couple of other good benchmarking functions, and easy and hard starting guesses for each; the licenses are compatible so maybe this would be useful for future scipy minimize() benchmarks. Benchmarks are an endless source of nitpicking, so I'll mention two nitpicks for your code :) First, the different minimize() functions might differ in how close they get to the optimum, before they report that they have successfully converged. The nth dimensional rosenbrock function has its minimum at (1, 1, ..., 1) so this should be not so hard to compare closeness. Second and possibly more importantly, the relative performances may change depending on whether the starting guess is easy vs. hard. Your starting point x0=[0.8, 1.2, 0.7] is relatively near (1, 1, 1) so it is "easy". Starting points that require walking around the Rosenbrock valley http://en.wikipedia.org/wiki/File:Rosenbrock_function.svg are more tricky, and the less clever minimization functions may outperform the more clever functions at easy starting guesses. Best, Alex
Would you be interested in more benchmarking problems? There should be a couple lists of problems within the thread for http://scicomp.stackexchange.com/questions/46/where-can-one-obtain-good-data.... (Disclaimer: I've moderated Computational Science Stack Exchange for a couple years with the goal of answering questions like, "Where do I find benchmark problems for numerical optimization?") The problem of benchmarking within optimization is pretty common, so you should be able to develop a fairly comprehensive suite of tests if you so desire. Geoff On Mon, Nov 18, 2013 at 8:05 AM, alex <argriffi@ncsu.edu> wrote:
On Mon, Nov 18, 2013 at 10:20 AM, Jacob Stevenson <jstevenson131@gmail.com> wrote:
Hi Everyone, it seemed to me that the folder scipy/optimize/benchmarks/ was rather lonely, with only one file in it, so I wrote a script which benchmarks the scipy minimizers. The script simpy runs all the optimizers on the Rosenbrock function and prints various information. Here's the output sorted by minimization time
Optimizer benchmark on the Rosenbrock function sorted by time L-BFGS-B pass nfev 6 njev 0 nhev 0 time 0.000691891 TNC pass nfev 13 njev 0 nhev 0 time 0.00105786 Newton-CG pass nfev 17 njev 27 nhev 11 time 0.00400996 SLSQP pass nfev 41 njev 27 nhev 0 time 0.00410509 trust-ncg pass nfev 18 njev 16 nhev 15 time 0.00415802 dogleg pass nfev 16 njev 14 nhev 13 time 0.00426602 CG pass nfev 63 njev 63 nhev 0 time 0.0065279 BFGS pass nfev 44 njev 44 nhev 0 time 0.0070231 Powell pass nfev 524 njev 0 nhev 0 time 0.0262001 COBYLA fail nfev 1000 njev 0 nhev 0 time 0.026603
The results are interesting with L-BFGS-B outperforming all the others by a significant margin in both total time and total number of function calls.
I have not submitted a pull request because I have no idea how to fit what I've done into an existing benchmarking framework (if there is one). I will submit the pull request if there is interest. In my opinion it would be really useful to have a long set of benchmarks to see how all the minimizers perform on different types of minimization problems.
Here is the script in my scipy fork
https://github.com/js850/scipy/blob/benchmarks/scipy/optimize/benchmarks/ben...
Best wishes, Jake
I'll make a couple of comments, before I forget everything I learned about Rosenbrock and about the scipy optimization framework when I implemented the dogleg and trust-ncg functions from the Nocedal and Wright book...
First, thanks for adding these benchmarks! This seems like a natural comparison to have available in scipy, and I suspect that this has not been done earlier because Denis has only recently created a general framework that allows interchangeable minimization functions. I hope that something like this will go into scipy.
I've written similar one-off benchmarking code for algopy
https://github.com/b45ch1/algopy/tree/master/documentation/sphinx/examples/m... before I'd started contributing to scipy. This includes the Rosenbrock function as well as a couple of other good benchmarking functions, and easy and hard starting guesses for each; the licenses are compatible so maybe this would be useful for future scipy minimize() benchmarks.
Benchmarks are an endless source of nitpicking, so I'll mention two nitpicks for your code :) First, the different minimize() functions might differ in how close they get to the optimum, before they report that they have successfully converged. The nth dimensional rosenbrock function has its minimum at (1, 1, ..., 1) so this should be not so hard to compare closeness. Second and possibly more importantly, the relative performances may change depending on whether the starting guess is easy vs. hard. Your starting point x0=[0.8, 1.2, 0.7] is relatively near (1, 1, 1) so it is "easy". Starting points that require walking around the Rosenbrock valley http://en.wikipedia.org/wiki/File:Rosenbrock_function.svg are more tricky, and the less clever minimization functions may outperform the more clever functions at easy starting guesses.
Best, Alex _______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-dev
-- Geoffrey Oxberry, Ph.D., E.I.T. goxberry@gmail.com
I added several more test functions to the benchmarking data (results are below). Taking into account advice from earlier replied, I also generalized the interface to easily make add new functions to test and to average over multiple starting points. My idea is that if this becomes part of the public repository more functions can easily be added (e.g. by any of you). We could even make several groups of benchmarks. e.g. problems with functions only, problems with gradients, problems with constraints, etc. Is this something people would want to see in scipy? Would you be interested in contributing if if it was a separate repository? Here is the link to the relevant code and the results from the new benchmarking. https://github.com/js850/scipy/blob/benchmarks/scipy/optimize/benchmarks/ben... --------------------------------------------------------- Optimizer benchmark: Rosenbrock function averaged over 10 starting configurations Optimizer nfail nfev njev nhev time --------------------------------------------------------- L-BFGS-B 0 35 0 0 0.00334594 SLSQP 0 51 35 0 0.00544584 BFGS 0 49 49 0 0.00776296 trust-ncg 0 45 40 39 0.0111956 Newton-CG 0 78 140 63 0.0229024 Powell 0 939 0 0 0.0497912 TNC 1 61 0 0 0.00444455 dogleg 3 17 15 14 0.00463629 CG 3 93 90 0 0.0100623 COBYLA 9 905 0 0 0.0247099 --------------------------------------------------------- Optimizer benchmark: simple quadratic function averaged over 10 starting configurations Optimizer nfail nfev njev nhev time --------------------------------------------------------- TNC 0 7 0 0 0.000121212 L-BFGS-B 0 3 0 0 0.000132966 SLSQP 0 3 2 0 0.000221419 CG 0 5 5 0 0.00023191 COBYLA 0 64 0 0 0.000245976 BFGS 0 4 4 0 0.000284338 trust-ncg 0 3 3 2 0.000300932 Newton-CG 0 3 4 2 0.000332808 dogleg 0 3 3 2 0.000438738 Powell 0 52 0 0 0.00148728 --------------------------------------------------------- Optimizer benchmark: function sum(x**2) + x[0] averaged over 10 starting configurations Optimizer nfail nfev njev nhev time --------------------------------------------------------- L-BFGS-B 0 3 0 0 0.000148368 TNC 0 12 0 0 0.000190687 SLSQP 0 3 2 0 0.000227571 CG 0 4 4 0 0.00024004 COBYLA 0 62 0 0 0.000283909 BFGS 0 3 3 0 0.000284839 trust-ncg 0 3 3 2 0.000315571 Newton-CG 0 3 4 2 0.000344849 dogleg 0 3 3 2 0.000449395 Powell 0 135 0 0 0.00436816 --------------------------------------------------------- Optimizer benchmark: 1d sin function averaged over 10 starting configurations Optimizer nfail nfev njev nhev time --------------------------------------------------------- COBYLA 0 23 0 0 0.000144291 TNC 0 10 0 0 0.000207186 L-BFGS-B 0 6 0 0 0.000222659 CG 0 5 5 0 0.000294614 SLSQP 0 4 3 0 0.000340533 BFGS 0 5 5 0 0.000469255 Powell 0 37 0 0 0.00122664 --------------------------------------------------------- Optimizer benchmark: Booth's function averaged over 10 starting configurations Optimizer nfail nfev njev nhev time --------------------------------------------------------- TNC 0 6 0 0 0.000252295 L-BFGS-B 0 5 0 0 0.000304174 CG 0 5 5 0 0.000353932 BFGS 0 5 5 0 0.000439787 SLSQP 0 7 5 0 0.000566912 COBYLA 0 63 0 0 0.000614142 Powell 0 67 0 0 0.00229499 checking gradient 7.00777666894e-06 --------------------------------------------------------- Optimizer benchmark: Beale's function averaged over 10 starting configurations Optimizer nfail nfev njev nhev time --------------------------------------------------------- L-BFGS-B 0 25 0 0 0.00166378 TNC 1 37 0 0 0.00172372 SLSQP 1 33 21 0 0.00265439 COBYLA 2 336 0 0 0.00415859 BFGS 3 180 180 0 0.0245004 CG 4 103 99 0 0.00788155 Powell 8 1829 0 0 0.071332 checking gradient 1.53950157701e-08 --------------------------------------------------------- Optimizer benchmark: 4 atom Lennard Jones potential averaged over 10 starting configurations Optimizer nfail nfev njev nhev time --------------------------------------------------------- L-BFGS-B 0 54 0 0 0.0231662 SLSQP 0 113 38 0 0.0295753 BFGS 0 73 73 0 0.0356844 Powell 0 2401 0 0 0.372276 CG 1 104 103 0 0.0457192 TNC 6 112 0 0 0.0459664 COBYLA 7 864 0 0 0.112254
On Mon, Nov 18, 2013 at 03:20:13PM +0000, Jacob Stevenson wrote:
The results are interesting with L-BFGS-B outperforming all the others by a significant margin in both total time and total number of function calls.
That seems right. BFGS/LBFGS should in general be prefered to other approaches if your problem is smooth without noisy gradient and you know nothing about the Hessian. A piece of warning: the clear cut win of L-BFGS will depend a bit on the function to optimize. Rosenbrock is amongst the nastiest function to optimize. On easer function (eg quadratic or close to quadratc) results will differ. By the way, a somewhat lengthy discussion on this, with benchmark scripts, can be found on http://scipy-lectures.github.io/advanced/mathematical_optimization/index.htm... G
I have a related question: does anybody knows of a simple minimizer function written in pure python or cython ? Are there native minimizers in scipy ? I'm asking this question because I need to optimize many small problems, where the overhead of calling the optimizing becomes non-negligible. I suspect I could achieve big performance gains, if I could call that function with compiled python code (using numba). Best, Pablo On Mon, Nov 18, 2013 at 5:34 PM, Gael Varoquaux < gael.varoquaux@normalesup.org> wrote:
On Mon, Nov 18, 2013 at 03:20:13PM +0000, Jacob Stevenson wrote:
The results are interesting with L-BFGS-B outperforming all the others by a significant margin in both total time and total number of function calls.
That seems right. BFGS/LBFGS should in general be prefered to other approaches if your problem is smooth without noisy gradient and you know nothing about the Hessian. A piece of warning: the clear cut win of L-BFGS will depend a bit on the function to optimize. Rosenbrock is amongst the nastiest function to optimize. On easer function (eg quadratic or close to quadratc) results will differ.
By the way, a somewhat lengthy discussion on this, with benchmark scripts, can be found on
http://scipy-lectures.github.io/advanced/mathematical_optimization/index.htm...
G _______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-dev
18.11.2013 18:56, Pablo Winant kirjoitti:
I have a related question: does anybody knows of a simple minimizer function written in pure python or cython ? Are there native minimizers in scipy ? I'm asking this question because I need to optimize many small problems, where the overhead of calling the optimizing becomes non-negligible. I suspect I could achieve big performance gains, if I could call that function with compiled python code (using numba).
Several of the minimizers in Scipy are pure-Python. You can take a look at the source code to see which ones (I don't remember from the top of my head the full list). -- Pauli Virtanen
Thank you. I'll have a look and see whether one of them can be compiled without too much hassle. By the way, the scipy lectures posted by Gael are really excellent. It's a pleasure to read them. Pablo On Mon, Nov 18, 2013 at 7:28 PM, Pauli Virtanen <pav@iki.fi> wrote:
18.11.2013 18:56, Pablo Winant kirjoitti:
I have a related question: does anybody knows of a simple minimizer function written in pure python or cython ? Are there native minimizers in scipy ? I'm asking this question because I need to optimize many small problems, where the overhead of calling the optimizing becomes non-negligible. I suspect I could achieve big performance gains, if I could call that function with compiled python code (using numba).
Several of the minimizers in Scipy are pure-Python. You can take a look at the source code to see which ones (I don't remember from the top of my head the full list).
-- Pauli Virtanen
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-dev
Jacob Stevenson a écrit :
I have not submitted a pull request because I have no idea how to fit what I've done into an existing benchmarking framework (if there is one). I will submit the pull request if there is interest. In my opinion it would be really useful to have a long set of benchmarks to see how all the minimizers perform on different types of minimization problems.
Here is the script in my scipy fork
https://github.com/js850/scipy/blob/benchmarks/scipy/optimize/benchmarks/ben...
I also think this could be useful. If you want to include this, I'd suggest to use numpy's benchmarking framework (see e.g. numpy.testing.Tester.bench) as this is done elsewhere (e.g. sparse.linalg).
participants (8)
-
alex -
Denis Laxalde -
Gael Varoquaux -
Geoff Oxberry -
Jacob Stevenson -
josef.pktd＠gmail.com -
Pablo Winant -
Pauli Virtanen