Mathematics of Operations Research August 1990 [antikvár]

MATHEMATICS OF OPERATIONS RESEARCH Vol. 15, No. August 1990 n-iiMd in U.S.A. ON-LINE OPTIMIZATION OF SIMULATED MARKOVIAN PROCESSES* G. CH. PFLUG Unirersity of Vienna Let {Z„) be a Markovian process, the transition of which depends on a control parameter X. Let fi^ be its invariant law. It is shown that the solution of the optimization problem F(x) ¦¦= fH(z,x)dti,(^z) = rnin], xsS can be found with a recursive estimation procedure of the stochastic approximation-type. The method consists in finding a stochastic quasigradient of Fix) and in adapting the parameter X in the direction of descent. An a.s. convergence is proved and a practical example is given. 1. Introduction. The basic method for studying complex stochastic systems which cannot be treated in an analytic manner is to simulate them on a digital computer. In most cases we are, however, not primarily interested in the simulation per se, but we want to evaluate the properties of several alternative systems in order to find out which one is the best. Thus an optimization problem is inherent to many simulation studies. Since the outcome of a stochastic simulation experiment is a random variable, the problem falls into the broader class of stochastic optimization problems. For the optimization of noise corrupted functions stochastic approximation type procedures are widely used. If a stochastic estimate of the gradient of the objective function is available, then the Robbins-Monro (RM) procedure is appropriate; if only the values themselves and not the gradients are observable, the Kiefer-Wolfowitz (KW) procedure must be used. It is well known that the speed of the RM-procedure is much higher than that of the KW-procedure (typically for RM and ©(rt"'/") for KW; see Wasan [19, pp. 34, 43]). The purpose of this paper is to show how a RM-type procedure can be defined for the optimization of simulated Markovian processes. The most frequently used techniques reported in the simulation literature are not based on gradients: (i) The response surface technique. A grid is defined in the feasible set. For each point jCj in the grid, a simulation experiment is conducted to get an estimate F{x!) of F(x). A curve is fitted using these estimates and finally the optimal point of this curve is taken as a solution of the problem. (ii) The experimental design technique. This method is borrowed from the design of statistical experiments. First, simulation experiments are conducted at few points forming some geometric pattern. Based on the results, new points are adaptively added in a regular manner. The geometric pattern of the design points may be cubic, hexagonal, etc. For a description see e.g. Kleijnen [8] or Mihram [12]. If the points are •Received January 30, 1988. AMS !980 subject classification. Primary: 90C15, 62L20. lAOR 1973 subject classification. Main: Programming, probabilistic, Cross references; Gradient methods. OR /MS Index 1978 subject classification. Primary: 663 Programming/Stochastic. Key words. Stochastic optimization, stochastic quasigradient method, stochastic approximation. 381