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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (778 KB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 19 , Issue 2 (March 2009) table of contents

Article No. 5

Year of Publication: 2009

ISSN:1049-3301

Authors

Raghu Pasupathy	Virginia Tech, Blacksburg, VA
Bruce W. Schmeiser	Purdue University, West Lafayette, IN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 145, Citation Count: 0

Additional Information:

appendices and supplements abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1502787.1502788 What is a DOI?

APPENDICES and SUPPLEMENTS

Pasupathy Appendix

Online appendix to retrospective-approximation algorithms for the multidimensional stochastic root-finding problem. The appendix supports the information on article 5.

ABSTRACT

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 attains a given target using only a simulation capable of providing estimates of the function. SRFPs find application in a wide variety of physical settings.

We develop a family of retrospective-approximation (RA) algorithms called Bounding RA that efficiently solves a certain class of multidimensional SRFPs. During each iteration, Bounding RA generates and solves a sample-path problem by identifying a polytope of stipulated diameter, with an image that bounds the given target to within stipulated tolerance. Across iterations, the stipulations become increasingly stringent, resulting in a sequence of shrinking polytopes that approach the correct solution.

Efficiency results from: (i) the RA structure, (ii) the idea of using bounding polytopes to exploit problem structure, and (iii) careful step-size and direction choice during algorithm evolution. Bounding RA has good finite-time performance that is robust with respect to the location of the initial solution, and algorithm parameter values. Empirical tests suggest that Bounding RA outperforms Simultaneous Perturbation Stochastic Approximation (SPSA), which is arguably the best-known algorithm for solving SRFPs.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sirgrún Andradóttir, A projected stochastic approximation algorithm, Proceedings of the 23rd conference on Winter simulation, p.954-957, December 08-11, 1991, Phoenix, Arizona, United States
	2	Sigrún Andradóttir, A scaled stochastic approximation algorithm, Management Science, v.42 n.4, p.475-498, April 1996 [doi>10.1287/mnsc.42.4.475]
	3	Sigrún Andradóttir, A review of simulation optimization techniques, Proceedings of the 30th conference on Winter simulation, p.151-158, December 13-16, 1998, Washington, D.C., United States
	4	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.
	5	Russell R. Barton , John S. Ivey, Jr., Nelder-Mead simplex modifications for simulation optimization, Management Science, v.42 n.7, p.954-973, July 1996 [doi>10.1287/mnsc.42.7.954]
	6	Blum, J. 1954. Multidimensional stochastic approximation. Ann. Math. Statist. 25, 737--744.
	7	Broyden, C. G. 1965. A class of methods for solving nonlinear simultaneous equations. Math. Comput. 19, 577--593.
	8	Chen, H. 1994. Stochastic root finding in system design. Ph.D. thesis, School of Industrial Engineering, Purdue University, West Lafayette, Indiana.
	9	Chen, H. and Schmeiser, B. W. 2001. Stochastic root finding via retrospective approximation. IIE Trans. 33, 259--275.
	10	Fabian, V. 1968. On asymptotic normality in stochastic approximation. Ann. Math. Statist. 39, 1327--1332.
	11	Fu, M. C. 1994. Optimization via simulation: A review. Ann. Oper. Res. 53, 199--247.
	12	Michael C. Fu, Feature Article: Optimization for simulation: Theory vs. Practice, INFORMS Journal on Computing, v.14 n.3, p.192-215, July 2002 [doi>10.1287/ijoc.14.3.192.113]
	13	Fu, M. C. 2006. Gradient estimation. In Simulation, S. G. Henderson and B. L. Nelson, Eds. Handbooks in Operations Research and Management Science. Elsevier, Amsterdam, Chapter 19, 575--616.
	14	Goldsman, D. and Nelson, B. 1998. Comparing systems via simulation. In Handbook of Simulation: Principles, Methodology, Advances, Application, and Practice. John Wiley & Sons, Chapter 8.
	15	Kevin Healy , Lee W. Schruben, Retrospective simulation response optimization, Proceedings of the 23rd conference on Winter simulation, p.901-906, December 08-11, 1991, Phoenix, Arizona, United States
	16	Tito Homem-De-Mello, Variable-sample methods for stochastic optimization, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.2, p.108-133, April 2003 [doi>10.1145/858481.858483]
	17	David G. Humphrey , James R. Wilson, A Revised Simplex Search Procedure for Stochastic Simulation Response Surface Optimization, INFORMS Journal on Computing, v.12 n.4, p.272-283, October 2000 [doi>10.1287/ijoc.12.4.272.11879]
	18	Jacobson, S. H. and Schruben, L. W. 1989. A review of techniques for simulation optimization. Oper. Res. Lett. 8, 1--9.
	19	Kesten, H. 1958. Accelerated stochastic approximation. Ann. Math. Statist. 21, 41--59.
	20	Kushner, H. and Clark, D. 1978. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer, New York.
	21	Kushner, H. J. and Yin, G. G. 2003. Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York.
	22	Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
	23	Nelder, J. A. and Mead, R. 1965. A simplex method for function minimization. Comput. J. 7, 308--313.
	24	James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
	25	Raghu Pasupathy, On choosing parameters in retrospective-approximation algorithms for simulation-optimization, Proceedings of the 38th conference on Winter simulation, December 03-06, 2006, Monterey, California
	26	Raghu Pasupathy , Shane G. Henderson, A testbed of simulation-optimization problems, Proceedings of the 38th conference on Winter simulation, December 03-06, 2006, Monterey, California
	27	Raghubhushan K. Pasupathy , Bruce W. Schmeiser, Retrospective-approximation algorithms for the multidimensional stochastic root-finding problem, Purdue University, West Lafayette, IN, 2005
	28	Erica L. Plambeck , Bor-Ruey Fu , Stephen M. Robinson , Rajan Suri, Sample-path optimization of convex stochastic performance functions, Mathematical Programming: Series A and B, v.75 n.2, p.137-176, Nov. 30, 1996 [doi>10.1007/BF02592150]
	29	Robbins, H. and Monro, S. 1951. A stochastic approximation method. Ann. Math. Statist. 22, 400--407.
	30	Rodriguez, R. N. 1977. A guide to the Burr type XII distributions. Biometrika 64, 1, 129--134.
	31	Rubinstein, R. Y. and Shapiro, A. 1993. Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method. John Wiley & Sons, New York.
	32	Ruszczynski, A. and Shapiro, A., Eds. 2003. Stochastic Programming. Handbook in Operations Research and Management Science. Elsevier, New York.
	33	Safizadeh, M. H. 1990. Optimization in simulation: Current issues and the future outlook. Naval Res. Logist. 37, 807--825.
	34	Alexander Shapiro, Asymptotic analysis of stochastic programs, Annals of Operations Research, v.30 n.1-4, p.169-186, June 1991 [doi>10.1007/BF02204815]
	35	Alexander Shapiro, Simulation based optimization, Proceedings of the 28th conference on Winter simulation, p.332-336, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256644]
	36	Shapiro, A. 2000. Stochastic programming by Monte Carlo simulation methods. Stochastic Programming E-Print Series. http://hera.rz.hu-berlin.de/speps/.
	37	Alexander Shapiro , Tito Homem-de-Mello, On the Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs, SIAM Journal on Optimization, v.11 n.1, p.70-86, 2000 [doi>10.1137/S1052623498349541]
	38	Spall, J. C. 1998. Implementation of the simultaneous perturbation algorithm for stochastic optimization. IEEE Trans. Aerospace Electron. Syst. 34, 817--823.
	39	Spall, J. C. 2000. Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Trans. Autom. Control 45, 1839--1853.
	40	James C. Spall, Introduction to Stochastic Search and Optimization, John Wiley & Sons, Inc., New York, NY, 2003
	41	Swann, W. H. 1972. Direct Search Methods. Numerical Methods for Unconstrained Optimization. Academic Press, London, Chapter 2, 13--28.
	42	Venter, H. J. 1967. An extension of the Robbins-Monro procedure. Ann. Math. Statist. 38, 181--190.
	43	Wasan, M. T. 1969. Stochastic Approximation. Cambridge University Press, Cambridge, UK.
	44	Sidney Yakowitz , Pierre L'Ecuyer , Felisa Vázquez-Abad, Global Stochastic Optimization with Low-Dispersion Point Sets, Operations Research, v.48 n.6, p.939-950, November 2000 [doi>10.1287/opre.48.6.939.12393]