Global random optimization by simultaneous perturbation stochastic approximation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Global random optimization by simultaneous perturbation stochastic approximation

Full text

Pdf (170 KB)

Source

Winter Simulation Conference archive
Proceedings of the 33nd conference on Winter simulation table of contents

Arlington, Virginia

SESSION: Analysis methodology table of contents

Pages: 307 - 312

Year of Publication: 2001

ISBN:0-7803-7309-X

Authors

John L. Maryak	The Johns Hopkins University, Laurel, MD
Daniel C. Chin	The Johns Hopkins University, Laurel, MD

Sponsors

INFORMS/CS : Institute for Operations Research and the Management Sciences/College on Simulation
IEEE/SMCS : Institute of Electrical and Electronics Engineers/Systems, Man, and Cybernetics Society
NIST : National Institute of Standards and Technology
ACM: Association for Computing Machinery
SCS : The Society for Computer Simulation International
SIGSIM: ACM Special Interest Group on Simulation and Modeling
IIE : Institute of Industrial Engineers
IEEE/CS : Institute of Electrical and Electronics Engineers/Computer Society
ASA : American Statistical Association

Publisher

IEEE Computer Society Washington, DC, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 29, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

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

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	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]