Root Finding via DARTS: Dynamic Adaptive Random Target Shooting. Pasupathy, R. & Schmeiser, B. W. In B.~Johansson, S.~Jain, J.~Montoya-Torres, J.~Hugan, & E.~Yücesan, editors, Proceedings of the 2010 Winter Simulation Conference, pages 1255–1262, Piscataway, NJ, 2010. Institute of Electrical and Electronics Engineers, Inc..
Root Finding via DARTS: Dynamic Adaptive Random Target Shooting [pdf]Paper  abstract   bibtex   
Consider multi-dimensional root finding when the equations are available only implicitly via a Monte Carlo simulation oracle that for any solution returns a vector of point estimates. We develop DARTS, a stochastic-approximation algorithm that makes quasi-Newton moves to a new solution whenever the current sample size is large compared to the estimated quality of the current solution and estimated sampling error. We show that DARTS converges in a certain precise sense, and discuss reasons to expect substantial computational efficiencies over traditional stochastic approximation variations.

Downloads: 0