Bug 80647 - request to add Nelder Mead simplex to SOLVER for small dimension non-linear problems
Summary: request to add Nelder Mead simplex to SOLVER for small dimension non-linear p...
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
4.2.4.2 release
Hardware: All All
: medium enhancement
Assignee: Not Assigned
URL:
Whiteboard:
Keywords:
Depends on:
Blocks: Solver
  Show dependency treegraph
 
Reported: 2014-06-28 20:14 UTC by Charlie
Modified: 2017-10-22 21:14 UTC (History)
2 users (show)

See Also:
Crash report or crash signature:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Charlie 2014-06-28 20:14:15 UTC
I have been trying to use the solver in Calc to find the minimum of a non-linear function calculated in the spreadsheet found here:
http://claub.net/temp/Solver-crashes-CALC.xls

The optimized quantity is a sum-of-squares error, cell A134, and the value in this cell should fall to 10 or less. I set up the solver to find a minimum by manipulating the values in cells F13 through F17. The initial values I choose are F13=1.0 and the other set to zero. I am using Calc under Windows 8, version 4.2.4.2, Build ID: 63150712c6d317d27ce2db16eb94c2f3d7b699f8.

I have tried both the DEPS and SCO algorithms. The solver runs for what seems like a long time (more than a minute on my machine) and makes some progress reducing the error. Then it, and calc, crash and close. This happens every time.

What I find strange is that I can run this exact same problem with the same initial conditions using the Excel solver (GRG nonlienar algorithm) and it finishes in about 1-2 seconds and never crashes.

The Calc SOLVER really should include a basic, Nelder-Mead simplex based, non-linear optimization option. This works very reliably for non-pathological optimization problems of modest dimension (e.g. less than 15-20 variables). I have applied that algorithm to the problem in the spreadsheet linked above with 100% success for instance, and it would be much faster than these bizarre evolutionary algorithms for my 5-variable problem. I have some experience coding the Nelder-Mead algorithm and know of some slight modifications from the literature that help it to work better than the original implementation and that keep it from crashing in the case that the simplex collapses or a duplicate point (within machine precision) is created during the minimization. Please contact me for details here:
http://audio.claub.net/contact_form.html

Adding the (very reliable) Nelder Mead simplex algorithm to the available non-linear optimization engines in the Solver would round out its capabilities nicely and should not be difficult to code (the algorithm is not complicated).

Thanks,

Charlie
Comment 1 Julien Nabet 2014-06-28 20:42:37 UTC
Winfried: I don't know if this kind of function exists on Excel but thought you might have be interested in this bugtracker.
Comment 2 Owen Genat (retired) 2014-06-29 02:51:45 UTC
Confirmed insofar that the Nelder-Mead simplex algorithm does not appear to be available. Status set to NEW. Platform / architecture set to All / All. Related discussion with respect to this particular spreadsheet can be found:

- http://en.libreofficeforum.org/node/8371

I provide some test settings, times, and results in the thread for the DEPS and SCO algorithms. The crash under Windows 8 I could not reproduce (under Debian x86_64) and in any case is a separate issue requiring a separate bug report (please file one Charlie, and thanks for filing this one).