Hostname: page-component-7c8c6479df-xxrs7 Total loading time: 0 Render date: 2024-03-28T16:11:40.485Z Has data issue: false hasContentIssue false

A two Timescale Stochastic Approximation Scheme for Simulation-Based Parametric Optimization

Published online by Cambridge University Press:  27 July 2009

Shalabh Bhatnagar
Affiliation:
Institute for Systems Research, University of Maryland, College Park, MD 20742shalabh@isr.umd.edu
Vivek S. Borkar
Affiliation:
Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560 012, Indiaborkar@csa.iisc.ernet.in

Abstract

A two timescale stochastic approximation scheme which uses coupled iterations is used for simulation-based parametric optimization as an alternative to traditional “infinitesimal perturbation analysis” schemes. It avoids the aggregation of data present in many other schemes. Its convergence is analyzed, and a queueing example is presented.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Bhatnagar, S. & Borkar, V.S. (1997). Multiscale stochastic approximation for parametric optimization of hidden Markov models. Probability in the Engineering and Informational Sciences 11: 509522.CrossRefGoogle Scholar
2.Borkar, V.S. (1995). Probability theory: An advanced course. New York: Springer Verlag.CrossRefGoogle Scholar
3.Borkar, V.S. (1997). Stochastic approximation with two time scales. Systems and Control Letters 29: 291294.CrossRefGoogle Scholar
4.Chong, E.K.P. & Ramadge, R.J. (1994). Stochastic optimization of regenerative systems using infinitesimal perturbation analysis. IEEE Transactions on Automatic Control 39(7): 14001410.CrossRefGoogle Scholar
5.Chong, E.K.P. & Ramadge, P.J. (1993). Optimization of queues using an infinitesimal perturbation analysis-based stochastic algorithm with general update times. SIAM Journal on Control and Optimization 31(3): 698732.CrossRefGoogle Scholar
6.Hirsch, M.W. (1987). Convergent activation dynamics in continuous time networks. Neural Networks 2: 331349.CrossRefGoogle Scholar
7.Kushner, H.J. & Clark, D.S. (1978). Stochastic approximation methods for constrained and unconstrained systems. New York: Springer Verlag.CrossRefGoogle Scholar
8.L'Ecuyer, P. & Glynn, P.W. (1994). Stochastic optimization by simulation: Convergence proofs for the GI/G/I queue in steady state. Management Science 40(11): 15621578.CrossRefGoogle Scholar
9.Loeve, M. (1977). Probability theory 2, 4th ed.New York; Springer.Google Scholar
10.Rubinstein, R. (1981). Simulation and the Monte Carlo Method. New York: John Wiley.CrossRefGoogle Scholar
11.Ruszczynski, A. & Syski, W. (1983). Stochastic approximation method with gradient averaging for unconstrained problems. IEEE Transactions on Automatic Control AC-28(12): 10971105.CrossRefGoogle Scholar
12.Spall, J.C. (1992). Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control 37(3): 332341.CrossRefGoogle Scholar
13.Suri, R. & Zazanis, M.A. (1988). Perturbation analysis gives strongly consistent estimates for the M/G/1 queue. Management Science 34(1): 3964.CrossRefGoogle Scholar