Stochastic optimization
Encyclopedia
Stochastic optimization (SO) methods are optimization
method
s that generate and use random variable
s. 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.
are run as estimates of an actual system, 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
consists of precise measurements, some methods introduce randomness into the search-process to accelerate progress. Such randomness can also make the method less sensitive to modeling errors. Further, the injected randomness may enable the method to escape a local minimum 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:
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
method
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
s that generate and use random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s. 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
Deterministic system (mathematics)
In mathematics, a deterministic system is a system in which no randomness is involved in the development of future states of the system. A deterministic model will thus always produce the same output from a given starting condition or initial state.-Examples:...
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 simulationsMonte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
are run as estimates of an actual system, 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
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
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 approximationStochastic approximationStochastic approximation methods are a family of iterative stochastic optimization algorithms that attempt to find zeroes or extrema of functions which cannot be computed directly, but only estimated via noisy observations....
(SA), by RobbinsHerbert RobbinsHerbert Ellis Robbins was an American mathematician and statistician who did research in topology, measure theory, statistics, and a variety of other fields. He was the co-author, with Richard Courant, of What is Mathematics?, a popularization that is still in print. The Robbins lemma, used in...
and Monro (1951)- stochastic gradient descentStochastic gradient descentStochastic gradient descent is an optimization method for minimizing an objective function that is written as a sum of differentiable functions.- Background :...
- finite-difference SA by Kiefer and Wolfowitz (1952)
- simultaneous perturbation SASimultaneous perturbation stochastic approximationSimultaneous perturbation stochastic approximation is an algorithmic method for optimizing systems with multiple unknown parameters. It is a type of stochastic approximation algorithm. As an optimization method, it is appropriately suited to large-scale population models, adaptive modeling,...
by Spall (1992)
- stochastic gradient descent
Randomized search methods
On the other hand, even when the data setData set
A data set is a collection of data, usually presented in tabular form. Each column represents a particular variable. Each row corresponds to a given member of the data set in question. Its values for each of the variables, such as height and weight of an object or values of random numbers. Each...
consists of precise measurements, some methods introduce randomness into the search-process to accelerate progress. Such randomness can also make the method less sensitive to modeling errors. Further, the injected randomness may enable the method to escape a local minimum and eventually to approach a global optimum. Indeed, this randomization
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
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 annealingSimulated annealingSimulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi (1983) - reactive search optimization (RSO)Reactive search optimizationReactive search optimization defines local-search heuristics based on machine learning, a family of optimization algorithms based on the local search techniques...
by Roberto BattitiRoberto Battiti-References:...
, G. Tecchiolli (1994), recently reviewed in the reference book - cross-entropy methodCross-entropy methodThe cross-entropy method attributed to Reuven Rubinstein is a general Monte Carlo approach tocombinatorial and continuous multi-extremal optimization and importance sampling.The method originated from the field of rare event simulation, where...
by Rubinstein and Kroese (2004) - random searchRandom searchRandom search is a family of numerical optimization methods that do not require the gradient of the problem to be optimized and RS can hence be used on functions that are not continuous or differentiable...
by Anatoly ZhigljavskyAnatoly ZhigljavskyAnatoly Zhigljavsky is a professor of statistics in the school of mathematics at Cardiff University. He is the author of 8 research monographs and papers on various topics...
(1991) - stochastic tunnelingStochastic tunnelingStochastic tunneling is an approach to global optimization based on the Monte Carlo method-sampling of the function to be minimized.- Idea :...
- parallel temperingParallel temperingParallel tempering, also known as replica exchange MCMC sampling, is a simulation method aimed at improving the dynamic properties of Monte Carlo method simulations of physical systems, and of Markov chain Monte Carlo sampling methods more generally...
a.k.a. replica exchange - stochastic hill climbingStochastic hill climbingStochastic hill climbing is a variant of the basic hill climbing method. While basic hill climbing always chooses the steepest uphill move, stochastic hill climbing chooses at random from among the uphill moves. The probability of selection may vary with the steepness of the uphill move....
- swarm algorithmsSwarm intelligenceSwarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
- evolutionary algorithms
- genetic algorithms by Holland (1975)
- evolution strategies
See also
- Global optimizationGlobal optimizationGlobal optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria.- General :The most common form is the minimization of one real-valued function...
- Machine learningMachine learningMachine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
- Gaussian processGaussian processIn probability theory and statistics, a Gaussian process is a stochastic process whose realisations consist of random values associated with every point in a range of times such that each such random variable has a normal distribution...
- State Space Model
- Model predictive controlModel predictive controlModel Predictive Control, or MPC, is an advanced method of process control that has been in use in the process industries such as chemical plants and oil refineries since the 1980s...
- Nonlinear programmingNonlinear programmingIn mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
Software
- AIMMS (AIMMSAIMMSAIMMS is a software system designed for modeling and solving large-scale optimization and scheduling-type problems....
) - FortSP solver (FortSPFortSPFortSP is a software package for solving stochastic programming problems. It solves scenario-based SP problems with recourse as well as problems with chance constraints and integrated chance constraints...
) - SPInE
- XPRESS-SP