.
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.[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] 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)[3]
stochastic gradient descent
finite-difference SA by Kiefer and Wolfowitz (1952)[4]
simultaneous perturbation SA by Spall (1992)[5]
Randomized search methods
See also: Metaheuristic
On the other hand, even when the data set consists of precise measurements, some methods introduce randomness into the search-process to accelerate progress[6]. 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:
simulated annealing by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi (1983)[7]
Probability Collectives by D.H. Wolpert, S.R. Bieniawski and D.G. Rajnarayan (2011)[8]
reactive search optimization (RSO) by Roberto Battiti, G. Tecchiolli (1994),[9] recently reviewed in the reference book [10]
cross-entropy method by Rubinstein and Kroese (2004)[11]
random search by Anatoly Zhigljavsky (1991)[12]
stochastic tunneling[13]
parallel tempering a.k.a. replica exchange[14]
stochastic hill climbing
swarm algorithms
evolutionary algorithms
genetic algorithms by Holland (1975)[15]
evolution strategies
See also
Global optimization
Machine learning
Gaussian process
State Space Model
Model predictive control
Nonlinear programming
References
^ Spall, J. C. (2003). Introduction to Stochastic Search and Optimization. Wiley. ISBN 0-471-33052-3.
^ Fu, M. C. (2002). "Optimization for Simulation: Theory vs. Practice". INFORMS Journal on Computing 14 (3): 192–227. doi:10.1287/ijoc.14.3.192.113.
^ Robbins, H.; Monro, S. (1951). "A Stochastic Approximation Method". Annals of Mathematical Statistics 22 (3): 400–407. doi:10.1214/aoms/1177729586.
^ J. Kiefer; J. Wolfowitz (1952). "Stochastic Estimation of the Maximum of a Regression Function". Annals of Mathematical Statistics 23 (3): 462–466. doi:10.1214/aoms/1177729392.
^ Spall, J. C. (1992). "Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation". IEEE Transactions on Automatic Control 37 (3): 332–341. doi:10.1109/9.119632.
^ Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004.
^ S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). "Optimization by Simulated Annealing". Science 220 (4598): 671–680. doi:10.1126/science.220.4598.671. PMID 17813860.
^ D.H. Wolpert; S.R. Bieniawski; D.G. Rajnarayan (2011). C.R. Rao; V. Govindaraju. ed. Probability Collectives in Optimization.
^ Battiti, Roberto; Gianpietro Tecchiolli (1994). "The reactive tabu search" (PDF). ORSA Journal on Computing 6 (2): 126–140.
^ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0.
^ Rubinstein, R. Y.; Kroese, D. P. (2004). The Cross-Entropy Method. Springer-Verlag. ISBN 978-0-387-21240-1.
^ Zhigljavsky, A. A. (1991). Theory of Global Random Search. Kluwer Academic. ISBN 0-7923-1122-1.
^ W. Wenzel; K. Hamacher (1999). "Stochastic tunneling approach for global optimization of complex potential energy landscapes". Phys. Rev. Lett. 82 (15): 3003. Bibcode 1999PhRvL..82.3003W. doi:10.1103/PhysRevLett.82.3003.
^ E. Marinari; G. Parisi (1992). "Simulated tempering: A new monte carlo scheme". Europhys. Lett. 19 (6): 451. doi:10.1209/0295-5075/19/6/002.
^ Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. ISBN 0-201-15767-5.
Michalewicz, Z. and Fogel, D. B. (2000), How to Solve It: Modern Heuristics, Springer-Verlag, New York.
External links
Software
AIMMS (AIMMS)
FortSP solver (FortSP)
SPInE
XPRESS-SP
When k = n or n−1 we saw in the previous section that Vk(Fn) is a principal homogeneous space, and therefore diffeomorphic to the corresponding classical group. These are listed in the table at the right.
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
