The Number of Random Restarts Required to Identify all Solutions to a Nonlinear System: Applications to Global Stochastic Optimization

摘要

We consider the question of identifying the set of all solutions to a system of nonlinear equations, when the functions involved in the system can only be observed through a stochastic simulation. Such problems frequently arise as first order necessary conditions in global simulation optimization problems. A convenient method of "solving" such problems involves generating (using a fixed sample) a sample-path approximation of the functions involved, and then executing a convergent root-finding algorithm with several random restarts. The various solutions obtained thus are then gathered to form the estimator of the true set. We investigate the quality of the returned set in terms of the expected Hausdorff distance between the returned and true sets. Our message is that a certain simple logarithmic relationship between the sample size and the number of random restarts ensures maximal efficiency.