Stochastic programming
|
|
Stochastic programming appeared with numerical methods to simulate physical phenomena. It can be used for any describe problem posed as the minimization of an energy. Stochastic programming has two main features:
- non-intensive computing (at least, less than the full resolution); and
- it avoids becoming stuck in local minima ( an unstable state)
In fact, it's deeply linked with the computational abilities, which, up to recently, were really poor. As a consequence, one couldn't afford for a full resolution on our problem (even with a super-computer like a Cray). Imagine handling a physical system, in a initial state. The idea is to perform a random update of this state. You randomly pick up an element of your system and check towards which point it would evolve given the current state. If the system is in a lower energy state, then you perform the update, otherwise you perform the update according to an a priori given probability. And you iterate this procedure.
The classic example is the Monte Carlo algorithm used for a set of magnetic particles. The current state is the knowledge of spin up/spin down for each particle. You pick up one of them, and you check if the change of spin would decrease or increase the global energy.