Adaptive multivariate three-timescale stochastic approximation algorithms for simulation based optimization
Author:
Open Access
- 1 January 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 15 (1) , 74-107
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.Keywords
This publication has 31 references indexed in Scilit:
- Multiscale Chaotic SPSA and Smoothed Functional Algorithms for Simulation OptimizationSIMULATION, 2003
- Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequencesACM Transactions on Modeling and Computer Simulation, 2003
- Optimal structured feedback policies for ABR flow control using two-timescale SPSAIEEE/ACM Transactions on Networking, 2001
- Two-timescale algorithms for simulation optimization of hidden Markov modelsIIE Transactions, 2001
- A Kiefer-Wolfowitz algorithm with randomized differencesIEEE Transactions on Automatic Control, 1999
- A two Timescale Stochastic Approximation Scheme for Simulation-Based Parametric OptimizationProbability in the Engineering and Informational Sciences, 1998
- Some Pathological Traps for Stochastic ApproximationSIAM Journal on Control and Optimization, 1998
- Multiscale Stochastic Approximation for Parametric Optimization of Hidden Markov ModelsProbability in the Engineering and Informational Sciences, 1997
- Optimization of the Transient and Steady-State Behavior of Discrete Event SystemsManagement Science, 1996
- Optimization of Queues Using an Infinitesimal Perturbation Analysis-Based Stochastic Algorithm with General Update TimesSIAM Journal on Control and Optimization, 1993