![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
I love the simplex method
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.
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.
The simplex method as interpretive dance
B: Yes. So, by up, you mean...?
A: Uh... the line greatest dgoodness/dvariable?
A: *shades eyes in looking getsure, turns around examining ground, chooses a direction and marches confidently on the spot*
B: Right. Is it this way? *holds arm out straight* Or this way? *Holds arm out at right angles* Or this way? *holds first arm straight up* Or this? Or this? Or this? *points arms in all directions, simulating n-space*
A: Uh...
B: You are in n dimensions. You have n *basis* directions.
A: Ooh! Pick one of *them*! Pick one of them!
B: OK, right. Which?
A: The best one?
B: By which you mean?
A: Uhhh... the worst one?
B: What?
A: Uhhhh *makes a seesaw motion* the direction with greatest positive gradient, but assume d2 is approx constant over small distances, so equally well the opposite of the one with the greatest negative.
B: Good! So you're going to compare all these...
A: Wait.
B: Ooh, what have you spotted.
A: I don't want to test *all* of them.
B: Correct! If you change one at a time, you can work out the new ones from the old ones.
A: Cool. *bounces*
B: You've invented the simplex method *hyperpyramid gesture*
Apologies -- I'm rather tired and have mangled the method beyond all recognition. But I think that's the point, kinda...
At work we have verilog compiler/optimisers that work iteritively. You'd think they'd never make things *worse*, wouldn't you.