Stochastic programming

Stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within certain bounds, one approach to tackling such problems is called robust optimization. Here the goal is to find a solution which is feasible for all such data and optimal in some sense. Stochastic programming models are similar in style but take advantage of the fact that probability distributions governing the data are known or can be estimated. The goal here is to find some policy that is feasible for all (or almost all) the possible data instances and maximizes the expectation of some function of the decisions and the random variables. More generally, such models are formulated, solved analytically or numerically, and analyzed in order to provide useful information to a decision-maker.

The most widely applied and studied stochastic programming models are two-stage linear programs. Here the decision maker takes some action in the first stage, after which a random event occurs affecting the outcome of the first-stage decision. A recourse decision can then be made in the second stage that compensates for any bad effects that might have been experienced as a result of the first-stage decision. The optimal policy from such a model is a single first-stage policy and a collection of recourse decisions (a decision rule) defining which second-stage action should be taken in response to each random outcome.

Biological Applications

Stochastic dynamic programming is frequently used to model animal behaviour in such fields as behavioural ecology [Mangel, M. & Clark, C. W. 1988. "Dynamic modeling in behavioral ecology." Princeton University Press ISBN 0-691-08506-4] [Houston, A. I & McNamara, J. M. 1999. "Models of adaptive behaviour: an approach based on state". Cambridge University Press ISBN 0-521-65539-0] . Empirical tests of models of optimal foraging, life-history transitions such as fledging in birds and egg laying in parasitoid wasps have shown the value of this modelling technique in explaining the evolution of behavioural decision making. These models are typically many staged, rather than two-staged.

Economic Applications

Stochastic dynamic programming is a useful tool in understanding decision making under uncertainty. The accumulation of capital stock under uncertainty is one example, often it is used by resource economists to analyze bioeconomic problems [ Howitt, R., Msangi, S., Reynaud, A and K. Knapp. 2002. "Using Polynomial Approximations to Solve Stochastic Dynamic Programming Problems: or A "Betty Crocker " Approach to SDP." University of California, Davis, Department of Agricultural and Resource Economics Working Paper. http://www.agecon.ucdavis.edu/aredepart/facultydocs/Howitt/Polyapprox3a.pdf ] where the uncertainty enters in such as weather, etc.

References

External links

* [http://stoprog.org Stochastic Programming Community Home Page] .
* [http://www.unizh.ch/ior/Pages/Deutsch/Mitglieder/Kall/bib/ka-wal-94.pdf A free Book on Stochastic Programming]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • stochastic programming — tikimybinis programavimas statusas T sritis automatika atitikmenys: angl. stochastic programming vok. stochastische Programmierung, f rus. стохастическое программирование, n pranc. programmation stochastique, f ryšiai: sinonimas – stochastinis… …   Automatikos terminų žodynas

  • Stochastic optimization — (SO) methods are optimization algorithms which incorporate probabilistic (random) elements, either in the problem data (the objective function, the constraints, etc.), or in the algorithm itself (through random parameter values, random choices,… …   Wikipedia

  • Stochastic calculator — The concept of calculator stochastic is already old (for the young history of data processing) and contemporary of research and applications developed at the any end of the decade 1950 and until the middle of the decade 1970.Their definition in… …   Wikipedia

  • Stochastic context-free grammar — A stochastic context free grammar (SCFG; also probabilistic context free grammar, PCFG) is a context free grammar in which each production is augmented with a probability. The probability of a derivation (parse) is then the product of the… …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

  • Second-order cone programming — A second order cone program (SOCP) is a convex optimization problem of the form:minimize f^T x subject to:lVert A i x + b i Vert 2 leq c i^T x + d i,quad i = 1,dots,m:Fx = g where the problem parameters are f in mathbb{R}^n, A i in mathbb{R}^n i} …   Wikipedia

  • Mathematical Programming Society — Known as the Mathematical Programming Society until 2010,[1] the Mathematical Optimization Society (MOS) is an international association of researchers active in optimization. The MOS encourages the research, development, and use of optimization… …   Wikipedia

  • Mathematical Programming —   Former name(s) Mathematical Programming Studies …   Wikipedia

  • Mathematical Programming Society — Logo der Mathematical Programming Society Die Mathematical Programming Society (MPS) ist eine internationale Organisation im Bereich der mathematischen Optimierung. Ihr Ziel ist die Förderung der Optimierung in Theorie und Praxis. Die MPS… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.