Using perturbation analysis for gradient estimation, averaging and updating in a stochastic approximation algorithm

ABSTRACT

We propose a gradient updating procedure for using both “present” and “past” data to improve the convergence properties of a stochastic approximation algorithm. This procedure utilizes second derivatives estimated by perturbation analysis techniques. Experimental evidence provided by simulation runs appear to confirm the improvement in convergence rate gained by this modified algorithm.

REFERENCES

• 1: Cao, X. R. (1985), "Convergence of Parameter Sensitivity Estimates in a Stochastic Experiment," IEEE Trans. Automatic Control, Vol. AC-30, pp. 845-853.
• 2: Xi-Ren Cao, A sample performance function of closed Jackson queueing networks, Operations Research, v.36 n.1, p.128-136, January-February 1988 [doi>10.1287/opre.36.1.128]
• 3: Fogel, E. (I981), "A Fundamental Approach to the Convergence Analysis of Least Squares Algorithms," IEEE Trans. Automatic Control, Vol. AC-26, pp. 646-655.
• 4: Peter W. Glynn, Optimization of stochastic systems, Proceedings of the 18th conference on Winter simulation, p.52-59, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318260]
• 5: Gong, W. B. and Ho, Y. C. (1987), "Smoothed Perturbation Analysis of Discrete Event Dynamic Systems,'TEEE Trans. Automatic Control, Vol. AC-32, pp. 858-866.
• 6: Ho, Y. C. (1979), "Parameter Sensitivity of a Statistical Experiment, IEEE Trans. Automatic Control Vol. AC-24, pp. 982-983.
• 7: Ho, Y. C. (1987), "Performance Evaluation and Perturbation Analysis of Discrete Systems: Perspective and Open Problems," IEEE Trans. Automatic Control, Vol. AC-32, pp. 563-572.
• 8: Ho, Y. C. and Cao, X. R. (1983), "Perturbation Analysts and Optimization of Queueing Networks," J. Optim. Theory Applic., Vol. 40, No. 4, pp. 559-582.
• 9: Ho, Y. C. and Li, S. (1988), "Extensions of Infinitesimal Perturbation Analysis,"IEEE Trans. Automatic Control, Voi. AC-33, pp. 427-438.
• 10: Kesten, H. (1958), "Accelerated Stochastic Approximation," Ann. Math. Star., Vol. 29, pp. 41-59.
• 11: Kiefer, J. and Wolfowitz, J. (1952), "Stochastic Estimation of the Maximum of a Regression Function," Ann. Math. Stat., Vot. 23, pp. 462-466.
• 12: Kteinrock, L. (1975), Queueing Systems, John Wiley and Sons.
• 13: Kushner, H. J. and Clark, D. C. (1978), Stochastic Approximation Methods for Constrained and Unconstrained Systems, Springer-Verlag, New York.
• 14: 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]
• 15: Nevelson, M. B. and Zalmar~ovich, R. (I 976), Stochastic Approximation and Recursive Estimation.
• 16: Robbins, H. and Monro, S. (1951), "A Stochastic Approximation Method," Ann. Math. Star., Vol: 22, pp. 400-407.
• 17: Ruszczynski, A. and Syski, W. (1983), "Stochastic Approximation Method with Gradient Averaging for Unconstrained Problems," 1EEE Trans. Automatic Control, Vol. AC-28, pp. 1097-1105.
• 18: Sacks, J. (1958), "Asymptotic Distribution of Stochastic Approximation Procedures," Ann. Math. Stat., Vol. 29, pp. 373-405.
• 19: 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]
• 20: Suri, R. and Leung, Y. T. (1988), "Single Run Optimization of Discrete Event Simulations - An Empirical Study Using the M/M/1 Queue," to appear in HE Transactions.
• 21: 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]
• 22: Zazanis, M. A. (1986b), Statistical Properties of Perturbation Analysis Estimates for Discrete Event Systems, Ph.D. thesis, Harvard University.
• 23: Zazanis, M. A. and Suri, R. (1984), "Comparison of Perturbation Analysis with Conventional Sensitivity Estimates for Stochastic Systems, submitted to Operations Research.
• 24: Zazanis, M. A. and Suri, R. (1985), "Estimating First and Second Derivatives of Response Time for G/G/1 Queues From a Single Sample Path," submitted to Queueing Systems.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Algorithms, Design, Measurement, Performance, Theory