Optimization in simulation: a survey of recent results

ABSTRACT

This paper surveys existing methods, and presents several new ideas, for optimizing performance measures with respect to input parameters for simulation. The usual methods fall into three categories. First, there is the application of traditional non-linear programming techniques, regardless of the stochastic properties of most discrete event simulations. Second, is the application of response surface methodologies. Third, are stochastic approximation techniques, a well known but little used optimization technique. The last two categories account for the stochastic behavior of simulations. This paper also discusses several developments within the past seven years that promise greater efficiency in optimizing simulations. These developments include: Karmarkar's algorithm, infinitesimal perturbation analysis and likelihood ratios to estimate derivatives of performance measures with respect to parameters, adaptive control and hybrid models.

REFERENCES

• 1: Abdelhamid, S. N. (1973). Transformations of Observations in Stochastic Approximation. The Annals of Statistics 1, 1158- 1174.
• 2: Anbar, D. (1973). On Optimal Estimation Methods using Stochastic Approximation Procedures. The Annals of Statistics 1, 1175-1184.
• 3: Avriel, M. (1975). Non-Linear Programming: Analysis and Methods, Prentice-Hall, Englewood Cliffs, New Jersey.
• 4: Azadivar, F. and Talavage, J. (1980). Optimization of Stochastic Simulation Models, Mathematics and Computation in Simulation XXII, 231-241.
• 5: Barton, R. R. (1984). Minimization Algorithms for Functions with Random Noise. American Journal of Mathematical and Management Sciences 4, 109-138.
• 6: Becker, A., Kumar, F'. R., and Wei, C. E. (1983). Adaptive Control the Stochastic Approximation Algorithm. University of Maryland - Baltimore County, Department of Mathematics, Report #83-8.
• 7: William E. Biles , James J. Swain, Strategies for optimization of multiple-response simulation models, Proceedings of the 9th conference on Winter simulation, p.134-142, December 05-07, 1977, Gaitherburg, Maryland, United States
• 8: Deming, S. I'4. (t977). Optimization of Experimental Parameters in Chemical Analysis, Validation of Measurement Process. 162-175.
• 9: Farrell, W., McCall, C. H., and Russell, E. C. (1975). Optimization Techniques for Computerized Simulation Models. CACI, Inc. Technical Report 1200-4-75.
• 10: Peter W. Glynn, Stochastic approximation for Monte Carlo optimization, Proceedings of the 18th conference on Winter simulation, p.356-365, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318459]
• 11: Glynn, P. E. (1986b). Sensitivity Analysis for Stationary Probabilities of a Markov Chain. Proceedings of the 4th Army Conference on Applied Mathematics and Computers.
• 12: 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]
• 13: Gong, W. B. and Ho, Y. C. (1987). Smoothed Perturbation Analysis of Discrete Event Dynamic Systems. To appear in lk, EE Transactions on Automatic Control.
• 14: Goodwin, G. 15'.., Ramadge, P. J., and Caines, P. E. (1981). Discrete Time Stochastic Adaptive Control. Siam Journal of Control amt Optimization, 19, 829-853.
• 15: Goodwin, Ramadge, and Caines (1982). Corrigendum: Discrete Time Stochastic Adaptive Control. Siam Journal of Control and Optimization, 20, 893.
• 16: Hanssman, Dinif, Fisher, and Ramer (1980). Analytical Search Model for Optimum Seeking in Simulations. OR Spektrum 2.
• 17: Heidelberger, P. (1986). Convergence Properties of Infinitesimal Perturbation Analysis Estimates. Manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY.
• 18: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 19: Kesten, H. (1958). Accelerated Stochastic Approximation. Annals of M~thematical Stati,~tics 29, 41-59.
• 20: Kiefer, J. and Wolfowitz (1952). Stochastic Estimation of the Maximum of a Regression Function, Annals of Mathematical Statistics 23, 462-466.
• 21: Lai, T. L., and Robbins, H. (1979). Adaptive Design and Stochastic Approximation. 7"he Annals of Statistics 7, 1196- 1221.
• 22: Montgomery, D. C., and Bettencourt, V. M. (1977). Multiple Response Surface Methods in Computer Simulation. Simulation, 113-121.
• 23: Reiman, M. I., and Weiss, A. (1986). Sensitivity Analysis for Simulations via Likelihood Ratios. Operations Research, to appear.
• 24: Reiman, M. I., and Nguyen, P. (1987). Variance Reduction for Sensitivity Estimates Obtained from Regenerative Simulation. AT&T Manuscript.
• 25: Robbins, H., and Monroe, S (1951). On a Stochastic Approximation Technique, Annals of Mathematical Statistics 22, 400-407.
• 26: Rubinstein, R. Y. (1983). Smoothed Functionals in Stochastic Optimization, Mathematics of Operations Research 8, 26-33.
• 27: Rubinstein, R. Y., and Kreimer, J. (1982). Stochastic Optimization via Stochastic Approximation. Operations Research Statistics and Economics Mimeograph, Series N.350, Technion, Haifa, Israel.
• 28: Rubinstein, R. Y. (1987). Sensitivity Analysis of Computer Simulation Models via the Efficient Score. George Washington University, Department of Operations Research.
• 29: Rubinstein, R. Y. (1987b). The "What If" Problem in Simulation Analysis. GWU/IMSE/Serial T-514/87. The George Washington University, School of Engineering and Applied Sciences.
• 30: Rustagi, J. S. (1978). Optimization in Statistics: An Overview. Communications of Statistics - Simulation and Computation BT, 303-307.
• 31: Shanthikumar, J. G., and Sargent R. G. (1982). A Unifying View of Hybrid Simulation/Analytical Models and Modeling. Syracuse University, Department of IE/OR, Working Paper #82-003.
• 32: Segreti, A. C., Carter, W. H., and Wampler, G. L. (1979). Monte Carlo Evaluation of Several Sequential Optimization Techniques when the Response is Time to an Event. Journal of Statistical Computation and Simulation 9, 289-301.
• 33: Segreti, Carter, and Wampler (1981). A Monte Carlo Evaluation of the Robustness of Several Sequential Optimization Techniques when the Response is Time to an Event. Journal of Statistical Computation and Simulation 12, 209-216.
• 34: Smith, D. E. (1973). An Empirical Investigation of Optimum- Seeking in the Computer Simulation Situation. Operations Research 21, 475-497.
• 35: Suri, R. (1983). Infinitesimal Perturbation Analysis of Discrete Event Dynamic Systems: A General Theory. Proceedings of the 22nd {EEE Conference on Decision and Control.
• 36: Suri, R. and Leung, Y. T. (1987). Single Run Optimization of Discrete Event Simulations - An Empirical Study Using the M/M/1 Queue. Working paper, University of Wisconsin- Madison.
• 37: Vanderbei, R., Meketon, M., and Freedman, B. (1986). A Modification of Karmarkar's Linear Programming Algorithm. Algorithmica 1, 395-407.

INDEX TERMS

Primary Classification:
  A. General Literature

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

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