article

On Choosing Parameters in Retrospective-Approximation Algorithms for Stochastic Root Finding and Simulation Optimization

Author:

Raghu PasupathyAuthors Info & Claims

Operations Research, Volume 58, Issue 4-Part-1

Pages 889 - 901

https://doi.org/10.1287/opre.1090.0773

Published: 01 July 2010 Publication History

Abstract

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 simulation that generates function estimates. Retrospective approximation (RA) is a sample-path technique for solving such problems, where the solution to the underlying problem is approached via solutions to a sequence of approximate deterministic problems, each of which is generated using a specified sample size, and solved to a specified error tolerance. Our primary focus, in this paper, is providing guidance on choosing the sequence of sample sizes and error tolerances in RA algorithms. We first present an overview of the conditions that guarantee the correct convergence of RA's iterates. Then we characterize a class of error-tolerance and sample-size sequences that are superior to others in a certain precisely defined sense. We also identify and recommend members of this class and provide a numerical example illustrating the key results.

References

[1]

Andradóttir, S., Henderson, S. G. and Nelson, B. L., "An overview of simulation optimization via random search," Simulation. Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, pp. 617-631, 2006.

[2]

Atlason, J., Epelman, M. A. and Henderson, S. G., "Call center staffing with simulation and cutting plane methods," Ann. Oper. Res., v127, pp. 333-358, 2004.

[3]

Atlason, J., Epelman, M. A. and Henderson, S. G., "Optimizing call center staffing using simulation and analytic center cutting-plane methods," Management Sci., v54, pp. 295-309, 2008.

Digital Library

[4]

Barton, R. R., Meckesheimer, M., Henderson, S. G. and Nelson, B. L., "Metamodel-based simulation optimization," Simulation. Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, pp. 535-574, 2006.

[5]

Bastin, F., Cirillo, C. and Toint, P. L., "Convergence theory for nonconvex stochastic programming with an application to mixed logit," Math. Programming, v108, pp. 207-234, 2006.

Digital Library

[6]

Bayraksan, G. and Morton, D. P., "Assessing solution quality in stochastic programs," Math. Programming Ser. B, v108, pp. 495-514, 2007.

Digital Library

[7]

Bayraksan, G. and Morton, D. P., "A sequential sampling procedure for stochastic programming," Oper. Res., 2010.

[8]

Bhatnagar, S. and Borkar, V. S., "A two time scale stochastic approximation scheme for simulation based parametric optimization," Probab. Engrg. Informational Sci., v12, pp. 519-531, 1998.

[9]

Bhatnagar, S., Fu, M. C., Marcus, S. I. and Bhatnagar, S., "Two-timescale algorithms for simulation optimization of hidden Markov models," IIE Trans., v33, pp. 245-258, 2001.

[10]

Boyd, S., Convex Optimization, Cambridge University Press, Cambridge, UK, 2004.

[11]

Chen, H. and Schmeiser, B. W., "Stochastic root finding via retrospective approximation," IIE Trans., v33, pp. 259-275, 2001.

[12]

Fu, M. C., "Optimization for simulation: Theory vs. practice," INFORMS J. Comput., v14, pp. 192-215, 2002.

[13]

Gill, P. E., Murray, W. and Wright, M. H., Practical Optimization, Elsevier, London, 1986.

[14]

Glasserman, P., Gradient Estimation via Perturbation Analysis, Kluwer, Dordrecht, The Netherlands, 1991.

[15]

Healy, K., Schruben, L. W., Nelson, B. L., Kelton, D. W. and Clark, G. M., "Retrospective simulation response optimization," Proc. 1991 Winter Simulation Conf., Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 954-957, 1991.

[16]

Herer, Y. T., Tzur, M. and Yucesan, E., "The multilocation transshipment problem," IIE Trans., v38, pp. 185-200, 2006.

[17]

Higle, J. and Sen, S., "Stochastic decomposition: An algorithm for two-stage linear programs with recourse," Math. Oper. Res., v16, pp. 650-669, 1991.

[18]

Homem-de-Mello, T., "Variable-sample methods for stochastic optimization," ACM Trans. Modeling Comput. Simulation, v13, pp. 108-133, 2003.

Digital Library

[19]

Homem-de-Mello, T., "On rates of convergence for stochastic optimization problems under non-i.i.d. sampling," SIAM J. Optim., v19, pp. 524-551, 2008.

Digital Library

[20]

Homem-de-Mello, T., Shapiro, A. and Spearman, M. L., "Finding optimal material release times using simulation-based optimization," Management Sci., v45, pp. 86-102, 1999.

Digital Library

[21]

Kim, S.-H., Nelson, B. L., Henderson, S. G. and Nelson, B. L., "Selecting the best system," Simulation. Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, pp. 501-534, 2006.

[22]

Kleywegt, A. J., Shapiro, A. and Homem-de-Mello, T., "The sample average approximation method for stochastic discrete optimization," SIAM J. Optim., v12, pp. 479-502, 2001.

Digital Library

[23]

Kushner, H. and Clark, D., Stochastic Approximation Methods for Constrained and Unconstrained Systems, Springer-Verlag, New York, 1978.

[24]

Kushner, H. J. and Yin, G. G., Stochastic Approximation and Recursive Algorithms and Applications, Springer-Verlag, New York, 2003.

[25]

Mak, W. K., Morton, D. P. and Wood, R. K., "Monte Carlo bounding techniques for determining solution quality in stochastic programs," Oper. Res. Lett., v24, pp. 47-56, 1999.

Digital Library

[26]

Nemirovski, A. and Shapiro, A., "Convex approximations of chance constrained programs," Optim. Online, 2004.

[27]

Ólafsson, S., Henderson, S. G. and Nelson, B. L., "Metaheuristics," Simulation. Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, pp. 633-654, 2006.

[28]

Ortega, J. M. and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.

Digital Library

[29]

Pasupathy, R., Perrone, L., Wieland, F., Liu, J., Lawson, B., Nicol, D. and Fujimoto, R., "On choosing parameters in retrospective-approximation algorithms for simulation-optimization," Proc. 2006 Winter Simulation Conf., Institute of Electrical and Electronics Engineers, Piscataway, NJ, pp. 208-215, 2006.

[30]

Pasupathy, R. and Schmeiser, B. W., "Retrospective-approximation algorithms for multidimensional stochastic root-finding problems," ACM TOMACS, v19, pp. 5:1-5:36, 2009.

Digital Library

[31]

Plambeck, E. L., Fu, B. R., Robinson, S. M. and Suri, R., "Sample-path optimization of convex stochastic performance functions," Math. Programming, v75, pp. 137-176, 1996.

Digital Library

[32]

Polak, E. and Royset, J. O., "Efficient sample sizes in stochastic nonlinear programming," J. Comput. Appl. Math., v217, pp. 301-310, 2008.

Digital Library

[33]

Prakash, P., Deng, G., Converse, M. C., Webster, J. G., Mahvi, G. M. and Ferris, M. C., "Design optimization of a robust sleeve antenna for hepatic microwave ablation," Phys. Med. Biol., v53, pp. 1057-1069, 2008.

[34]

Robbins, H. and Monro, S., "A stochastic approximation method," Ann. Math. Statist., v22, pp. 400-407, 1951.

[35]

Robinson, S., "Analysis of sample-path optimization," Math. Oper. Res., v21, pp. 513-528, 1996.

Digital Library

[36]

Rubinstein, R. Y. and Shapiro, A., Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method, John Wiley & Sons, New York, 1993.

[37]

Rudin, W., Principles of Mathematical Analysis, Mc-Graw Hill, New York, 1976.

[38]

Shapiro, A., "Asymptotic analysis of stochastic programs," Ann. Oper. Res., v30, pp. 169-186, 1991.

Digital Library

[39]

Shapiro, A., "Stochastic programming by Monte Carlo simulation methods," Stochastic Programming E-Print Ser., 2000.

[40]

Shapiro, A., Ruszczynski, A. and Shapiro, A., "Monte Carlo sampling methods," Stochastic Programming. Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, pp. 353-426, 2004.

[41]

Spall, J. C., Introduction to Stochastic Search and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2003.

[42]

Spall, J. C., "Feedback and weighting mechanisms for improving Jacobian (Hessian) estimates in the adaptive simultaneous perturbation algorithm," Proc. Amer. Control Conf., 2006.

[43]

Szechtman, R., Henderson, S. G. and Nelson, B. L., "A Hilbert space approach to variance reduction," Simulation. Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, pp. 259-290, 2006.

[44]

Tadic, V. and Meyn, S. P., "Asymptotic properties of two time-scale stochastic approximation algorithms with constant step sizes," Proc. Amer. Control Conf., 2003.

[45]

Verweij, B., Ahmed, S., Kleywegt, A., Nemhauser, G. and Shapiro, A., "The sample average approximation method applied to stochastic vehicle routing problems: A computational study," Comput. Appl. Optim., v24, pp. 289-333, 2003.

[46]

Wardi, Y., Melamed, B., Cassandras, C. G. and Panayiotou, C. G., "On-line IPA gradient estimators in stochastic continuous fluid models," J. Optim. Theory Appl., v115, pp. 369-405, 2002.

Digital Library

Cited By

Lam HZhang XZhang X(2023)Enhanced Balancing of Bias-Variance Tradeoff in Stochastic EstimationOperations Research10.1287/opre.2022.231971:6(2352-2373)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1287/opre.2022.2319
He LShanbhag USong E(2023)Stochastic Approximation for Multi-period Simulation Optimization with Streaming Input DataACM Transactions on Modeling and Computer Simulation10.1145/361759534:2(1-27)Online publication date: 29-Aug-2023
https://dl.acm.org/doi/10.1145/3617595
Zhou ZHonnappa HPasupathy R(2022)Sample Average Approximation over Function SpacesProceedings of the Winter Simulation Conference10.5555/3586210.3586216(61-72)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.5555/3586210.3586216
Show More Cited By

Recommendations

Discrete Optimization via Simulation Using COMPASS

We propose an optimization-via-simulation algorithm, called COMPASS, for use when the performance measure is estimated via a stochastic, discrete-event simulation, and the decision variables are integer ordered. We prove that COMPASS converges to the ...
Shape - a Stochastic Hybrid Approximation Procedure for Two-Stage Stochastic Programs

We consider the problem of approximating the expected recourse function for two-stage stochastic programs. Our problem is motivated by applications that have special structure, such as an underlying network that allows reasonable approximations to the ...
A Sequential Sampling Procedure for Stochastic Programming

We develop a sequential sampling procedure for a class of stochastic programs. We assume that a sequence of feasible solutions with an optimal limit point is given as input to our procedure. Such a sequence can be generated by solving a series of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 58, Issue 4-Part-1

July 2010

266 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 July 2010

Accepted: 01 November 2008

Received: 01 March 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
1
Total Downloads

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

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lam HZhang XZhang X(2023)Enhanced Balancing of Bias-Variance Tradeoff in Stochastic EstimationOperations Research10.1287/opre.2022.231971:6(2352-2373)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1287/opre.2022.2319
He LShanbhag USong E(2023)Stochastic Approximation for Multi-period Simulation Optimization with Streaming Input DataACM Transactions on Modeling and Computer Simulation10.1145/361759534:2(1-27)Online publication date: 29-Aug-2023
https://dl.acm.org/doi/10.1145/3617595
Zhou ZHonnappa HPasupathy R(2022)Sample Average Approximation over Function SpacesProceedings of the Winter Simulation Conference10.5555/3586210.3586216(61-72)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.5555/3586210.3586216
Jalilzadeh ANedić AShanbhag UYousefian F(2022)A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex OptimizationMathematics of Operations Research10.1287/moor.2021.114747:1(690-719)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1287/moor.2021.1147
Hao SZhang DDong M(2022)Iteratively sampling scheme for stochastic optimization with variable number sample pathOperations Research Letters10.1016/j.orl.2022.03.00650:3(347-355)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.orl.2022.03.006
Zhang MMatta AAlfieri A(2020)Sample-path algorithm for global optimal solution of resource allocation in queueing systems with performance constraintsProceedings of the Winter Simulation Conference10.5555/3466184.3466502(2767-2778)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466502
Krklec Jerinkić NRožnjik A(2020)Penalty variable sample size method for solving optimization problems with equality constraints in a form of mathematical expectationNumerical Algorithms10.1007/s11075-019-00699-683:2(701-718)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s11075-019-00699-6
Pasupathy RSon YHaas P(2019)The number of random restarts required to identify all solutions to a nonlinear systemProceedings of the Winter Simulation Conference10.5555/3400397.3400684(3540-3550)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3400397.3400684
Krejić NKrklec Jerinkić N(2019)Spectral projected gradient method for stochastic optimizationJournal of Global Optimization10.1007/s10898-018-0682-673:1(59-81)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10898-018-0682-6
Newton DPasupathy RYousefian FJohansson BJain S(2018)Recent trends in stochastic gradient descent for machine learning and big dataProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320569(366-380)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320569
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Issue’s Table of Contents