Article

Gradient-based simulation optimization

Author:

Sujin KimAuthors Info & Claims

WSC '06: Proceedings of the 38th conference on Winter simulation

Pages 159 - 167

Published: 03 December 2006 Publication History

Abstract

We present a review of methods for simulation optimization. In particular, we focus on gradient-based techniques for continuous optimization. We demonstrate the main concepts using as an example the multidimensional newsvendor problem. We also discuss mathematical techniques and results that are useful in verifying and analyzing the simulation optimization procedures.

References

[1]

Andradóttir, S. 1998. A review of simulation optimization techniques. In Proceedings of the 1998 Winter Simulation Conference, ed. D. Medeiros, E. Watson, J. S. Carson, and M. S. Manivannan, 151--158.

Digital Library

[2]

Azadivar, F. 1999. Simulation optimization methodologies. In Proceedings of the 1999 Winter Simulation Conference, ed. P. A. Farrington, H. Black Nembhard, D. T. Sturrock, and G. W. Evans, 93--100.

Digital Library

[3]

Bastin, F., C. Cirillo, and P. L. Toint. 2007. Convergence theory for nonconvex stochastic programming with an application to mixed logit. Mathematical Programming 108:207--234.

Digital Library

[4]

Birge, J. R., and F. Louveaux. 1997. Introduction to stochastic programming. New York: Springer.

[5]

Chen, H., and B. W. Schmeiser. 2001. Stochastic root finding via retrospective approximation. IIE Transactions 33:259--275.

[6]

Fu, M. C. 1990. Convergence of the GI/G/1 queue using infinitesimal perturbation analysis. Journal of Optimization Theory and Applications 65:149--160.

Digital Library

[7]

Fu, M. C. 1994. Optimization via simulation: a review. Annals of Operations Research 53:199--247.

[8]

Fu, M. C. 2002. Optimization for simulation: theory vs. practice. INFORMS Journal on Computing 14:192--215.

Digital Library

[9]

Fu, M. C., F. Glover, and J. April. 2005. Simulation optimization: A review, new developments and applications. In Proceedings of the 2005 Winter Simulation Conference, ed. M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, 83--95.

Digital Library

[10]

Fu, M. C., and J.-Q. Hu. 1996. A comparison of perturbation analysis techniques. In Proceedings of the 1996 Winter Simulation Conference, ed. J.M. Charnes, D. J. Morrice, D. T. Brunner, and J. J. Swain, 295--301.

Digital Library

[11]

Fu, M. C., and J.-Q. Hu. 1997. Conditional Monte Carlo: Gradient estimation and optimization applications. Boston: Kluwer.

[12]

Glasserman, P. 1991. Gradient estimation via perturbation analysis. The Netherlands: Kluwer.

[13]

Glynn, P. W. 1989. Optimization of stochastic systems via simulation. In Proceedings of the 1989 Winter Simulation Conference, 90--105.

Digital Library

[14]

Harrison, J. M., and J. A. Van Mieghem. 1999. Multi-resource investment stragies: Operational hedging under demand uncertainty. European Journal of Operational Research 113:17--29.

[15]

Healy, K., and L. W. Schruben. 1991. Retrospective simulation response optimization. In Proceedings of the 1991 Winter Simulation Conference, ed. B. L. Nelson, W. D. Kelton, and G. Clark, 901--907.

Digital Library

[16]

Henderson, S. G., and B. L. Nelson. (Eds.) 2006. Handbook of simulation. Elsevier. Forthcoming.

[17]

Kiefer, J., and J. Wolfowitz. 1952. Stochastic estimation of the maximum of a regression function. Annals of Mathematical Statistics 23:462--466.

[18]

Kushner, H. J., and D. C. Clark. 1978. Stochastic approximation methods for constrained and unconstrained systems. New York: Springer-Verlag.

[19]

Kushner, H. J., and G. G. Yin. 2003. Stochastic approximation and recursive algorithms and applications. 2nd ed. New York: Springer-Verlag.

[20]

L'Ecuyer, P. 1991. A unified view of the IPA, SF and LR gradient estimation techniques. Management Science 36:1364--1383.

Digital Library

[21]

L'Ecuyer, P. 1995. On the interchange of derivative and expectation for likelihood ratio derivative estimators. Management Science 41:738--748.

Digital Library

[22]

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.

Digital Library

[23]

L'Ecuyer, P., and G. Perron. 1994. On the convergence rates of IPA and FDC derivative estimators. Operations Research 42(4):643--656.

Digital Library

[24]

Plambeck, E. L., B.-R. Fu, S. M. Robinson, and R. Suri. 1996. Sample-path optimization of convex stochastic performance functions. Mathematical Programming 75:137--176.

Digital Library

[25]

Polyak, B., and A. Juditsky. 1992. Acceleration of stochastic approximation by averaging. SIAM Journals on Control and Optimization 30(4):838--855.

Digital Library

[26]

Robbins, H., and S. Monro. 1951. A stochastic approximation method. Annals of Mathematical Statistics 22:400--407.

[27]

Robinson, S. M. 1996. Analysis of sample-path optimization. Mathematics of Operations Research 21:513--528.

Digital Library

[28]

Rubinstein, R. Y., and A. Shapiro. 1993. Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method. Chichester: Wiley.

[29]

Ruppert, D. 1985. A Newton-Raphson version of the multivariate Robbins-Monro procedure. Annals of Statistics 13:236--245.

[30]

Shapiro, A. 1993. Asymptotic behavior of optimal solutions in stochastic programming. Mathematics of Operations Research 18:829--845.

Digital Library

[31]

Shapiro, A. 2003. Monte Carlo sampling methods. In Stochastic Programming, ed. A. Ruszczynski and A. Shapiro, Handbooks in Operations Research and Management Science. Elsevier.

[32]

Van Mieghem, J. A., and N. Rudi. 2002. Newsvendor networks: Inventory management and capacity investment with discretionarty activities. Manufacturing and Service Operations Management 4(4):313--335.

Digital Library

[33]

Zazanis, M. A., and R. Suri. 1993. Convergence rates of finite-difference sensitivity estimates for stochastic systems. Operations Research 41:694--703.

Digital Library

Cited By

Ryzhov IPasupathy RHonnappa HRossetti MHunter S(2024)Introduction to Optimal TransportProceedings of the Winter Simulation Conference10.5555/3712729.3712737(101-115)Online publication date: 15-Dec-2024
https://dl.acm.org/doi/10.5555/3712729.3712737
Broadie MCicek DZeevi A(2014)Multidimensional stochastic approximationACM Transactions on Modeling and Computer Simulation10.1145/255308524:1(1-28)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2553085
Hamm ASalfeld TWeber SHill RKuhl M(2013)Stochastic root finding for optimized certainty equivalentsProceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World10.5555/2675983.2676101(922-932)Online publication date: 8-Dec-2013
https://dl.acm.org/doi/10.5555/2675983.2676101
Show More Cited By

Gradient-based simulation optimization
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Gradient-based adaptive particle swarm optimizer with improved extremal optimization

Most real-world applications can be formulated as optimization problems, which commonly suffer from being trapped into the local optima. In this paper, we make full use of the global search capability of particle swarm optimization (PSO) and local ...
Example-based learning particle swarm optimization for continuous optimization

Particle swarm optimization (PSO) is a heuristic optimization technique based on swarm intelligence that is inspired by the behavior of bird flocking. The canonical PSO has the disadvantage of premature convergence. Several improved PSO versions do well ...
Improved Particle Swarm Optimization Based on Gradient Descent Method
CSAE '20: Proceedings of the 4th International Conference on Computer Science and Application Engineering

Due to the lack of effective guidance on particle's speed and precocity in standard particle swarm optimization, a particle swarm optimization on the basis of gradient information and time-varying acceleration coefficient (TVAC), namely gradient descent ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '06: Proceedings of the 38th conference on Winter simulation

December 2006

2429 pages

ISBN:1424405017

Editors:
L. Felipe Perrone
Bucknell University
,
Barry G. Lawson
University of Richmond
,
Jason Liu
Colorado School of Mines
,
Frederick P. Wieland
Sensis Corporation
,
General Chair:
David Nicol
University of Illinois, Urbana-Champaign
,
Program Chair:
Richard Fujimoto
College of Computing, Georgia Tech

Sponsors

IIE: Institute of Industrial Engineers
ASA: American Statistical Association
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEEE-CS\DATC: The IEEE Computer Society
SIGSIM: ACM Special Interest Group on Simulation and Modeling
NIST: National Institute of Standards and Technology
(SCS): The Society for Modeling and Simulation International
INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation

Publisher

Winter Simulation Conference

Publication History

Published: 03 December 2006

Check for updates

Qualifiers

Article

Conference

WSC06

Sponsor:

IIE
ASA
IEICE ESS
IEEE-CS\DATC
SIGSIM
NIST
(SCS)
INFORMS-CS

WSC06: Winter Simulation Conference 2006

December 3 - 6, 2006

California, Monterey

Acceptance Rates

WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
374
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ryzhov IPasupathy RHonnappa HRossetti MHunter S(2024)Introduction to Optimal TransportProceedings of the Winter Simulation Conference10.5555/3712729.3712737(101-115)Online publication date: 15-Dec-2024
https://dl.acm.org/doi/10.5555/3712729.3712737
Broadie MCicek DZeevi A(2014)Multidimensional stochastic approximationACM Transactions on Modeling and Computer Simulation10.1145/255308524:1(1-28)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2553085
Hamm ASalfeld TWeber SHill RKuhl M(2013)Stochastic root finding for optimized certainty equivalentsProceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World10.5555/2675983.2676101(922-932)Online publication date: 8-Dec-2013
https://dl.acm.org/doi/10.5555/2675983.2676101
Qu HRyzhov IFu MHill RKuhl M(2013)Learning logistic demand curves in business-to-business pricingProceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World10.5555/2675983.2675987(29-40)Online publication date: 8-Dec-2013
https://dl.acm.org/doi/10.5555/2675983.2675987
Kim SZhang DYücesan E(2010)Convergence properties of direct search methods for stochastic optimizationProceedings of the Winter Simulation Conference10.5555/2433508.2433628(1003-1011)Online publication date: 5-Dec-2010
https://dl.acm.org/doi/10.5555/2433508.2433628
özdemir DYücesan EHerer YDunkin AIngalls R(2009)Sample average approximation approach to multi-location transshipment problem with capacitated productionWinter Simulation Conference10.5555/1995456.1995782(2384-2394)Online publication date: 13-Dec-2009
https://dl.acm.org/doi/10.5555/1995456.1995782
Broadie MCicek DZeevi ADunkin AIngalls R(2009)An adaptive multidimensional version of the Kiefer-Wolfowitz stochastic approximation algorithmWinter Simulation Conference10.5555/1995456.1995549(601-612)Online publication date: 13-Dec-2009
https://dl.acm.org/doi/10.5555/1995456.1995549
Horng SLin S(2009)An ordinal optimization theory-based algorithm for a class of simulation optimization problems and applicationExpert Systems with Applications: An International Journal10.5555/1512993.151312536:5(9340-9349)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.5555/1512993.1513125
Paternina-Arboleda CMontoya-Torres JFábregas-Ariza AJefferson TFowler JIngalls R(2008)Simulation-optimization using a reinforcement learning approachProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516984(1376-1383)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.5555/1516744.1516984
Kim SHenderson SJefferson TFowler JIngalls R(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
https://dl.acm.org/doi/10.5555/1516744.1516774
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten