Seminar in Department of CSE: Simulation Based Methods for Optimization

In many engineering problems, one is often interested in optimizing a parameterized performance objective when only noisy observations of the objective function can be obtained. This is usually the case when the objective function corresponds to a long run average performance metric obtained from simulation. In such scenarios, often local search algorithms that perform incremental updates along descent directions are used. Finite difference stochastic approximation (FDSA) is one such approach for simulation optimization problems. A classical FDSA method is the Kiefer-Wolfowitz (K-W) finite difference algorithm. In a random direction version (Simultaneous Perturbation Stochastic Approximation (SPSA)) of K-W, all parameters are randomly perturbed together to obtain two function measurements that are then used to approximate the gradient. Another algorithm based on random perturbations is the smoothed functional algorithm (SFA). We present two efficient SPSA and SFA based discrete parameter simulation optimization algorithms and, we show their performance comparisons with the optimal computing budget allocation (OCBA) algorithm and also the equal allocation algorithm.

We also consider a parameterized SDE model of slotted Aloha with the retransmission probability as the associated parameter. Our work suggests that for the case of high dimensional noisy objective function these algorithms are significantly more economical than the conventional algorithms.

Speaker Bio:

Vivek Mishra received his B.Tech from IIT Roorkee and his PhD from IISc Bangalore. He was at IBM, ISL Bangalore from 2005 to 2007. His research interests are in the area of Computer Networks, High dimensional Discrete Optimization, Modeling and Simulation and Data Mining.