Optimization via simulation: randomized-direction stochastic approximation algorithms using deterministic sequences

ABSTRACT

We study the convergence and asymptotic normality of a generalized form of stochastic approximation algorithm with deterministic perturbation sequences. Both one-simulation and two-simulation methods are considered. Assuming a special structure of deterministic sequence, we establish sufficient condition on the noise sequence for a.s. convergence of the algorithm. Construction of such a special structure of deterministic sequence follows the discussion of asymptotic normality. Finally we discuss ideas on further research in analysis and design of the deterministic perturbation sequences.

REFERENCES

• 1: Shalabh Bhatnagar , Michael C. Fu , Steven I. Marcus , I-Jeng Wang, Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.2, p.180-209, April 2003 [doi>10.1145/858481.858486]
• 2: Blum, J. R. 1954. Multidimensional stochastic approximation methods. Ann. Math. Stats. 25: 737--744.
• 3: Fabian, V. 1968. On asymptotic normality in stochastic approximation. The Annals of Mathematical Statistics 39(4): 1327--1332.
• 4: Hedayat, A. S., N. J. A. Sloane, and J. Stufken. 1999. Orthogonal Arrays: Theory and Applications, Springer Verlag, New York, NY.
• 5: Kushner, H. J. and D. S. Clark. 1978 Stochastic Approximation Methods for Constrained and Unconstrained Systems, Springer Verlag, New York.
• 6: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 7: Sandilya, S., and S. R. Kulkarni. 1997. Deterministic sufficient conditions for convergence of simultaneous perturbation stochastic approximation algorithms. The 9th INFORMS Applied Probability Conference, Boston, MA.
• 8: Seberry, J. and M. Yamada. 1992. Hadamard matrices, sequences, and block designs. In Contemporary Design Theory - A Collection of Surveys (eds. D. J. Stinson and J. Dintiz), pp. 431--560, John Wiley and Sons.
• 9: Spall, J. C. 1992. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control, 37(3):332--341.
• 10: James C. Spall, A one-measurement form of simultaneous perturbation stochastic approximation, Automatica (Journal of IFAC), v.33 n.1, p.109-112, Jan. 1997 [doi>10.1016/S0005-1098(96)00149-5]
• 11: 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]
• 12: Wang, I-J., E. K. P. Chong, and S. R. Kulkarni. 1996. Equivalent necessary and sufficient conditions on noise sequences for stochastic approximation algorithms. Advances in Applied Probability, 28:784--801.
• 13: Wang, I-J., E. K. P. Chong, and S. R. Kulkarni. 1997. Weighted averaging and stochastic approximation. Mathematics of Control, Signals, and Systems, 10(1): 41--60.
• 14: Wang, I-J. and E.K.P. Chong. 1998. A deterministic analysis of stochastic approximation with randomized directions. IEEE Transactions on Automatic Control, 43(12):1745--1749.