Performance continuity and differentiability in Monte Carlo optimization

ABSTRACT

This paper describes a class of Monte Carlo optimization problems for which unbiased derivative estimators of the infinitesimal perturbation analysis (IPA) type can be derived; and also a simple framework within which to establish unbiasedness. Of central importance are systems with continuous, piecewise differentiable sample performance functions. Experience suggests that continuity is, in practice, almost necessary for IPA to work. “Piecewise” differentiable is a concession to the discrete nature of many applied probability models. We discuss a variety of examples, including both static and dynamic systems.

REFERENCES

• 1: C~, X.R., 'Convergence of parameter sensitivity estimate.,~ in a stochastic experiment,' IEEE Transactions on Autoraatic Control, AC-30, pp.845-853, 1985.
• 2: Dieudonne, J.A.. Foundations of Modern Analysis, Academic Press, New York, 1960.
• 3: Glasserman, P., 'Infinitesimal perturbation analysis of a birth and death process,' Operations Research Letters, 7, no.l, 1988.
• 4: Glasserman, P., "Equivalence methods in the perturbation analysis of queueing networks', Ph.D. Thesis, Harvard University, 1988.
• 5: Glynn, P.W., 'Process-differentiable representations of parametric families of random variables', Technical Report, Department of Industrial Engineering, University of Wisconsin - Madison, 1987.
• 6: Gong, W.B. and Ho, Y.C., 'Smoothed perturbation analysis of discrete-event dynamic system,~', IEEE Transactions on Automatic Control, AC-32, pp.858-867, 1987.
• 7: Li, S. and Ho, Y.C., 'Sample path and performance homogeneity of discrete event dynamic systems', Manuscript, Systems and Industrial Engineering, University of Arizona, 1988.
• 8: David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, Inc., New York, NY, 1997
• 9: Marc S. Meketon, Optimization in simulation: a survey of recent results, Proceedings of the 19th conference on Winter simulation, p.58-67, December 14-16, 1987, Atlanta, Georgia, United States [doi>10.1145/318371.318384]
• 10: R Y Rubinstein, The score function approach for sensitivity analysis of computer simulation models, Mathematics and Computers in Simulation, v.28 n.5, p.351-379, Oct. 1986 [doi>10.1016/0378-4754(86)90072-8]
• 11: Rajan Suri, Infinitesimal perturbation analysis for general discrete event systems, Journal of the ACM (JACM), v.34 n.3, p.686-717, July 1987 [doi>10.1145/28869.28879]
• 12: Rajan Suri , Michael A. Zazanis, Perturbation analysis gives strongly consistent sensitivity estimates for the M/G/1 queue, Management Science, v.34 n.1, p.39-64, Jan. 1988 [doi>10.1287/mnsc.34.1.39]
• 13: Whitt, W., 'Continuity of generalized semi-Markov processes', Mathematics of Operations Research, 5, pp.494-501, 2980.
• 14: Zazanis, M. 'Weak convergence of sample path derivatives for the waiting time in a single server queue', Proceedings of the ~!5th A;lerton Conference on Commun'ication, Control and Comp~ting, 1987.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Monte Carlo

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Performance, Theory, Verification