Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences

ABSTRACT

Simultaneous perturbation stochastic approximation (SPSA) algorithms have been found to be very effective for high-dimensional simulation optimization problems. The main idea is to estimate the gradient using simulation output performance measures at only two settings of the N-dimensional parameter vector being optimized rather than at the N + 1 or 2N settings required by the usual one-sided or symmetric difference estimates, respectively. The two settings of the parameter vector are obtained by simultaneously changing the parameter vector in each component direction using random perturbations. In this article, in order to enhance the convergence of these algorithms, we consider deterministic sequences of perturbations for two-timescale SPSA algorithms. Two constructions for the perturbation sequences are considered: complete lexicographical cycles and much shorter sequences based on normalized Hadamard matrices. Recently, one-simulation versions of SPSA have been proposed, and we also investigate these algorithms using deterministic sequences. Rigorous convergence analyses for all proposed algorithms are presented in detail. Extensive numerical experiments on a network of M/G/1 queues with feedback indicate that the deterministic sequence SPSA algorithms perform significantly better than the corresponding randomized algorithms.

REFERENCES

• 1: Bhatnagar, S. 1997. Multiscale stochastic approximation algorithms with applications to ABR service in ATM networks. Ph.D. dissertation, Department of Electrical Engineering, Indian Institute of Science, Bangalore, India.
• 2: Bhatnagar, S. and Borkar, V. S. 1997. Multiscale stochastic approximation for parametric optimization of hidden Markov models. Prob. Eng. Inf. Sci. 11, 509--522.
• 3: Bhatnagar, S. and Borkar, V. S. 1998. A two timescale stochastic approximation scheme for simulation based parametric optimization. Prob. Eng. and Inf. Sci. 12, 519--531.
• 4: Bhatnagar, S., Fu, M. C., Marcus, S. I., and Bhatnagar, S. 2001a. Two timescale algorithms for simulation optimization of hidden Markov models. IIE Trans. 33, 3, 245--258.
• 5: Shalabh Bhatnagar , Michael C. Fu , Steven I. Marcus , Pedram J. Fard, Optimal structured feedback policies for ABR flow control using two-timescale SPSA, IEEE/ACM Transactions on Networking (TON), v.9 n.4, p.479-491, August 2001 [doi>10.1109/90.944345]
• 6: Vivek S. Borkar, Stochastic approximation with two time scales, Systems & Control Letters, v.29 n.5, p.291-294, Feb. 1997 [doi>10.1016/S0167-6911(97)90015-3]
• 7: Chen, H. F., Duncan, T. E., and Pasik-Duncan, B. 1999. A Kiefer-Wolfowitz algorithm with randomized differences. IEEE Trans. Auto. Cont. 44, 3, 442--453.
• 8: Edwin K. P. Chong , Peter J. Ramadge, Optimization of queues using an infinitesimal perturbation analysis-based stochastic algorithm with general update times, SIAM Journal on Control and Optimization, v.31 n.3, p.698-732, May 1993 [doi>10.1137/0331032]
• 9: Chong, E. K. P. and Ramadge, P. J. 1994. Stochastic optimization of regenerative systems using infinitesimal perturbation analysis. IEEE Trans. Auto. Cont. 39, 7, 1400--1410.
• 10: M. C. Fu, Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation, Journal of Optimization Theory and Applications, v.65 n.1, p.149-160, Apr. 1990 [doi>10.1007/BF00941166]
• 11: Fu, M. C. and Hill, S. D. 1997. Optimization of discrete event systems via simultaneous perturbation stochastic approximation. IIE Trans. 29, 3, 233--243.
• 12: Gerencsér, L. 1999. Rate of convergence of moments for a simultaneous perturbation stochastic approximation method for function minimization. IEEE Trans. Auto. Cont. 44, 894--906.
• 13: Gerencsér, L., Hill, S. D., and Vágó, Z. 1999. Optimization over discrete sets via SPSA. In Proceedings of the IEEE Conference on Decision and Control (Phoenix, Az.). IEEE Computer Society Press, Los Alamitos Calif., pp. 1791--1795.
• 14: Hadamard, J. 1893. Résolution d'une question rélative aux determinants. Bull. des Sciences Mathematiques 17, 240--246.
• 15: Ho, Y. C. and Cao, X. R. 1991. Perturbation Analysis of Discrete Event Dynamical Systems. Kluwer, Boston.
• 16: Nathan L. Kleinman , James C. Spall , Daniel Q. Naiman, Simulation-Based Optimization with Stochastic Approximation Using Common Random Numbers, Management Science, v.45 n.11, p.1570-1578, November 1999 [doi>10.1287/mnsc.45.11.1570]
• 17: Kushner, H. J. and Clark, D. S. 1978. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer Verlag, New York.
• 18: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 19: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 20: Niederreiter, N. 1995. New developments in uniform pseudorandom number and vector generation. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, (H. Niederreiter and P. J-S. Shiue, Eds.). Lecture Notes in Statistics, Springer, New York.
• 21: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 22: Sandilya, S. and Kulkarni, S. R. 1997. Deterministic sufficient conditions for convergence of simultaneous perturbation stochastic approximation algorithms. In Proceedings of the 9th INFORMS Applied Probability Conference (Boston, Mass.).
• 23: Seberry, J. and Yamada, M. 1992. Hadamard matrices, sequences, and block designs. In Contemporary Design Theory---A Collection of Surveys, D. J. Stinson and J. Dintiz, Eds. Wiley, New York, pp. 431--560.
• 24: Spall, J. C. 1992. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. Auto. Cont. 37, 3, 332--341.
• 25: 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]
• 26: Spall, J. C. and Cristion, J. A. 1998. Model-free control of nonlinear stochastic systems with discrete-time measurements. IEEE Trans. Auto. Cont. 43, 9, 1198--1210.
• 27: Wang, I.-J. and Chong, E. K. P. 1998. A deterministic analysis of stochastic approximation with randomized directions. IEEE Trans. Auto. Cont. 43, 12, 1745--1749.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.0 General
      I.6.1 Simulation Theory

General Terms:
Algorithms, Performance, Theory

Keywords:
Hadamard matrices, SPSA, Simulation optimization, deterministic perturbations, stochastic approximation, two-timescale algorithms