Stochastic optimization

Last updated

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 involves random objective functions or random constraints. 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.

Contents

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:

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:

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.

See also

Related Research Articles

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. The name comes from the Monte Carlo Casino in Monaco, where the primary developer of the method, physicist Stanislaw Ulam, was inspired by his uncle's gambling habits.

<span class="mw-page-title-main">Simulated annealing</span> Probabilistic optimization technique and metaheuristic

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. For large numbers of local optima, SA can find the global optima. It is often used when the search space is discrete. For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent or branch and bound.

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

<span class="mw-page-title-main">Hill climbing</span> Optimization algorithm

In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.

Tabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989.

Multi-disciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. It is also known as multidisciplinary system design optimization (MSDO), and multidisciplinary design analysis and optimization (MDAO).

Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function is equivalent to the minimization of the function .

In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems.

Stochastic gradient descent is an iterative method for optimizing an objective function with suitable smoothness properties. It can be regarded as a stochastic approximation of gradient descent optimization, since it replaces the actual gradient by an estimate thereof. Especially in high-dimensional optimization problems this reduces the very high computational burden, achieving faster iterations in exchange for a lower convergence rate.

The greedy randomized adaptive search procedure is a metaheuristic algorithm commonly applied to combinatorial optimization problems. GRASP typically consists of iterations made up from successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search. The greedy randomized solutions are generated by adding elements to the problem's solution set from a list of elements ranked by a greedy function according to the quality of the solution they will achieve. To obtain variability in the candidate set of greedy solutions, well-ranked candidate elements are often placed in a restricted candidate list (RCL), and chosen at random when building up the solution. This kind of greedy randomized construction method is also known as a semi-greedy heuristic, first described in Hart and Shogan (1987).

The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective.

In fluid dynamics, pipe network analysis is the analysis of the fluid flow through a hydraulics network, containing several or many interconnected branches. The aim is to determine the flow rates and pressure drops in the individual sections of the network. This is a common problem in hydraulic design.

Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive update rules of stochastic approximation methods can be used, among other things, for solving linear systems when the collected data is corrupted by noise, or for approximating extreme values of functions which cannot be computed directly, but only estimated via noisy observations.

Simultaneous perturbation stochastic approximation (SPSA) 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, simulation optimization, and atmospheric modeling. Many examples are presented at the SPSA website http://www.jhuapl.edu/SPSA. A comprehensive book on the subject is Bhatnagar et al. (2013). An early paper on the subject is Spall (1987) and the foundational paper providing the key theory and justification is Spall (1992).

<span class="mw-page-title-main">Roberto Battiti</span>

Roberto Battiti is an Italian computer scientist, Professor of computer science at the University of Trento, director of the LIONlab, and deputy director of the DISI Department and delegate for technology transfer.

<span class="mw-page-title-main">Iterated local search</span>

Iterated Local Search (ILS) is a term in applied mathematics and computer science defining a modification of local search or hill climbing methods for solving discrete optimization problems.

LIONsolver is an integrated software for data mining, business intelligence, analytics, and modeling and reactive business intelligence approach. A non-profit version is also available as LIONoso.

Derivative-free optimization is a discipline in mathematical optimization that does not use derivative information in the classical sense to find optimal solutions: Sometimes information about the derivative of the objective function f is unavailable, unreliable or impractical to obtain. For example, f might be non-smooth, or time-consuming to evaluate, or in some way noisy, so that methods that rely on derivatives or approximate them via finite differences are of little use. The problem to find optimal points in such situations is referred to as derivative-free optimization, algorithms that do not use derivatives or finite differences are called derivative-free algorithms.

References

  1. ↑ Spall, J. C. (2003). Introduction to Stochastic Search and Optimization. Wiley. ISBN   978-0-471-33052-3.
  2. ↑ 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.
  3. ↑ M.C. Campi and S. Garatti. The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs. SIAM J. on Optimization, 19, no.3: 1211–1230, 2008.
  4. ↑ Robbins, H.; Monro, S. (1951). "A Stochastic Approximation Method". Annals of Mathematical Statistics. 22 (3): 400–407. doi: 10.1214/aoms/1177729586 .
  5. ↑ 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 .
  6. ↑ Spall, J. C. (1992). "Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation". IEEE Transactions on Automatic Control. 37 (3): 332–341. CiteSeerX   10.1.1.19.4562 . doi:10.1109/9.119632.
  7. ↑ Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications , Morgan Kaufmann / Elsevier, 2004.
  8. ↑ M. de Carvalho (2011). "Confidence intervals for the minimum of a function using extreme value statistics" (PDF). International Journal of Mathematical Modelling and Numerical Optimisation. 2 (3): 288–296. doi:10.1504/IJMMNO.2011.040793.
  9. ↑ M. de Carvalho (2012). "A generalization of the Solis-Wets method" (PDF). Journal of Statistical Planning and Inference. 142 (3): 633‒644. doi:10.1016/j.jspi.2011.08.016.
  10. ↑ S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680. Bibcode:1983Sci...220..671K. CiteSeerX   10.1.1.123.7607 . doi:10.1126/science.220.4598.671. PMID   17813860. S2CID   205939.
  11. ↑ D.H. Wolpert; S.R. Bieniawski; D.G. Rajnarayan (2011). "Probability Collectives in Optimization". Santa Fe Institute.
  12. ↑ Battiti, Roberto; Gianpietro Tecchiolli (1994). "The reactive tabu search" (PDF). ORSA Journal on Computing. 6 (2): 126–140. doi:10.1287/ijoc.6.2.126.
  13. ↑ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN   978-0-387-09623-0.
  14. ↑ Rubinstein, R. Y.; Kroese, D. P. (2004). The Cross-Entropy Method. Springer-Verlag. ISBN   978-0-387-21240-1.
  15. ↑ Zhigljavsky, A. A. (1991). Theory of Global Random Search. Kluwer Academic. ISBN   978-0-7923-1122-5.
  16. ↑ Kagan E.; Ben-Gal I. (2014). "A Group-Testing Algorithm with Online Informational Learning". IIE Transactions. 46 (2): 164–184. doi:10.1080/0740817X.2013.803639. S2CID   18588494.
  17. ↑ W. Wenzel; K. Hamacher (1999). "Stochastic tunneling approach for global optimization of complex potential energy landscapes". Phys. Rev. Lett. 82 (15): 3003. arXiv: physics/9903008 . Bibcode:1999PhRvL..82.3003W. doi:10.1103/PhysRevLett.82.3003. S2CID   5113626.
  18. ↑ E. Marinari; G. Parisi (1992). "Simulated tempering: A new monte carlo scheme". Europhys. Lett. 19 (6): 451–458. arXiv: hep-lat/9205018 . Bibcode:1992EL.....19..451M. doi:10.1209/0295-5075/19/6/002. S2CID   12321327.
  19. ↑ Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. ISBN   978-0-201-15767-3. Archived from the original on 2006-07-19.
  20. ↑ Tavridovich, S. A. (2017). "COOMA: an object-oriented stochastic optimization algorithm". International Journal of Advanced Studies. 7 (2): 26–47. doi: 10.12731/2227-930x-2017-2-26-47 .
  21. ↑ Yudkowsky, Eliezer. "Worse Than Random - LessWrong".
  22. ↑ Glover, F. (2007). "Tabu search—uncharted domains". Annals of Operations Research. 149: 89–98. CiteSeerX   10.1.1.417.8223 . doi:10.1007/s10479-006-0113-9. S2CID   6854578.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.