I love the simplex method

[fivemack]

The simplex method is a recipe which instructs an N-dimensional triangular amoeba in how to move to the position in N-dimensional space that it likes best. Thinking in N dimensions is difficult, but all you have to know is that an N-dimensional triangular amoeba has N+1 corners, and that if you look at all but one of the corners they define something which behaves a bit like the face of a solid polyhedron.

The recipe is:

Find the corner that you like least; call it W

Figure out the direction which takes W from its current position through the mid-point of the 'face' defined by all the other, better corners. Move along this direction; when you're half-way to the mid-point, call your position C. When you're at the mid-point, call it M, and say that you've moved 1 unit. When you've moved 2 units, call your position R; when you've moved four, call your position E.

If you liked R better than you liked W, check if you liked E even more; if so, move corner W to E, otherwise move corner W to R.

If R was inferior to W, check if C is nonetheless better than R; if so, move W to C.

And if E, R and C are all inferior to W, scrunch up by moving every one of your corners half-way towards your current absolute favourite corner G.

Repeat, and continue repeating until all your corners are immersed in equally high-quality happiness.

For the last month or so I've been wrestling with a particular problem at work, trying strategem after stratagem and cunning plan after cunning plan to find the best possible solution.

On Wednesday I gave up and let the amoeba crawl away at the problem starting from the best solution I'd had to date. By lunchtime it had managed to find a significantly better one, but by Thursday morning it had got stuck; so I started it off again, from the position that I'd started at back in September, and by teatime it had crawled to a position significantly better even that Wednesday's. It is still crawling; the simplex method is not very fast.

So, the simplex method is very useful, but it's slightly humiliating to be out-thought by so straightforwardly programmed an amoeba.

Comments

[ipsi-digit.livejournal.com]

Ah, that's what I did in 1988, coded in C from the Fortran listing. If I remember correctly, I found searching for optimum went fastest when I squared the results of each evaluation the function. I didn't have that many variables, only four I think, so the overhead wasn't too severe. My problem was finding a custom optimum temperature compensation network for each crystal oscillator in a production environment. It worked rather well.

I originally did the coding at home on a Commodore C64 and the results were good. A typical run took only 145 seconds. On the 4.7MHz PC at work, it took 296 seconds. A few years later on my 12 MHz '286' it took about 90 seconds. When I added in a 287 math coprocessor it took only 15 seconds. Today, on my dinky 1.4GHz Athlon, it's less than 8mS. I really don't have a good way to measure anything this fast so it may be faster.

With your 100+ variables, the squaring might add a little computing time, but the convergence to optimum may go faster.

I also found setting hard limits on the variable values drastically affected convergence time or prevented convergence altogether. It was much better to add in a squared error term for each 'out of range' variable to the function results. I'd have to go back to the source code to see exactly how I handled this, though.

Anyway, thanks for the reminder!

[fivemack.livejournal.com]

I like the pictures on your journal, particularly the anemone; I'm just slightly wondering how you came to find my page, and whether I know you in the physical world; feel free not to answer if you'd rather not, or to tom@womack.net if you'd rather not in public.

I'm now using about 250 variables, and with the objective function being itself a rather complicated optimisation (I'm trying to calibrate a detector, by the naively-ideal process of optimising the calibration values so that a mismatch measure given by a crystallographic program is minimised) the compute times are several days on a 2.4GHz dual-core Opteron; a dozen or so thousand iterations at 30 seconds each.

At least it gives me a nice feeling to come in in the morning and have freshly-baked minima-so-far delivered to my email; though the temptation to watch every twenty minutes the state of a job that you know won't complete until Monday is surprisingly hard to resist. Small incremental rewards, the conditioning technique of choice ...