Global Random Optimization by Simultaneous Perturbation Stochastic Approximation

We examine the theoretical and numerical global convergence properties of a certain ldquogradient freerdquo stochastic approximation algorithm called the ldquosimultaneous perturbation stochastic approximation (SPSA)rdquo that has performed well in complex optimization problems. We establish two theorems on the global convergence of SPSA, the first involving the well-known method of injected noise. The second theorem establishes conditions under which ldquobasicrdquo SPSA without injected noise can achieve convergence in probability to a global optimum, a result with important practical benefits.