research-article

The stochastic root-finding problem: Overview, solutions, and open questions

Authors:

Raghu Pasupathy,

Sujin KimAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 21, Issue 3

Article No.: 19, Pages 1 - 23

https://doi.org/10.1145/1921598.1921603

Published: 04 February 2011 Publication History

Get Access

Abstract

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 as stochastic fixed-point problems, where the underlying function is expressed implicitly via a noisy simulation. After motivating SRFPs using a few examples, we review available methods to solve such problems on constrained Euclidean spaces. We present the current literature as three broad categories, and detail the basic theoretical results that are currently known in each of the categories. With a view towards helping the practitioner, we discuss specific variations in their implementable form, and provide references to computer code when easily available. Finally, we list a few questions that are worthwhile research pursuits from the standpoint of advancing our knowledge of the theoretical underpinnings and the implementation aspects of solutions to SRFPs.

Supplementary Material

Pasupathy Appendix (a19-pasupathy-apndx.pdf)

Online appendix to the stochastic root-finding problem overview, solutions, and open questions on article 19.

Download
88.73 KB

References

[1]

Abbasbandy, S. 2003. Improving the Newton--Raphson method for nonlinear equations by modified Adomian decomposition method. Appl. Math. Comput. 145, 887--893.

Digital Library

Google Scholar

[2]

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

Crossref

Google Scholar

[3]

Atlason, J., Epelman, M. A., and Henderson, S. G. 2005. Optimizing call center staffing using simulation and analytic center cutting plane methods. Manage. Sci. To appear.

Digital Library

Google Scholar

[4]

Bartle, R. G. 1976. The Elements of Real Analysis. Wiley, New York.

Google Scholar

[5]

Barton, R. R. and Meckesheimer, M. 2006. Metamodel-based simulation optimization. In Simulation, S.G. Henderson and B.L. Nelson Eds. Elsevier, Amsterdam, 535--574.

Google Scholar

[6]

Bayraksan, G. and Morton, D. P. 2009. A sequential sampling procedure for stochastic programming. Oper. Res. To appear.

Digital Library

Google Scholar

[7]

Ben-Akiva, M. and Lerman, S. R. 1985. Discrete Choice Analysis: Theory and Application to Travel Demand. The MIT Press, Cambridge, MA.

Google Scholar

[8]

Bhatnagar, S. 2005. Adaptive three-timescale stochastic approximation. ACM Trans. Model. Comput. Simul. 15, 1, 74--107.

Digital Library

Google Scholar

[9]

Blum, J. 1954a. Approximation methods which converge with probability one. Ann. Math. Stat. 25, 2, 382--386.

Crossref

Google Scholar

[10]

Blum, J. 1954b. Multidimensional stochastic approximation. Ann. Math. Stat. 25, 4, 737--744.

Crossref

Google Scholar

[11]

Bratley, P., Fox, B. L., and Schrage, L. E. 1987. A Guide to Simulation. Springer, Berlin.

Digital Library

Google Scholar

[12]

Broadie, M., Cicek, D. M., and Zeevi, A. 2009. An adaptive multidimensional version of the Kiefer-Wolfowitz stochastic approximation algorithm. In Proceedings of the Winter Simulation Conference. M. D. Rossetti et al. Eds. IEEE, Los Alamitos, CA, 601--612.

Digital Library

Google Scholar

[13]

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

Crossref

Google Scholar

[14]

Chow, Y. S. and Robbins, H. E. 1965. On the asymptotic theory of fixed-width confidence intervals for the mean. Ann. Math. Stat. 36, 457--462.

Crossref

Google Scholar

[15]

Chung, K. L. 1954. On a stochastic approximation method. Ann. Math. Stat. 25, 463--483.

Crossref

Google Scholar

[16]

Dunkel, J. and Weber, S. 2009. Stochastic root finding and efficient estimation of convex risk measures. Oper. Res. To appear.

Digital Library

Google Scholar

[17]

Fabian, V. 1968. On asymptotic normality in stochastic approximation. Ann. Math. Stat. 39, 1327--1332.

Crossref

Google Scholar

[18]

Frees, E. W. and Ruppert, D. 1990. Estimation following a Robbins--Monro designed experiment. J. Amer. Stat. Asoc. 85, 1123--1129.

Crossref

Google Scholar

[19]

Fu, M. C. 1994. Optimization via simulation: A review. Ann. Oper. Res. 53, 199--247.

Crossref

Google Scholar

[20]

Giesecke, K., Schmidt, T., and Weber, S. 2008. Measuring the risk of large losses. J. Investment Manage. 6, 4, 1--15.

Google Scholar

[21]

Glasserman, P. 1991. Gradient Estimation Via Perturbation Analysis. Kluwer, Amsterdam.

Google Scholar

[22]

Healy, K. and Schruben, L. W. 1991. Retrospective simulation response optimization. In Proceedings of the Winter Simulation Conference. B. L. Nelson et al. Eds. IEEE, Los Alamitos, CA, 954--957.

Digital Library

Google Scholar

[23]

Henderson, S. G. and Nelson, B. L. (eds.). 2006. Handbooks in Operations Research and Management Science: Simulation. Vol. 13. Elsevier, Amsterdam.

Google Scholar

[24]

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

Crossref

Google Scholar

[25]

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

Digital Library

Google Scholar

[26]

Homem-de-Mello, T. 2003. Variable-sample methods for stochastic optimization. ACM Trans. Model. Comput. Simul. 13, 108--133.

Digital Library

Google Scholar

[27]

Householder, A. S. 1970. The Numerical Treatment of a Single Nonlinear Equation. McGraw-Hill, New York.

Google Scholar

[28]

Hsieh, M. and Glynn, P. W. 2002. Confidence regions for stochastic approximation algorithms. In Proceedings of the Winter Simulation Conference. E. Yucesan et al. Eds. IEEE, Los Alamitos, CA, 370--375.

Digital Library

Google Scholar

[29]

Joseph, V. R., Tian, Y., and Wu, C. F J. 2007. Adaptive designs for stochastic root-finding. Statistica Sinica 17, 1549--1565.

Google Scholar

[30]

Kelly, C. T. 1995. Iterative Methods for Linear and Nonlinear Equations. SIAM, Philadelphia, PA.

Google Scholar

[31]

Kelly, C. T. 2006. Solving Nonlinear Equations with Newton's Method. SIAM, Philadelphia, PA.

Google Scholar

[32]

Kim, S. and Henderson, S. G. 2008. The mathematics of continuous-variable simulation optimization. In Proceedings of the Winter Simulation Conference. S. J. Mason et al. Eds. IEEE, Los Alamitos, CA, 159--167.

Digital Library

Google Scholar

[33]

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

Digital Library

Google Scholar

[34]

Kushner, H. J. and Yin, G. G. 2003. Stochastic Approximation and Recursive Algorithms and Applications. Springer, Berlin.

Google Scholar

[35]

Lai, T. L. 2003. Invited paper: Stochastic approximation. Ann. Stat. 31, 2, 391--406.

Crossref

Google Scholar

[36]

Law, A. M. 2007. Simulation Modeling and Analysis. McGraw-Hill, New York.

Google Scholar

[37]

Lawphongpanich, S., Hearn, D. W., and Smith, M. J. (eds.). 2006. Applied Optimization: Mathematical and Computational Models for Congestion Charging, Vol. 101. Springer, Berlin.

Google Scholar

[38]

Ljung, L. 1977a. Analysis of recursive stochastic algorithms. IEEE Trans. Autom. Control AC-22, 551--575.

Crossref

Google Scholar

[39]

Ljung, L. 1977b. On positive real transfer functions and the convergence of some recursive schemes. IEEE Trans. Autom. Control AC-22, 539--551.

Crossref

Google Scholar

[40]

Luedtke, J. and Ahmed, S. 2008. A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. To appear.

Digital Library

Google Scholar

[41]

Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. 2009. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 4.

Digital Library

Google Scholar

[42]

Nevel'son, M. B. and Khas'minskii, R. Z. 1973. Stochastic Approximation and Recursive Estimation. American Mathematical Society, Providence, RI.

Google Scholar

[43]

Noor, K. I. and Noor, M. A. 2007. Iterative methods with fourth-order convergence for nonlinear equations. Appl. Math. Computation 189, 1, 221--227.

Crossref

Google Scholar

[44]

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

Google Scholar

[45]

Pasupathy, R. 2010. On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization. Oper. Res. 58, 4, 889--901.

Digital Library

Google Scholar

[46]

Pasupathy, R. and Schmeiser, B. W. 2009. Retrospective-approximation algorithms for multidimensional stochastic root-finding problems. ACM Trans. Model. Comput. Simul. 19, 2, 5:1--5:36.

Digital Library

Google Scholar

[47]

Pflug, G. C. 1996. Optimization of Stochastic Models: The Interface Between Simulation and Optimization. Kluwer, Amsterdam.

Google Scholar

[48]

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

Digital Library

Google Scholar

[49]

Polyak, B. T. and Juditsky, A. B. 1992. Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30, 4, 838--855.

Digital Library

Google Scholar

[50]

Rheinboldt, W. C. 1987. Methods for Solving Systems of Nonlinear Equations in Several Variables. Society for Industrial Mathematics.

Digital Library

Google Scholar

[51]

Robbins, H. and Monro, S. 1951. A stochastic approximation method. Ann. Math. Stat. 22, 400--407.

Crossref

Google Scholar

[52]

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

Google Scholar

[53]

Ruppert, D. 1985. A Newton--Raphson version of the multivariate Robbins--Monro procedure. Ann. Stat. 13, 236--245.

Crossref

Google Scholar

[54]

Ruppert, D. 1991. Stochastic approximation. In Handbook in Sequential Analysis. Dekker, New York, 503--529.

Google Scholar

[55]

Sacks, J. 1958. Asymptotic distribution of stochastic approximation procedure. Ann. Math. Stat. 29, 373--405.

Crossref

Google Scholar

[56]

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

Digital Library

Google Scholar

[57]

Shapiro, A. 2004. Monte Carlo sampling methods. In Stochastic Programming, A. Ruszczynski and Shapiro Eds. Elsevier, Amsterdam, 353--426.

Google Scholar

[58]

Sheffi, Y. 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice Hall, New York.

Google Scholar

[59]

Spall, J. C. 1998. Implementation of the simultaneous perturbation algorithm for stochastic optimization. IEEE Trans. Aerospace Electron. Syst. 34, 817--823.

Crossref

Google Scholar

[60]

Spall, J. C. 2000. Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Trans. Autom. Control 45, 1839--1853.

Crossref

Google Scholar

[61]

Spall, J. C. 2003. Introduction to Stochastic Search and Optimization. Wiley, New York.

Digital Library

Google Scholar

[62]

Stewart, G. W. 1973. Introduction to Matrix Computations. Academic Press, New York.

Google Scholar

[63]

Todd, M. J. 1976. The Computation of Fixed Points and Applications. Springer, Berlin.

Google Scholar

[64]

Traub, J. F. 1964. Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs, NJ.

Google Scholar

[65]

Venter, J. H. 1967. An extension of the Robbins--Monro procedure. Ann. Stat. 38, 181--190.

Crossref

Google Scholar

[66]

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

Digital Library

Google Scholar

[67]

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

Google Scholar

[68]

Weerakoon, S. and Fernando, T. G. I. 2000. A variant of Newton's method with accelerated third-order convergence. Appl. Math. Lett. 13, 87--93.

Crossref

Google Scholar

[69]

Wei, C. Z. 1987. Multivariate adaptive stochastic approximation. Ann. Stat. 15, 1115--1130.

Crossref

Google Scholar

[70]

Wu, C. F. J. 1985. Efficient sequential designs with binary data. Ann. Stat. 13, 1498--1508.

Google Scholar

[71]

Wu, C. F. J. 1986. Maximum likelihood recursion and stochastic approximation in sequential designs. In Statistical Procedures and Related Topics, J.V. Ryzin Ed. IMS, Hayward, CA, 298--313.

Google Scholar

[72]

Yakowitz, S., L'Ecuyer, P., and Vazquez-Abad, F. 2000. Global stochastic optimization with low-dispersion point sets. Oper. Res. 48, 939--950.

Digital Library

Google Scholar

[73]

Ying, Z. and Wu, C. F. J. 1997. An asymptotic theory of sequential designs based on maximum likelihood recursions. Stat. Sinica 7, 75--918.

Google Scholar

[74]

Young, D. M. 1971. Iterative Solution of Large Linear Systems. Academic Press, New York.

Google Scholar

Cited By

View all

Lei JShanbhag U(2024)Variance-Reduced Accelerated First-Order Methods: Central Limit Theorems and Confidence StatementsMathematics of Operations Research10.1287/moor.2021.0068Online publication date: 4-Jun-2024
https://doi.org/10.1287/moor.2021.0068
Lam HZhang XZhang X(2023)Enhanced Balancing of Bias-Variance Tradeoff in Stochastic Estimation: A Minimax PerspectiveOperations Research10.1287/opre.2022.231971:6(2352-2373)Online publication date: Nov-2023
https://doi.org/10.1287/opre.2022.2319
Zimmerman SRutherford Avan der Waall ANorena MDodek P(2023)A queuing model for ventilator capacity management during the COVID-19 pandemicHealth Care Management Science10.1007/s10729-023-09632-926:2(200-216)Online publication date: 22-May-2023
https://doi.org/10.1007/s10729-023-09632-9
Show More Cited By

Index Terms

The stochastic root-finding problem: Overview, solutions, and open questions
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation theory
2. Mathematics of computing
  1. Mathematical analysis
    1. Nonlinear equations
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

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 ...
Approximate stochastic annealing for online control of infinite horizon Markov decision processes

We present an online simulation-based algorithm called Approximate Stochastic Annealing (ASA) for solving infinite-horizon finite state-action space Markov decision processes (MDPs). The algorithm estimates the optimal policy by sampling at each ...
On Boundedness of Q-Learning Iterates for Stochastic Shortest Path Problems

We consider a totally asynchronous stochastic approximation algorithm, Q-learning, for solving finite space stochastic shortest path SSP problems, which are undiscounted, total cost Markov decision processes with an absorbing and cost-free state. For ...

Reviews

Reviewer: Grigore Albeanu

Both application- and theory-oriented scientists are familiar with the root-finding problem. The scientific literature is not only rich in original proposals and tutorials, but also in excellent books-Pasupathy and Kim mention some of them. This valuable overview of the stochastic root-finding problem consists of six sections and an electronic appendix (http://portal.acm.org/citation.cfm__?__doid=1921598.1921603). After a short introduction (Section 1), Section 2 offers some examples that motivate the request for efficient root-finding procedures in a stochastic framework, including stochastic optimization problem solving. Section 3 presents notations and terminology. In Section 4, the authors formulate the stochastic root-finding problem. Section 5 describes methods for solving the problem, giving only stochastic approximation and sample-path methods in detail, including basic convergence theorems, results on convergence rates and sample size, algorithms, implementation details, and comments on their performance. The online appendix describes a third type: parametric/semi-parametric methods. Contributions from many researchers, as well as recent developments by Pasupathy, represent the core of this section. Finally, in Section 6, readers will discover some ideas for future research. (The electronic appendix also includes in-depth discussions on research.) Readers who are unfamiliar with the stochastic root-finding problem should pay attention to some abbreviations (SPSA and SOP) that the paper uses without explanation, an error in relation (7), and the use of the SP abbreviation in two different contexts (in Sections 5.1 and 5.2). The references are adequate-many of them are on recent developments that can increase the performance of the existing algorithms. Unfortunately, the paper neglects to cite ten references and the introduction does not clearly state the structure of the online appendix. This paper is a valuable resource for online readers. It will be especially useful to PhD students and various researchers in modeling and computer simulation. Online Computing Reviews Service

Reviewer: Alexander Kreinin

This paper describes the general stochastic approximation problem: find the solutions of the nonlinear equations g ( x )=0, x ? D , where the function g ( x ) is computed with some random error. In this case, instead of computing g ( x ), one actually finds G n ( x ) = g ( x ) + xi n , where ? m forms a sequence of independent random vectors having a joint normal distribution. We can describe the simplest iterations by the equation X n +1 = X n a n G ( X n ), where the sequence a n satisfies certain conditions providing convergence of the sequence X n to the solution x *. The modern approach to this problem is based on the theory of martingales. Theorems 5.1 through 5.3 discuss the latest results on convergence, including the convergence rate of the iteration process. The next section discusses the sample path method. The idea of this method is to use an approximate problem with the function G ( x ) approximating g ( x ). The approximating function is usually an estimator of g ( x ). Theorems 5.5 through 5.7 discuss corresponding convergence results. This section also addresses implementation and performance issues. I recommend this paper to specialists who are interested in the application of stochastic optimization methods. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 21, Issue 3

March 2011

141 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/1921598

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 February 2011

Accepted: 01 September 2010

Revised: 01 August 2010

Received: 01 September 2009

Published in TOMACS Volume 21, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
Total Citations
View Citations
962
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)4

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lei JShanbhag U(2024)Variance-Reduced Accelerated First-Order Methods: Central Limit Theorems and Confidence StatementsMathematics of Operations Research10.1287/moor.2021.0068Online publication date: 4-Jun-2024
https://doi.org/10.1287/moor.2021.0068
Lam HZhang XZhang X(2023)Enhanced Balancing of Bias-Variance Tradeoff in Stochastic Estimation: A Minimax PerspectiveOperations Research10.1287/opre.2022.231971:6(2352-2373)Online publication date: Nov-2023
https://doi.org/10.1287/opre.2022.2319
Zimmerman SRutherford Avan der Waall ANorena MDodek P(2023)A queuing model for ventilator capacity management during the COVID-19 pandemicHealth Care Management Science10.1007/s10729-023-09632-926:2(200-216)Online publication date: 22-May-2023
https://doi.org/10.1007/s10729-023-09632-9
Hu ZHong L(2022)Robust Simulation with Likelihood-Ratio Constrained Input UncertaintyINFORMS Journal on Computing10.1287/ijoc.2022.116934:4(2350-2367)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1169
Glimsdal SGranmo O(2021)Thompson sampling guided stochastic searching on the line for deceptive environments with applications to root-finding problemsThe Journal of Machine Learning Research10.5555/3322706.336199320:1(1910-1933)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3361993
Goda TYamada Y(2021)Probabilistic threshold analysis by pairwise stochastic approximation for decision-making under uncertaintyScientific Reports10.1038/s41598-021-99089-z11:1Online publication date: 4-Oct-2021
https://doi.org/10.1038/s41598-021-99089-z
Salgia SZhao QVakili SDaumé HSingh A(2020)Stochastic coordinate minimization with progressive precision for stochastic convex optimizationProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525719(8427-8437)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525719
Ryzhov IZhang QChen Y(2020)Advanced statistical methodsProceedings of the Winter Simulation Conference10.5555/3466184.3466186(1-15)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466186
Chen YRyzhov I(2020)Technical Note—Consistency Analysis of Sequential Learning Under Approximate Bayesian InferenceOperations Research10.1287/opre.2019.185068:1(295-307)Online publication date: 2-Jan-2020
https://dl.acm.org/doi/10.1287/opre.2019.1850
Tunuguntla SHoban P(2020)A Near-Optimal Bidding Strategy for Real-Time Display Advertising AuctionsJournal of Marketing Research10.1177/002224372096854758:1(1-21)Online publication date: 3-Dec-2020
https://doi.org/10.1177/0022243720968547
Show More Cited By

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

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

Approximate stochastic annealing for online control of infinite horizon Markov decision processes

On Boundedness of Q-Learning Iterates for Stochastic Shortest Path Problems

Reviews

Access critical reviews of Computing literature here