Downhill Simplex Method Some time ago, Leonard Howell asked me if I had an APL program that implements the Nelder-Mead downhill simplex method for finding the minimum of an n-dimensional function. In response, I adapted an algorithm from the book Numerical Recipes in C to APL. I periodically get requests from other APLers for the same program, ergo this web page. (Also, people can't figure out how to use the program, so I've added an example.) The authors of NRC claim copyright to the programs in their book and to any "source-code-to-source-code" translations into other languages (though not to "reëxpressions" of the ideas in their programs). My APL code looks a whole lot different than their C program and uses some different techniques, but I couldn't tell you whether I've "reëxpressed" their ideas or merely translated them. To avoid violating their copyright, you should buy a copy of their book before using my DSMIN program. This is something I can heartily endorse--the book is a great source of useful numerical algorithms that belongs on every mathematical programmer's bookshelf. The authors' practical and humorous attitude make it a delight to read. Plus, you'll need the book for instructions on choosing the arguments and caveats on the algorithm. |
||
From: Jim Weigang |
||
Some users have had trouble figuring out how to use DSMIN (and it even takes me a while to figure it out), so here's an example. As described in the comments, the minimization function should be monadic, accept a matrix having an x-vector in each row, and return a vector of y-values. Here's a suitable function: The y value is just the sum of two terms that have minima at x_{1}=3 and x_{2}=0. The argument to the function should be a matrix with each row containing an x_{1},x_{2} pair, as in: The minimization function's name (as a character string) is the left argument to DSMIN; the right argument is the initial simplex (n+1 points in n-space) and the stopping criterion. The result is the final simplex, with the point having the lowest y-value in the first row. So the minimum found by DSMIN is at x_{1}=2.999998186 and x_{2}=-0.000005463061221, which is 3 and 0 to about five decimal places. (The stopping criterion is the fractional change in y-value, so it doesn't guarantee a specific precision in the x-values.) The NRC authors advise calling the function a second time with the first vertex being replaced by the minimum found in the first call: DSMIN can also be used to maximize a function. Simply negate the result of your FCN1, either in the definition or by putting a minus sign before the function name in the left argument of DSMIN. Any questions? |
||
Note: The APL code on this page can be extracted without you
having to retype it. See "Downloading Code" for instructions. |
||
JimW's Home Page |