
The latest issue of New Scientist:
New Scientist: The Algorithm That Runs The World
[WARNING: for 'geeks' only]
I found this of interest since I’ve used the ‘simplex’ method to optimise for several variables when I was evaluating modem chips at Intel back in my murky past. While very useful, I ran into a couple of problems with the algorithm. (1) It is pretty slow. Of course, computers are much faster than the were during my Intel days when Mammoths still munched on the weeds out back… and (2) It can sometimes ‘fixate’ on ‘local minima’… while failing to find the global minimum. This is no problem in a smooth ‘simple’ topology (image above), but in ‘bumpy’ or ‘dimpled’ multivariate functions it can be a serious complication. That is my experience. Still, it is a valuable tool for optimisation over several variables.
My solution to problem (2, above) was to ‘pre-wash’ the problem with a ‘simulated annealing’ algorithm, which is also slow, but if used properly, WILL find the the global minimum. Simulated Annealing, as the name implies, simulates a blacksmith heating and then cooling metal to strengthen it by ‘jiggling’ the molecules to find lower energy levels… thus ‘optimising’ the metal’s molecular structure. Mathematical ‘annealing’ involves randomising the results by a fixed percentage at each iteration. The randomisation amount is slowly reduced, simulating a lowering of temperature over time, thus ‘annealing’. Then, by knowing ‘where’ the global minimum is, I can apply the simplex method using ‘fixed’ initial conditions to force it to ‘look’ in the right place.
A pain in the ass and very slow to be sure, but with near guaranteed accuracy.
The NS cover article focuses on the algorithm’s speed (or lack thereof). For real-time applications, even with super-fast computers, it can be problematic, especially with more than a very few variables.
MathWorld: the Simplex Method
Surprisingly perhaps, Wikipedia offers a fair to good description of the Simplex method:
Wikipedia: Simplex Algorithm
And more on simulated annealing:
MathWorld: Simulated Annealing
It should come as no surprise that these same algorithms are routinely used to ‘optimise’ economics problems and help predict stock share prices. Sometimes they even work. Sometimes they DON’T.
* Not ‘herpes simplex’!