Stochastic optimization

Stochastic optimization (SO) are optimization methods that generate and use random variables. For stochastic optimization problems, the objective functions or constraints are random. Stochastic optimization also include methods with random iterates. Some hybrid methods use random iterates to solve stochastic problems, combining both meanings of stochastic optimization.^[1] Stochastic optimization methods generalize deterministic methods for deterministic problems.

Methods for stochastic functions

Partly random input data arise in such areas as real-time estimation and control, simulation-based optimization where Monte Carlo simulations are run as estimates of an actual system,^[2]^[3] and problems where there is experimental (random) error in the measurements of the criterion. In such cases, knowledge that the function values are contaminated by random "noise" leads naturally to algorithms that use statistical inference tools to estimate the "true" values of the function and/or make statistically optimal decisions about the next steps. Methods of this class include:

stochastic approximation (SA), by Robbins and Monro (1951)^[4]
stochastic gradient descent
finite-difference SA by Kiefer and Wolfowitz (1952)^[5]
simultaneous perturbation SA by Spall (1992)^[6]
scenario optimization

Randomized search methods

On the other hand, even when the data set consists of precise measurements, some methods introduce randomness into the search-process to accelerate progress.^[7] Such randomness can also make the method less sensitive to modeling errors. Another advantage is that randomness into the search-process can be used for obtaining interval estimates of the minimum of a function via extreme value statistics.^[8]^[9] Further, the injected randomness may enable the method to escape a local optimum and eventually to approach a global optimum. Indeed, this randomization principle is known to be a simple and effective way to obtain algorithms with almost certain good performance uniformly across many data sets, for many sorts of problems. Stochastic optimization methods of this kind include:

simulated annealing by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi (1983)^[10]
quantum annealing
Probability Collectives by D.H. Wolpert, S.R. Bieniawski and D.G. Rajnarayan (2011)^[11]
reactive search optimization (RSO) by Roberto Battiti, G. Tecchiolli (1994),^[12] recently reviewed in the reference book ^[13]
cross-entropy method by Rubinstein and Kroese (2004)^[14]
random search by Anatoly Zhigljavsky (1991)^[15]
Informational search ^[16]
stochastic tunneling^[17]
parallel tempering a.k.a. replica exchange^[18]
stochastic hill climbing
swarm algorithms
evolutionary algorithms
- genetic algorithms by Holland (1975)^[19]
- evolution strategies
cascade object optimization & modification algorithm (2016)^[20]

In contrast, some authors have argued that randomization can only improve a deterministic algorithm if the deterministic algorithm was poorly designed in the first place.^[21] Fred W. Glover^[22] argues that reliance on random elements may prevent the development of more intelligent and better deterministic components. The way in which results of stochastic optimization algorithms are usually presented (e.g., presenting only the average, or even the best, out of N runs without any mention of the spread), may also result in a positive bias towards randomness.