Optimization of stochastic systems via simulation

ABSTRACT

In this paper, we discuss some research issues related to the general topic of optimizing a stochastic system via simulation. In particular, we devote extensive attention to finite-difference estimators of objective function gradients and present a number of new limit theorems. We also discuss a new family of orthogonal function approximations to the global behavior of the objective function. We show that if the objective function is sufficiently smooth, the convergence rate can be made arbitrarily close to n^-1/2 in the number of observations required. The paper concludes with a brief discussion of how these ideas can be integrated into an optimization algorithm.

REFERENCES

• 1: CHUNG, K. L. (1974). A First Course in Probability Theory, Academic Press, New York.
• 2: FOX, B. L. and GLYNN, P. W. (1989). Replication schemes for limiting replications. To appear in Probability Theory of the Engineering and Informational Sciences.
• 3: FULKS, W. (1969). Advanced Calculus. John Wiley, New York.
• 4: GLASSERMAN, P. and GONG, W. (1989). Derivative estimates from discontinuous realizations: smoothing techniques. To appear in Proceedings of the 1989 Winter Simulation Conference.
• 5: GLYNN, P. W. (1987). Construction of process-differentiable representations for parametric families of distributions. Technical Report, Mathematics Research Center, University of Wisconsin, Madison.
• 6: HEIDELBERGER, P., CAO, X. R., ZAZANIS, M. A., and SURI, R. (1988). Convergence properties of infinitesimal perturbation analysis estimates. Management Science, 34, 1281--1302.
• 7: HO, Y. C. and CAO, X. R. (1983). Perturbation analysis of queueing networks. Journal of Optimization Theory and Applications 40, 559--582.
• 8: HO, Y. C. and CAO, X. R. (1985). Performance sensitivity to routing changes in queueing networks and flexible manufacturing systems using perturbation analysis. IEEE Journal of Robotics and Automation, RA-1, 615--672.
• 9: POLYAK, B. T. and TSYPKIN, Y. Z. (1980). Optimal pseudogradient adaptive algorithms. Automat. Remote Control 8, 74--84.
• 10: REIMAN, M. I. and WEISS, A. (1986). Sensitivity analysis via likelihood ratios. Proceedings of the 1986 Winter Simulation Conference, 285--289.
• 11: RUBINSTEIN, R. Y. (1986). Monte Carlo Optimization, Simulation and Sensitivity of Queueing Networks. John Wiley, New York.
• 12: RUPPERT, D. (1982). Almost sure approximations to the Robbins-Monro and Kiefer-Wolfowitz processes with dependent noise. Annals of Probability 10, 178--187.
• 13: SURI, R. Infinitesimal perturbation analysis for general discrete event systems. J. Assoc. Comput. Mach. 34, 686--717.
• 14: ZAZANIS, M. A. and SURI, R. (1986). Comparison of perturbation analysis with conventional sensitivity estimates for regenerative stochastic systems. Technical Report, Harvard University.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Elementary function approximation

General Terms:
Algorithms, Design, Performance