More Web Proxy on the site http://driver.im/

Article

Retrospective approximation algorithms for the multidimensional stochastic root-finding problem

Authors:

Raghu Pasupathy,

Bruce W. SchmeiserAuthors Info & Claims

WSC '04: Proceedings of the 36th conference on Winter simulation

Pages 520 - 528

Published: 05 December 2004 Publication History

Abstract

The stochastic root-finding problem (SRFP) is that of solving a system of q equations in q unknowns using only an oracle that provides estimates of the function values. This paper presents a family of algorithms to solve the multidimensional (q ≥ 1) SRFP, generalizing Chen and Schmeiser's one-dimensional retrospective approximation (RA) family of algorithms. The fundamental idea used in the algorithms is to generate and solve, with increasing accuracy, a sequence of approximations to the SRFP. We focus on a specific member of the family, called the Bounding RA algorithm, which finds a sequence of polytopes that progressively decrease in size while approaching the solution. The algorithm converges almost surely and exhibits good practical performance with no user tuning of parameters, but no convergence proofs or numerical results are included here.

References

[1]

Andradóttir, S. 1990. Stochastic Optimization with Applications to Discrete Event Systems, Doctoral Dissertation, Department of Operations Research, Stanford University, Stanford, California.

[2]

Andradóttir, S. 1991. A projected stochastic approximation algorithm. In Proceedings of the 1991 Winter Simulation Conference, ed. B. L. Nelson, W. D. Kelton, and G. M. Clark, 954--957. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.

Digital Library

[3]

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

[4]

Chen, H. 1994. Stochastic Root Finding in System Design, Doctoral Dissertation, School of Industrial Engineering, Purdue University, West Lafayette, Indiana.

[5]

Chen, H. and B. W. Schmeiser. 1994a. Stochastic root finding: problem definition, examples, and algorithms. In Proceedings of the Third Industrial Engineering Research Conference, ed. L. Burke and J. Jackman, 605--610. Norcross, Georgia: Institute of Industrial Engineers.

[6]

Chen, H. and B. W. Schmeiser. 1994b. Retrospective approximation algorithms for stochastic root finding. In Proceedings of the 1994 Winter Simulation Conference, ed. J. D. Tew, S. Manivannan, D. A. Sadowski, and A. F. Seila, 255--261. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.

Digital Library

[7]

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

[8]

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

[9]

Gürkan, G., A. Y. Ozge and S. Robinson. 1994. Sample-path optimization in simulation. In Proceedings of the 1991 Winter Simulation Conference, ed. J. D. Tew, S. Manivannan, D. A. Sadowski, and A. F. Seila, 247--254. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.

Digital Library

[10]

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. M. Clark, 954--957. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.

Digital Library

[11]

Hiriart-Urruty, J. -B., and C. Lemarechal. 1993. Convex Analysis and Minimization Algorithms I: Fundamentals (Grundlehren Der Mathematischen Wissenschaften, No 305). New York: Springer-Verlag.

[12]

Homem-de-Mello, T., A. Shapiro and M. L. Spearman. 1999. Finding optimal release times using simulation based optimization. Management Science 45: 86--102.

Digital Library

[13]

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

[14]

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

[15]

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

Digital Library

[16]

Pasupathy, R. and B. W. Schmeiser. 2003. Some issues in multivariate stochastic root finding. In Proceedings of the 2003 Winter Simulation Conference, ed. S. Chick, P. J. Sánchez, D. Ferrin, and D. J. Morrice, 574--577. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.

Digital Library

[17]

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

[18]

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

[19]

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

[20]

Shapiro, A. and T. Homem-de-Mello. 1997. A simulation-based approach to two-stage stochastic programming with recourse. Mathematical Programming 81: 301--325.

Digital Library

[21]

Spall, J. C. 1999. Stochastic optimization and the simultaneous perturbation method. In Proceedings of the 1999 Winter Simulation Conference, ed. P. A. Farrington, H. B. Nembhard, D. T. Sturrock, and G. W. Evans, 101--109. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers.

Digital Library

[22]

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

[23]

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

[24]

Wasan, M. T. 1969. Stochastic Approximation. Cambridge University Press.

Cited By

Fu MHenderson S(2017)History of seeking better solutions, aka simulation optimizationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242192(1-27)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242192
Ehrlichman SHenderson STew J(2007)Finite-sample performance guarantees for one-dimensional stochastic root findingProceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come10.5555/1351542.1351611(313-321)Online publication date: 9-Dec-2007
https://dl.acm.org/doi/10.5555/1351542.1351611

Recommendations

Retrospective-approximation algorithms for the multidimensional stochastic root-finding problem
Retrospective-approximation algorithms for the multidimensional stochastic root-finding problem

The stochastic root-finding problem (SRFP) is that of solving a nonlinear system of equations using only a simulation that provides estimates of the functions at requested points. Equivalently, SRFPs seek locations where an unknown vector function ...
The stochastic root-finding problem: Overview, solutions, and open questions

The stochastic root-finding problem (SRFP) is that of finding the zero(s) of a vector function, that is, solving a nonlinear system of equations when the function is expressed implicitly through a stochastic simulation. SRFPs are equivalently expressed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '04: Proceedings of the 36th conference on Winter simulation

December 2004

2052 pages

ISBN:0780387864

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Winter Simulation Conference

Publication History

Published: 05 December 2004

Check for updates

Qualifiers

Article

Acceptance Rates

WSC '04 Paper Acceptance Rate 144 of 171 submissions, 84%;

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
92
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fu MHenderson S(2017)History of seeking better solutions, aka simulation optimizationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242192(1-27)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242192
Ehrlichman SHenderson STew J(2007)Finite-sample performance guarantees for one-dimensional stochastic root findingProceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come10.5555/1351542.1351611(313-321)Online publication date: 9-Dec-2007
https://dl.acm.org/doi/10.5555/1351542.1351611

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.

Media

Figures

Other

Tables

View Table of Contents