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

[del-c.livejournal.com]

How many dimensions does your problem have?

[rysmiel.livejournal.com]

It would seem to me that this method should be relatively congenial in terms of keeping a record of its path, and thereby possibly providing indicators as to shape of the underlying distibution of your... ow. Half my brain said "objective function" and the other said "metric of eudemony", depending on how metaphorical your usage of "happiness" is.

The one-unit/two-unit/four-unit measurements acts as a protection against local minima, yes ? But this algorithm has no inherent "memory" beyond that ?

[purpletigron.livejournal.com]

I used this for my PhD.

[cartesiandaemon.livejournal.com]

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

But the amoeba is merely a more subtle expression of your will... Would you say the Wright brothers were outflown by their plane? Don't answer that :)

[ipsi-digit.livejournal.com]

Are you using the Nelder-Meade amoeba huristic from Numerical Recipes?

[ipsi-digit.livejournal.com]

Oh, I saw your entry about the sparkly sparks on the 'latest posts' (http://www.livejournal.com/stats/latest.bml) link. I've been an electronics geek for 45 years and so I zero in on electrical stuff. Liked what I read and checked your other journal entries. The Simplex entry caught my attention, tickling memories.

Yikes! 250 variables is a lot for NM. I wonder if one of the other NL optimization methods would work better. There isn't that much performance difference between the conjugate gradient methods. They can be used even on non-differentiable functions if finite differences are used. Each iteration takes longer but far, far fewer iterations are needed to converge, overall.

I've been watching the folding@home news. Seems they are starting to use the super number crunching power of the best video cards to accelerate their research. I can remember 25 years ago when Texas Instruments came out with a graphics card using their DSP chips to speed up graphics. The card had many times the power of the PC's CPU. Seems they were way ahead of their time.

Thanks about the graphics. I just use this account for posting some of the doodles I make in my retirement.