Nelder-Mead simplex optimization using only worksheet functions -> done!

[charlielaub]

I have experimented with looping/iterating structures in Excel in the past and have created a couple of nifty applications for my hobbies that come close to what you get with programming (e.g. VBA) but using only worksheet functions. I decided to see if I could do something a little more challenging, so I've managed to come up with a way using only worksheet functions to implement the Nelder-Mead simplex (non-linear) optimization method. This took a lot of head scratching and analysis of the algorithm, but I did figure out how to make it work.

Some key elements include a variable that tracks the current "line" of the program (borrowing that terminology from high level programming), and a decision table that is consulted at each step to see what to do next - this can include terminating the iterations, branching to a new "line", or stepping on to the next line. The table also aids with "if..then" types of decisions that are often employed in programming.

I have included a link to the spreadsheet below (works in Excel 2003 or later) if you would like to check it out. I would love to know if anyone else out there is interested in this kind of thing! How far could one push this approach? I just made up this implementation out of the blue, but I would guess that one could come up with a structured way to implement all sorts of high level programming in this way.

The Excel file at the link below is set up to solve DeJong's function in 5 variables and the solution vector to this problem is: 1, -2, 3, 4, 5. I have nicknamed the method "Loopy" as a play on "to iterate" and the fact that I must have been loopy to do this! To run the optimization/minimization, go to the LoopyControl worksheet. Enter "0" in cell A3. Next press F9 to "reset" the program. Next enter "1" in cell A3. Again press F9 to execute the program. The spreadsheet it set to iterate 10,000 times and this should be sufficient to find the solution. The iteration will stop when the error falls below the "STOP ERROR" (cell A15 in the LooptControl sheet). Worksheet functions are not fast, so please be patient unless you have a new machine. There may be an iteration counter in the bottom bar of Excel that counts up as the algorithm marches along. After the minimization has completed there is a plot of the progress of the minimization that can be found in the ResultPlot sheet. The sheet "InputOutput" contains cells for a guess at the solution (you can enter most anything) and the "best fit" result will appear there when the program execution completes. There is no protection or hidden cells - everything is shown. This means that you can easily break the spreadsheet, so only change the cells that are in bold, blue type unless you really know what you are doing.

Loopy can easily be modified to solve other 5-dimension (only) non-linear problems that can be described with a single valued "error" like a sum-of-squares-error or similar. In the Calculations worksheet, there is a blue box containing a few lines that form part of the objective function. The values of the 5 variables are taken from cells A15 through A19. The program tries to optimize the value in cell A47. To use a new function, use the area in the blue box (insert new rows as necessary) to calculate it and code the resulting error into cell A47. For instance I use another incarnation of this spreadsheet to perform a 5-variable nonlinear data fitting problem, on 100 data points.

I'm happy to help people out if you encounter questions while checking out Loopy. FYI: this seems to only work in Excel (not OO or LO Calc or other Excel clones where Err:523 pops up).

-Charlie

Download Loopy:
http://claub.net/Loopy/Loopy_v2.0.xls

 

[charlielaub]

Check this:
http://www.mimuw.edu.pl/~jty/MrExcel/errotest.xlsx

J.Ty.

I opened the file in Excel. Sheet1 cell A1 says "Excel".

I saved the file, opened the file in LibreOffice Calc. Sheet1 cell A1 says "Excel".

I then opened the file in OpenOffice Calc. Sheet1 cell A1 says "Excel".

Doesn't work for me!

Maybe you can use different functions, one that isn't recognized by Excel to test for Calc, and the opposite to test for Excel. I think that is what you are trying to do, so maybe this approach is no longer valid.

Versions:
ApacheOpenOffice 4.1.0
LibreOffice Version: 4.2.4.2
Excel version 15.0.4615.1000 (part of Office365)

 

[J.Ty.]

Then I do not understand any more. Perhaps the difference is that I do not save the file. I open it "as is" in both systems and it reports, which one it is.
I use the newest LibreOffice and Excel 2010 - this might make the difference.

J.Ty.

 

[J.Ty.]

Function INFO is the solution.
The following formulas return different results for Excel and LibreOffice:

=INFO("release")
=INFO("system")
 =INFO("osversion")

J.Ty.

 

[charlielaub]

Function INFO is the solution.
The following formulas return different results for Excel and LibreOffice:

=INFO("release")
=INFO("system")
 =INFO("osversion")

J.Ty.

I found something that works for me. What is needed is a function that works fine in one program (e.g. Excel) but is not recognized by the other (e.g. Calc) and so returns an error. The INFO("origin") function works for me, for the versions of Excel and Calc that I have on my machine.

The complete formula that I use is:

=IF(ISERROR(INFO("origin")), "Calc", "Excel")

The downside is that I can't know or test for all versions of each program. Even if this difference allows one to distinguish the two programs now, if INFO("origin") is implemented in Calc in the future the ability to distinguish one program from the other using this formula will be lost.

The other possibility I see is INFO("version"). Excel returns something like 15.0 while calc returns a 40 character string consisting of lower case letters and numbers with no decimal point. So perhaps based on the general size of what is returned you could always distinguish the two programs using this formula.

-Charlie