DEPARTMENT OF MECHANICS AND APPLIED MATHEMATICS

STOCHASTIC PROGRAMMING

HEAD OF THE PROJECT Riho LEPP, Ph.D.

DESCRIPTION

Two types of stochastic programming (SP) models are widely known: two-stage SP-s (or stochastic programs with recourse) and chance-constrained (or probabilistic) SP-s. Last ones include the probability function v (x, ) of the form

v (x, ) = P { f (x, ) < } (1)

where is a random parameter and x is the control parameter. The problem is to maximize v (x, ) over x for a fixed level .

The inverse to the problem (1), the quantile minimization problem is defined in such a way that the probability level , 0 < < 1, is fixed earlier, and the purpose now is to minimize the quantile :

w(x) = min { v (x, ) } ,(2)

and then to minimize w(x) over x.

Both problems (1), (2) are mathematically quite uncomfortable to handle: v (x, ) and w(x) are never convex, only under very hard restrictions to distribution of and to function f (x,) they are differentiable etc. At the same time functions v (x, ) and w(x) are very important in applications. Consider as an example the problem of the correction of a satellite orbit.

The mathematical model of the correction is given by the following recursion relation: d (x,) = ₀ + x (1 + ₁) where d is the drift speed after the correction, ₀ is the current drift speed at the apogee, x is the drift speed impulse and ₁ is the random coefficient characterizing the error of the correction impulse implementation. The variable ₀ is the rest of the drift speed after the correction process at the previous stage. It is assumed that ₀ and ₁ are independent Gaussian random variables. The quantile function w(x) is now defined as follows:

w(x) = min { : P ( | | d (x,) | }(3)

and the quantile minimization problem is for this model the following: minimize over certain class of strategies x = x() the quantile function w(x) where is near to 1, e.g. = 0,9999.

In general, there are two ways to find an optimal strategy: mean square and minimax ones. If the fixed probability level is around 0,9 then differences between the two strategies are quite small, but in the case of 0,999 the situation changes drastically, and we must use the more complicated, minimax strategy in order to find optimal quantile for the correction of the satellite orbit, see and of mean square and minimax straregies in the figure for correction of the satellite orbit (3), respectively.

10/04/1998 webmaster