Stochastic programming

The branch of mathematical programming in which one studies the theory and methods for the solution of conditional extremal problems, given incomplete information on the aims and restrictions of the problem. Stochastic programming includes many particular problems of control, planning and design. Stochastic programming methods can also be used to adapt systems and algorithms to random changes in the state of the medium in which they operate. Stochastic optimization models are usually more suitable in real conditions for the choice of solutions than deterministic formulations of extremal problems.

In order to construct realistic stochastic models of control processes, it is necessary to have at one's disposal not only the statistical characteristics of the random parameters of the conditions, but also data on the order in which information enters, is stored and is used, admissible scheduling of solutions, and quality requirements for the solutions. Stochastic problems are divided into single-stage, two-stage and multi-stage problems.

In single-stage problems of stochastic programming, the dynamics of entering the initial information does not play a role, and the solution is accepted once and is not corrected. Single-stage problems are classified according to the type of the objective functional, the character of the restrictions and the form of the solution. The most commonly used objective functionals are the probability of hitting a certain, generally random, domain (the $P$-model) and the mathematical expectation or variance of a certain function of the solution (the $M$-model and the $V$-model, respectively). The domain of feasible solutions of a single-stage problem is defined by rigid, probabilistic or statistical restrictions. Restrictions that must be fulfilled for all (or nearly all) realizations are called rigid. Restrictions are called probabilistic if discrepancies are admissible in the conditions of the problem with a probability not higher than a given value. Restrictions are called statistical if there are good grounds for requiring only that they be satisfied on the average.

Single-stage problems are also distinguished according to whether the solution is accepted before or after the observation of realizations of the initial data. In the first case, the solution is defined in the form of a deterministic vector, in the second, in the form of a "decision principle" — a function in the random parameters of the conditions of the problem.

Research into the solution methods for single-stage problems of stochastic programming is divided into direct and indirect methods. Direct methods are iterative processes that permit one to approximate the solution of the problem by observing successive realizations of the conditions. Direct methods are interpreted as adaptation methods. These methods are a generalization of the so-called schemes of stochastic approximation. Indirect methods reduce to the construction of deterministic equivalents of stochastic problems, and to the use of known methods of deterministic mathematical programming. Both direct and indirect methods are effective in cases where the deterministic equivalent is a problem of convex programming.

Two-stage problems of stochastic programming are the most widespread models of control processes under conditions of incomplete information. Two-stage models are generalized to include stochastic problems of a different information structure that reflects possible aspects of the dynamics of accumulating information and choosing and correcting solutions. The theory of multi-stage stochastic models is included in Markov programming (see, for example, [6]) and in stochastic discrete optimal control.

The theory and methods of stochastic programming have been generalized to include a number of classes of stochastic optimal control (see [5]).

References

[1]	D.B. Yudin, "Mathematical methods of control in conditions of incomplete information" , Moscow (1974) (In Russian)
[2]	E.B. Dynkin, A.A. Yushkevich, "Controlled Markov processes" , Springer (1979)
[3]	Yu.M. Ermol'ev, "Methods of stochastic programming" , Moscow (1976) (In Russian)
[4]	V.I. Arkin, I.V. Evstigneev, "Stochastic models of control and economic dynamics" , Acad. Press (1987) (Translated from Russian)
[5]	D.B. Yudin, "Problems and methods of stochastic programming" , Moscow (1979) (In Russian)
[6]	D.B. Yudin, A.D. Yudin, "Extremal models in economics" , Moscow (1979) (In Russian)

References

[a1]	R.J.-B. Wets, "Stochastic programming: solution techniques and approximation schemes" A. Bachem (ed.) B. Korte (ed.) , Mathematical Programming - The State of the Art , Springer (1983) pp. 566–603
[a2]	S. Vajda, "Probabilistic programming" , Acad. Press (1972)