Stochastic programming: Difference between revisions

Revision as of 10:30, 8 May 2025

Revision as of 10:35, 8 May 2025

Line 210:

is the sample variance estimate of <math>\sigma^2(x)</math>. That is, the error of estimation of <math>g(x)</math> is (stochastically) of order <math> O(\sqrt{N})</math>.

== Applications and Examplesexamples==

=== Biological applications ===

[[Stochastic dynamic programming]] is frequently used to model [[ethology|animal behaviour]] in such fields as [[behavioural ecology]].<ref>Mangel, M. & Clark, C. W. 1988. ''Dynamic modeling in behavioral ecology.'' Princeton University Press {{ISBN|0-691-08506-4}}</ref><ref>Houston, A. I & McNamara, J. M. 1999. ''Models of adaptive behaviour: an approach based on state''. Cambridge University Press {{ISBN|0-521-65539-0}}</ref> Empirical tests of models of [[Optimal foraging theory|optimal foraging]], [[Biological life cycle|life-history]] transitions such as [[Fledge|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===

Line 224:

Suppose that at time <math>t=0</math> we have initial capital <math>W_0</math> to invest in <math>n</math> assets. Suppose further that we are allowed to rebalance our portfolio at times <math>t=1,\dots,T-1</math> but without injecting additional cash into it. At each period <math>t</math> we make a decision about redistributing the current wealth <math>W_t</math> among the <math>n</math> assets. Let <math>x_0=(x_{10},\dots,x_{n0})</math> be the initial amounts invested in the n assets. We require that each <math>x_{i0}</math> is nonnegative and that the balance equation <math>\sum_{i=1}^{n}x_{i0}=W_0</math> should hold.

Consider the total returns <math>\xi_t=(\xi_{1t},\dots,\xi_{nt})</math> for each period <math>t=1,\dots,T</math>. This forms a vector-valued random process <math>\xi_1,\dots,\xi_T</math>. At time period <math>t=1</math>, we can rebalance the portfolio by specifying the amounts <math>x_1=(x_{11},\dots,x_{n1})</math> invested in the respective assets. At that time the returns in the first period have been realized so it is reasonable to use this information in the rebalancing decision. Thus, the second-stage decisions, at time <math>t=1</math>, are actually functions of realization of the random vector <math>\xi_1</math>, i.e., <math>x_1=x_1(\xi_1)</math>. Similarly, at time <math>t</math> the decision <math>x_t=(x_{1t},\dots,x_{nt})</math> is a function <math>x_t=x_t(\xi_{[t]})</math> of the available information given by <math>\xi_{[t]}=(\xi_{1},\dots,\xi_{t})</math> the history of the random process up to time <math>t</math>. A sequence of functions <math>x_t=x_t(\xi_{[t]})</math>, <math>t=0,\dots,T-1</math>, with <math>x_0</math> being constant, defines an ''implementable policy'' of the decision process. It is said that such a policy is ''feasible'' if it satisfies the model constraints with probability 1, i.e., the nonnegativity constraints <math>x_{it}(\xi_{[t]})\geq 0</math>, <math>i=1,\dots,n</math>, <math>t=0,\dots,T-1</math>, and the balance of wealth constraints,

:<math>

Line 246:

This is a multistage stochastic programming problem, where stages are numbered from <math>t=0</math> to <math>t=T-1</math>. Optimization is performed over all implementable and feasible policies. To complete the problem description one also needs to define the probability distribution of the random process <math>\xi_1,\dots,\xi_T</math>. This can be done in various ways. For example, one can construct a particular scenario tree defining time evolution of the process. If at every stage the random return of each asset is allowed to have two continuations, independent of other assets, then the total number of scenarios is <math>2^{nT}.</math>

In order to write [[dynamic programming]] equations, consider the above multistage problem backward in time. At the last stage <math>t=T-1</math>, a realization <math>\xi_{[T-1]}=(\xi_{1},\dots,\xi_{T-1})</math> of the random process is known and <math>x_{T-2}</math> has been chosen. Therefore, one needs to solve the following problem

:<math>

Line 313:

An instance of an SP problem generated by a general modelling language tends to grow quite large (linearly in the number of scenarios), and its matrix loses the structure that is intrinsic to this class of problems, which could otherwise be exploited at solution time by specific decomposition algorithms.

Extensions to modelling languages specifically designed for SP are starting to appear, see:

*[[AIMMS]] -– supports the definition of SP problems

*[[Extended Mathematical Programming (EMP)#EMP for Stochastic Programming|EMP SP]] (Extended Mathematical Programming for Stochastic Programming) -– a module of [[General Algebraic Modeling System|GAMS]] created to facilitate stochastic programming (includes keywords for parametric distributions, chance constraints and risk measures such as [[Value at risk]] and [[Expected shortfall]]).

*[[SAMPL]] -– a set of extensions to [[AMPL]] specifically designed to express stochastic programs (includes syntax for chance constraints, integrated chance constraints and [[Robustrobust optimization|Robust Optimization]] problems)

They both can generate SMPS instance level format, which conveys in a non-redundant form the structure of the problem to the solver.

Line 334:

* John R. Birge and François V. Louveaux. ''[https://books.google.com/books?id=Vp0Bp8kjPxUC&dq=%22Introduction+to+Stochastic+Programming%22&pg=PR1 Introduction to Stochastic Programming]''. Springer Verlag, New York, 1997.

* {{cite book | last1=Kall|first1=Peter |last2=Wallace|first2=Stein W.| title=Stochastic programming | series=Wiley-Interscience Series in Systems and Optimization| publisher=John Wiley & Sons, Ltd.| ___location=Chichester|year=1994|pages=xii+307|isbn=0-471-95158-7| url=http://stoprog.org/index.html?introductions.html |mr=1315300 }}

* G. Ch. Pflug: ''[https://books.google.com/books?id=XJXhBwAAQBAJ&q=%22Stochastic+programming%22&pg=PR13 Optimization of Stochastic Models. The Interface between Simulation and Optimization]''. Kluwer, Dordrecht, 1996.

* [[András Prékopa]]. Stochastic Programming. Kluwer Academic Publishers, Dordrecht, 1995.

* [[Andrzej Piotr Ruszczyński|Andrzej Ruszczynski]] and Alexander Shapiro (eds.) (2003) ''Stochastic Programming''. Handbooks in Operations Research and Management Science, Vol. 10, Elsevier.