How can you find the top of a mountain in a thick fog? One way is to walk upwards and stop when you get to a point where it's downhill in every direction you turn. That might work — but most of the time, when the fog lifts you find yourself on a secondary peak, a bump on the side of the real mountain. The same problem arises constantly in computation, when some quantity — profit, efficiency, safety, whatever — needs to be maximized. The computer is like a climber in the fog; it has no global "vision" of the topography, and must rely on local measurements.
To do better than simple hill-climbing takes a willingness to go down once in a while, that is, to give up immediate gain for long-range profit. One approach that works is to sample the terrain on a grid, say every 1000 meters in a north-south and east-west direction. The altitude data from those samples can then be used to model the entire mountain, assuming that the surface is reasonably smooth. (There's no guarantee that it is, but one can hope ... and measurements give evidence for or against the smoothness of the land.) A model that fits the samples then can guide an explorer to home in on the likeliest zones, where more readings taken on a finer grid, perhaps every 100 meters, may lead to the true peak.
Another way to seek the mountaintop comes from the physics of solids; it's called "simulated annealing". When crystals grow quickly, layers of atoms are laid down with lots of defects. To get rid of those faults, a blacksmith heats an ingot and then gradually cools it. The heat lets atoms bounce around and get into their proper places, and then the cooling locks them in where they belong. In the same way, a simulated hill-climber is started at a high "temperature", racing off in a random direction with only a slight bias toward going up. The ersatz climber's temperature is then lowered slowly, increasing the tendency to climb and making it less likely (but not impossible) to go down. This method keeps the climber from always getting trapped on a local maximum, and when done many times can lead to a good (though maybe not the best) solution.
The real challenge comes when trying to optimize not over two quantities, but over hundreds or more. Imagine the trek up a thousand-dimensional mountain! At each point along the trail there are so many directions to turn that one is almost certain to waste time heading the wrong way. But such high dimensionality problems are precisely what must be solved when dealing with complex real-world situations — scheduling an airline's flights, running a factory, or tweaking a telecommunications network. Tough or impossible to do perfectly, especially under time constraints, but with mathematical help feasible to do "good enough".
Monday, December 13, 1999 at 22:21:13 (EST) = 1999-12-13
(correlates: GorillaPhilosopher, Comments on Steely Eyed Missile Man, HerodotusOnFreedom, ...)