skip to main content
10.5555/1030453.1030505acmconferencesArticle/Chapter ViewAbstractPublication PageswscConference Proceedingsconference-collections
Article

Recent advances in simulation optimization: confidence regions for stochastic approximation algorithms

Published: 08 December 2002 Publication History

Abstract

In principle, known central limit theorems for stochastic approximation schemes permit the simulationist to provide confidence regions for both the optimum and optimizer of a stochastic optimization problem that is solved by means of such algorithms. Unfortunately, the covariance structure of the limiting normal distribution depends in a complex way on the problem data. In particular, the covariance matrix depends not only on variance constants but also on even more statistically challenging parameters (e.g. the Hessian of the objective function at the optimizer). In this paper, we describe an approach to producing such confidence regions that avoids the necessity of having to explicitly estimate the covariance structure of the limiting normal distribution. This procedure offers an easy way for the simulationist to provide confidence regions in the stochastic optimization setting.

References

[1]
Billingsley, P. 1995. Probability and Measure. Third Edition. John Wiley & Sons, New York.
[2]
Fu, M. C., and J. Q. Hu. 1997. Conditional Monte Carlo: Gradient estimation and optimization applications. Kluwer Academic Publisher, Boston.
[3]
Gill, P. E., W. Murray, and M. H. Wright. 1981. Practical Optimization, Academic Press, London and New York.
[4]
Glasserman, P. 1991. Gradient estimation via perturbation analysis. Boston: Kluwer.
[5]
Glynn, P. W. 1986. Stochastic approximation for Monte Carlo optimization. In Proceedings of the 1986 Winter Simulation Conference, 356--365.
[6]
Glynn, P. W. 1990. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM 33:75--84.
[7]
Glynn, P. W. and D. L. Iglehart 1990. Simulation output analysis using standardized time series. Mathematics of Operations Research 15:1--16.
[8]
Kushner, H. J., and G. G. Yin. 1997. Stochastic approximation algorithms and applications. New York: Springer-Verlag.
[9]
L'Ecuyer, P., and P. W. Glynn. 1994. Stochastic optimization by simulation: Convergence proofs for the GI/G/1 queue in steady-state. Management Science 40:1562--1578.
[10]
L'Ecuyer, P., N. Giroux, and P. W. Glynn 1994. Stochastic optimization by simulation: Numerical Experiments with the M/M/1 queue in steady-state. Management Science 40:1245--1261.
[11]
Ljung, L., G. Ch. Pflug, and H. Walk. 1992. Stochastic approximation and optimization of random systems. Basel: Birkhäuser Verlag.
[12]
Loeve, M. 1977. Probability Theory, Vol. 1, 4th edition, Springer-Verlag.
[13]
Luenberger, D. G. 1984. Introduction to Linear and Nonlinear Programming, Addison-Wesley, Menlo Park, California.
[14]
Nevel'son, M. B., and R. Z. Has'minskii. 1973. Stochastic Approximation and Recursive Estimation. American mathematical Society, Providence, Rhode Island.
[15]
Polyak, B. T., and A. B. Juditsky. 1992. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization 30:838--855.
[16]
Rubinstein, R. Y. 1992. Sensitivity analysis of discrete event systems by the "push-out" method. Annals of Operations Research 39:229--237.
[17]
Searle, S. R. 1982. Matrix Algebra Useful for Statistics. John Wiley, New York.
[18]
Williams, D. 1991. Probability with Martingales. Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge.

Cited By

View all
  • (2021)On constructing confidence region for model parameters in stochastic gradient descent via batch meansProceedings of the Winter Simulation Conference10.5555/3522802.3522822(1-12)Online publication date: 13-Dec-2021
  • (2011)The stochastic root-finding problemACM Transactions on Modeling and Computer Simulation10.1145/1921598.192160321:3(1-23)Online publication date: 4-Feb-2011
  • (2008)The mathematics of continuous-variable simulation optimizationProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516774(122-132)Online publication date: 7-Dec-2008
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
WSC '02: Proceedings of the 34th conference on Winter simulation: exploring new frontiers
December 2002
2143 pages
ISBN:0780376153
  • General Chair:
  • Jane L. Snowdon,
  • Program Chair:
  • John M. Charnes

Sponsors

  • INFORMS/CS: Institute for Operations Research and the Management Sciences/College on Simulation
  • IIE: Institute of Industrial Engineers
  • ASA: American Statistical Association
  • ACM: Association for Computing Machinery
  • SIGSIM: ACM Special Interest Group on Simulation and Modeling
  • IEEE/CS: Institute of Electrical and Electronics Engineers/Computer Society
  • NIST: National Institute of Standards and Technology
  • (SCS): The Society for Modeling and Simulation International
  • IEEE/SMCS: Institute of Electrical and Electronics Engineers/Systems, Man, and Cybernetics Society

Publisher

Winter Simulation Conference

Publication History

Published: 08 December 2002

Check for updates

Qualifiers

  • Article

Conference

WSC02
Sponsor:
  • INFORMS/CS
  • IIE
  • ASA
  • ACM
  • SIGSIM
  • IEEE/CS
  • NIST
  • (SCS)
  • IEEE/SMCS
WSC02: Winter Simulation Conference 2002
December 8 - 11, 2002
California, San Diego

Acceptance Rates

WSC '02 Paper Acceptance Rate 166 of 185 submissions, 90%;
Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)On constructing confidence region for model parameters in stochastic gradient descent via batch meansProceedings of the Winter Simulation Conference10.5555/3522802.3522822(1-12)Online publication date: 13-Dec-2021
  • (2011)The stochastic root-finding problemACM Transactions on Modeling and Computer Simulation10.1145/1921598.192160321:3(1-23)Online publication date: 4-Feb-2011
  • (2008)The mathematics of continuous-variable simulation optimizationProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516774(122-132)Online publication date: 7-Dec-2008
  • (2006)Numerical estimation of the impact of interferences on the localization problem in sensor networksProceedings of the 5th international conference on Experimental Algorithms10.1007/11764298_2(13-23)Online publication date: 24-May-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media