Stochastic optimization

Stochastic optimization (SO) methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involve random objective functions or random constraints, for example. Stochastic optimization methods also include methods with random iterates. Some stochastic optimization methods use random iterates to solve stochastic problems, combining both meanings of stochastic optimization. Stochastic optimization methods generalize deterministic methods for deterministic problems.

Common methods

The common methods for stochastic functions are:

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

The common randomized search methods are:

• simulated annealing by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi (1983)
• quantum annealing
• Probability Collectives by D.H. Wolpert, S.R. Bieniawski and D.G. Rajnarayan (2011)
• reactive search optimization (RSO) by Roberto Battiti, G. Tecchiolli (1994), recently reviewed in the reference book
• cross-entropy method by Rubinstein and Kroese (2004)
• random search by Anatoly Zhigljavsky (1991)
• Informational search
• stochastic tunneling
• parallel tempering a.k.a. replica exchange
• stochastic hill climbing
• swarm algorithms
• evolutionary algorithms

See also

Mathematical Optimization

Papers

• Neely, Michael J. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks 3.1 (2010): 1-211.
• Kingma, Diederik, and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).

Books

• Schneider, Johannes J.; Kirkpatrick, Scott (2006). Stochastic Optimization. Springer
• Marti, Kurt (2010). Stochastic Optimization Methods. Springer
• Heyman, Daniel P.; Sobel, Matthew J. (2003). Stochastic Models in Operations Research, Vol. I: Stochastic Processes and Operating Characteristics. Courier Corporation.
• Heyman, Daniel P.; Sobel, Matthew J. (2003). Stochastic Models in Operations Research, Vol. II: Stochastic Optimization. Courier Corporation.