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

[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 ?