Shalabh Bhatnagar
Abstract
We develop in this article, four adaptive three-timescale stochastic approximation algorithms for simulation optimization that estimate both the gradient and Hessian of average cost at each update epoch. These algorithms use four, three, two, and one simulation(s), respectively, and update the values of the decision variable and Hessian matrix components simultaneously, with estimates based on the simultaneous perturbation methodology. Our algorithms use coupled stochastic recursions that proceed using three different timescales or step-size schedules. We present a detailed convergence analysis of the algorithms and show numerical experiments using all the developed algorithms on a two-node network of M/G/1 queues with feedback for a 50-dimensional parameter vector. We provide comparisons of the performance of these algorithms with two recently developed two-timescale steepest descent simultaneous perturbation analogs that use randomized and deterministic perturbation sequences, respectively. We also present experiments to explore the sensitivity of the algorithms to their associated parameters. The algorithms that use four and three simulations, respectively, perform significantly better than the rest of the algorithms.
- Andradóttir, S. 1996. Optimization of the transient and steady-state behavior of discrete event systems. Manag. Sci. 42, 5, 717--737. Google Scholar
- Bertsekas, D. P. 1999. Nonlinear Programming. Athena Scientific, Belmont.Google Scholar
- Bertsekas, D. P. and Tsitsiklis, J. N. 1989. Parallel and Distributed Computation. Prentice Hall, New Jersey. Google Scholar
- Bhatnagar, S. 1997. Multiscale Stochastic Approximation Algorithms with Applications to ABR Service in ATM Networks. Ph. D. thesis, Department of Electrical Engineering, Indian Institute of Science, Bangalore, India.Google Scholar
- Bhatnagar, S. and Borkar, V. S. 1997. Multiscale stochastic approximation for parametric optimization of hidden Markov models. Prob. Eng. and Info. Sci. 11, 509--522.Google Scholar
- Bhatnagar, S. and Borkar, V. S. 1998. A two time scale stochastic approximation scheme for simulation based parametric optimization. Prob. Eng. and Info. Sci. 12, 519--531.Google Scholar
- Bhatnagar, S. and Borkar, V. S. 2003. Multiscale chaotic SPSA and smoothed functional algorithms for simulation optimization. Simulation 79, 10, 568--580.Google Scholar
- 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.Google Scholar
- Bhatnagar, S., Fu, M. C., Marcus, S. I., and Fard, P. J. 2001b. Optimal structured feedback policies for ABR flow control using two-timescale SPSA. IEEE/ACM Trans. Network. 9, 4, 479--491. Google Scholar
- Bhatnagar, S., Fu, M. C., Marcus, S. I., and Wang, I.-J. 2003. Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences. ACM Trans. Modell. Comput. Simul. 13, 2, 180--209. Google Scholar
- Brandiere, O. 1998. Some pathological traps for stochastic approximation. SIAM J. Contr. Optim. 36, 1293--1314. Google Scholar
- 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.Google Scholar
- Chong, E. K. P. and Ramadge, P. J. 1993. Optimization of queues using an infinitesimal perturbation analysis-based stochastic algorithm with general update times. SIAM J. Cont. Optim. 31, 3, 698--732. Google Scholar
- 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.Google Scholar
- Dippon, J. and Renz, J. 1997. Weighted means in stochastic approximation of minima. SIAM J. Contr. Optim. 35, 1811--1827. Google Scholar
- Fabian, V. 1971. Stochastic approximation. In Optimizing Methods in Statistics J. J. Rustagi, Ed. Academic Press, New York, NY, 439--470.Google Scholar
- Fu, M. C. 1990. Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysis. J. Optim. Theo. Appl. 65, 149--160. Google Scholar
- Fu, M. C. and Hill, S. D. 1997. Optimization of discrete event systems via simultaneous perturbation stochastic approximation. IIE Trans. 29, 3, 233--243.Google Scholar
- Gelfand, S. B. and Mitter, S. K. 1991. Recursive stochastic algorithms for global optimization in Rd*. SIAM J. Cont. Optim. 29, 5, 999--1018. Google Scholar
- Hirsch, M. W. 1989. Convergent activation dynamics in continuous time networks. Neural Networks 2, 331--349. Google Scholar
- Ho, Y. C. and Cao, X. R. 1991. Perturbation Analysis of Discrete Event Dynamical Systems. Kluwer, Boston, MA.Google Scholar
- Kiefer, E. and Wolfowitz, J. 1952. Stochastic estimation of the maximum of a regression function. Ann. Math. Statist. 23, 462--466.Google Scholar
- Kleinman, N. L., Spall, J. C., and Naiman, D. Q. 1999. Simulation-based optimization with stochastic approximation using common random numbers. Manag. Sci. 45, 1570--1578. Google Scholar
- Kushner, H. J. and Clark, D. S. 1978. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer Verlag, New York, NY.Google Scholar
- Kushner, H. J. and Yin, G. G. 1997. Stochastic Approximation Algorithms and Applications. Springer Verlag, New York, NY.Google Scholar
- Lasalle, J. P. and Lefschetz, S. 1961. Stability by Liapunov's Direct Method with Applications. Academic Press, New York, NY.Google Scholar
- L'Ecuyer, P. and Glynn, P. W. 1994. Stochastic optimization by simulation: convergence proofs for the GI/G/1 queue in steady-state. Manag. Sci. 40, 11, 1562--1578. Google Scholar
- Luman, R. R. 2000. Upgrading complex systems of systems: a CAIV methodology for warfare area requirements allocation. Military Operations Research 5, 2, 53--75.Google Scholar
- Pemantle, R. 1990. Nonconvergence to unstable points in urn models and stochastic approximations. Annals of Prob. 18, 698--712.Google Scholar
- Polyak, B. T. and Juditsky, A. B. 1992. Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30, 4, 838--855. Google Scholar
- Robbins, H. and Monro, S. 1951. A stochastic approximation method. Ann. Math. Statist. 22, 400--407.Google Scholar
- Ruppert, D. 1985. A Newton-Raphson version of the multivariate Robbins-Monro procedure. Annals Statist. 13, 236--245.Google Scholar
- Spall, J. C. 1992. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. Auto. Cont. 37, 3, 332--341.Google Scholar
- Spall, J. C. 1997. A one-measurement form of simultaneous perturbation stochastic approximation. Automatica 33, 109--112. Google Scholar
- Spall, J. C. 2000. Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Trans. Autom. Contr. 45, 1839--1853.Google Scholar
- Zhu, X. and Spall, J. C. 2002. A modified second-order SPSA optimization algorithm for finite samples. Int. J. Adapt. Contr. Sign. Proce. 16, 397--409.Google Scholar
Index Terms
- Adaptive multivariate three-timescale stochastic approximation algorithms for simulation based optimization
Recommendations
Adaptive Newton-based multivariate smoothed functional algorithms for simulation optimization
In this article, we present three smoothed functional (SF) algorithms for simulation optimization. While one of these estimates only the gradient by using a finite difference approximation with two parallel simulations, the other two are adaptive Newton-...
Stochastic approximation algorithms for constrained optimization via simulation
We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem ...
Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences
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 ...
Comments