I love the simplex method
Oct. 19th, 2006 04:56 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
fivemackThe 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.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2006-10-28 09:12 pm (UTC)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 ...