Article

On choosing parameters in retrospective-approximation algorithms for simulation-optimization

Author:

Raghu PasupathyAuthors Info & Claims

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

Pages 208 - 215

Published: 03 December 2006 Publication History

Abstract

The Simulation-Optimization (SO) problem is a constrained optimization problem where the objective function is observed with error, usually through an oracle such as a simulation. Retrospective Approximation (RA) is a general technique that can be used to solve SO problems. In RA, the solution to the SO problem is approached using solutions to a sequence of approximate problems, each of which is generated using a specified sample size and solved to a specified error tolerance. In this paper, our focus is parameter choice in RA algorithms, where the term parameter is broadly interpreted. Specifically, we present (i) conditions that guarantee convergence of estimated solutions to the true solution; (ii) convergence properties of the sample-size and error-tolerance sequences that ensure that the sequence of estimated solutions converge to the true solution in an optimal fashion; and (iii) a numerical procedure that efficiently solves the generated approximate problems for one-dimensional SO.

References

[1]

Andradóttir, S. 1990. Stochastic optimization with applications to discrete event systems. Ph.D. thesis, Department of Operations Research, Stanford University, Stanford, CA.

[2]

Andradóttir, S. 1991. A projected stochastic approximation algorithm. In Proceedings of the 1991 Winter Simulation Conference, ed. B. L. Nelson, D. W. Kelton, and G. M. Clark, 854--957.

Digital Library

[3]

Atlason, J., M. A. Epelman, and S. G. Henderson. 2002. Call center staffing with simulation and cutting plane methods. Annals of Operations Research 127:333--358.

[4]

Bazaara, M. S., H. Sherali, and C. M. Shetty. 2006. Nonlinear programming: Theory and algorithms. New York, NY.: John Wiley & Sons.

[5]

Bertsekas, D. 1999. Nonlinear programming. Nashua, NH.: Athena Scientific.

[6]

Blum, J. 1954. Multidimensional stochastic approximation. Annals of Mathematical Statistics 25:737--744.

[7]

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

[8]

de Mello, T. H. 2003. Variable-sample methods for stochastic optimization. ACM Transactions on Modeling and Computer Simulation 13:108--133.

Digital Library

[9]

Dupačová, J., and R. J. B. Wets. 1988. Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems. The Annals of Statistics 16:1517--1549.

[10]

Fabian, V. 1968. On asymptotic normality in stochastic approximation. Annals of Mathematical Statistics 39:1327--1332.

[11]

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

[12]

He, Y., M. C. Fu, and S. Marcus. 2003. Convergence of simultaneous perturbation stochastic approximation for nondifferentiable optimization. IEEE Transactions on Automatic Control 48:1459--1463.

[13]

Healy, K., and L. W. Schruben. 1991. Retrospective simulation response optimization. In Proceedings of the 1991 Winter Simulation Conference, ed. B. L. Nelson, D. W. Kelton, and G. M. Clark, 954--957: Institute of Electrical and Electronics Engineers: Piscataway, New Jersey.

Digital Library

[14]

Kesten, H. 1958. Accelerated stochastic approximation. Annals of Mathematical Statistics 21:41--59.

[15]

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

[16]

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

[17]

Nemirovski, A., and A. Shapiro. 2004. Convex approximations of chance constrained programs. Optimization On-line. <http://www.optimization-online.org/>.

[18]

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

[19]

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

[20]

Rubinstein, R. Y., and A. Shapiro. 1993. Discrete event systems: sensitivity analysis and stochastic optimization by the score function method. New York, NY.: John Wiley & Sons.

[21]

Ruszczynski, and Shapiro. (Eds.) 2003. Stochastic programming. Handbook in operations research and management science. New York, NY.: Elsevier.

[22]

Safizadeh, M. H. 1990. Optimization in simulation: current issues and the future outlook. Naval Research Logistics 37:807--825.

[23]

Shapiro, A. 2000. Stochastic programming by monte carlo simulation methods. Stochastic Programming E-Print Series. <http://hera.rz.hu-berlin.de/speps/>.

[24]

Shapiro, A., and T. H. de Mello. 2000. On the rate of convergence of optimal solutions of monte carlo approximations of stochastic programs. SIAM Journal on Optimization 11 (1): 70--86.

Digital Library

[25]

Spall, J. C. 1998. Implementation of the simultaneous perturbation algorithm for stochastic optimization. IEEE Transactions on Aerospace and Electronic Systems 34:817--823.

[26]

Spall, J. C. 2000. Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Transactions on Automatic Control 45:1839--1853.

[27]

Venter, H. J. 1967. An extension of the robbins-monro procedure. Annals of Mathematical Statistics 38:181--190.

[28]

Wasan, M. T. 1969. Stochastic approximation. Cambridge, UK: Cambridge University Press.

Cited By

Krejić NKrklec N(2013)Line search methods with variable sample size for unconstrained optimizationJournal of Computational and Applied Mathematics10.1016/j.cam.2012.12.020245(213-231)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.cam.2012.12.020
Pasupathy RSchmeiser B(2009)Retrospective-approximation algorithms for the multidimensional stochastic root-finding problemACM Transactions on Modeling and Computer Simulation10.1145/1502787.150278819:2(1-36)Online publication date: 23-Mar-2009
https://dl.acm.org/doi/10.1145/1502787.1502788

On choosing parameters in retrospective-approximation algorithms for simulation-optimization
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Inexact Successive quadratic approximation for regularized optimization

Successive quadratic approximations, or second-order proximal methods, are useful for minimizing functions that are a sum of a smooth part and a convex, possibly nonsmooth part that promotes regularization. Most analyses of iteration complexity focus on ...
On Choosing Parameters in Retrospective-Approximation Algorithms for Stochastic Root Finding and Simulation Optimization

The stochastic root-finding problem is that of finding a zero of a vector-valued function known only through a stochastic simulation. The simulation-optimization problem is that of locating a real-valued function's minimum, again with only a stochastic ...
Dual Variable Metric Algorithms for Constrained Optimization

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

2
Total Citations
View Citations
109
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

Krejić NKrklec N(2013)Line search methods with variable sample size for unconstrained optimizationJournal of Computational and Applied Mathematics10.1016/j.cam.2012.12.020245(213-231)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.cam.2012.12.020
Pasupathy RSchmeiser B(2009)Retrospective-approximation algorithms for the multidimensional stochastic root-finding problemACM Transactions on Modeling and Computer Simulation10.1145/1502787.150278819:2(1-36)Online publication date: 23-Mar-2009
https://dl.acm.org/doi/10.1145/1502787.1502788

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