Global random optimization by simultaneous perturbation stochastic approximation

ABSTRACT

A desire with iterative optimization techniques is that the algorithm reach the global optimum rather than get stranded at a local optimum value. Here, we examine the global convergence properties of a "gradient free" stochastic approximation algorithm called "SPSA," that has performed well in complex optimization problems. We establish two theorems on the global convergence of SPSA. The first provides conditions under which SPSA will converge in probability to a global optimum using the well-known method of injected noise. In the second theorem, we show that, under different conditions, "basic" SPSA without injected noise can achieve convergence in probability to a global optimum. This latter result can have important benefits in the setup (tuning) and performance of the algorithm. The discussion is supported by numerical studies showing favorable comparisons of SPSA to simulated annealing and genetic algorithms.

REFERENCES

• 1: Mahmoud H. Alrefaei , Sigrún Andradóttir, A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic Optimization, Management Science, v.45 n.5, p.748-764, May 1999 [doi>10.1287/mnsc.45.5.748]
• 2: Tzuu-Shuh Chiang , Chii-Ruey Hwang, Diffusion for global optimization in R, SIAM Journal on Control and Optimization, v.25 n.3, p.737-753, May 1, 1987 [doi>10.1137/0325042]
• 3: Chin, D. C. (1997), "Comparative Study of Stochastic Algorithms for System Optimization Based on Gradient Approximations," IEEE Trans. Systems, Man, and Cybernetics - Part B: Cybernetics,27, pp. 244-249.
• 4: Chin, D. C. (1994), "A More Efficient Global Optimization Algorithm Based on Styblinski and Tang," Neural Networks,7, pp. 573-574.
• 5: Dippon, J. and Fabian, V. (1994), "Stochastic Approximation of Global Minimum Points," J. Statistical Planning and Inference,41, pp. 327-347.
• 6: J. Dippon , J. Renz, Weighted Means in Stochastic Approximation of Minima, SIAM Journal on Control and Optimization, v.35 n.5, p.1811-1827, Sept. 1997 [doi>10.1137/S0363012995283789]
• 7: Haitao Fang , Guanglu Gong , Minping Qian, Annealing of Iterative Stochastic Schemes, SIAM Journal on Control and Optimization, v.35 n.6, p.1886-1907, Nov. 1997 [doi>10.1137/S0363012995293670]
• 8: Saul B. Gelfand , Sanjoy K. Mitter, Recursive stochastic algorithms for global optimization in Rd, SIAM Journal on Control and Optimization, v.29 n.5, p.999-1018, Sept. 1991 [doi>10.1137/0329055]
• 9: Saul B. Gelfand , Sanjoy K. Mitter, Metropolis-type annealing algorithms for global optimization in R^d , SIAM Journal on Control and Optimization, v.31 n.1, p.111-131, Jan. 1993 [doi>10.1137/0331009]
• 10: Geman S. and Geman, D. (1984), "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images, IEEE Trans. Pattern Analysis and Machine Intelligence,PAMI-6, pp. 721-741.
• 11: Haataja, J. (1999), "Using Genetic Algorithms for Optimization: Technology Transfer in Action," Chapter 1, pp. 3 - 22, in Evolutionary Algorithms in Engineering and Computer Science, Edited by K. Miettinen, M. M. Makela, P. Neittaanmaki, and J. Periaux, Wiley, Chichester.
• 12: Bruce Hajek, Cooling schedules for optimal annealing, Mathematics of Operations Research, v.13 n.2, p.311-329, May 1988 [doi>10.1287/moor.13.2.311]
• 13: Kushner, H. J. and Yin, G. G. (1997), Stochastic Approximation Algorithms and Applications, Springer, New York.
• 14: H. J. Kushner, Asymptotic global behavior for stochastic approximation and diffusions with slowly decreasing noise effects: Global minimization via Monte Carlo, SIAM Journal on Applied Mathematics, v.47 n.1, p.169-185, Feb. 1987 [doi>10.1137/0147010]
• 15: Maryak, J. L. and Chin, D. C. (1999), "Efficient Global Optimization Using SPSA," Proc. Amer. Control Conf., San Diego, June 2-4, pp. 890-894.
• 16: Maryak, J. L. and Chin, D. C. (2001), "Global Random Optimization by Simultaneous Perturbation Stochastic Approximation," Proc. Amer. Control Conf., Arlington, VA, June 25-27, pp. 756-762.
• 17: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 18: Spall, J. C. (2000), "Adaptive Stochastic Approximation by the Simultaneous Perturbation Method," IEEE Trans. Automat. Control,45, pp. 1839-1853.
• 19: Spall, J. C. (1998), "Implementation of the Simultaneous Perturbation Algorithm for Stochastic Optimization," IEEE Trans. Aerospace and Electronic Systems,34, pp. 817-823.
• 20: Spall, J. C. (1992), "Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation," IEEE Trans. Automat. Control,37, pp. 332-341.
• 21: M. A. Styblinski , T. -S. Tang, Experiments in nonconvex optimization: stochastic approximation with function smoothing and simulated annealing, Neural Networks, v.3 n.4, p.467-483, 1990 [doi>10.1016/0893-6080(90)90029-K]
• 22: Sid Yakowitz, A globally convergent stochastic approximation, SIAM Journal on Control and Optimization, v.31 n.1, p.30-40, Jan. 1993 [doi>10.1137/0331003]
• 23: 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]
• 24: G. Yin, Rates of Convergence for a Class of Global Stochastic Optimization Algorithms, SIAM Journal on Optimization, v.10 n.1, p.99-120, 1999 [doi>10.1137/S1052623497319225]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Performance, Theory