Optimal Design of Queuing Systems via Compositional Stochastic Programming

Ketan Rajawat
Rahul Vaze
Tuesday, 16 Jun 2020, 14:00 to 15:00
A-201 (STCS Seminar Room)
Abstract: Well-designed queuing systems form the backbone of modern communications, distributed computing, and content delivery architectures. Designs balancing infrastructure costs and user experience indices require tools from tele-traffic theory and operations research. A standard approach to designing such systems involves formulating optimization problems that strive to maximize the pertinent utility functions while adhering to quality-of-service and other physical constraints. In many cases, formulating such problems necessitates making simplistic assumptions on arrival and departure processes to keep the problem tractable.

This talks will introduce a stochastic optimization framework for designing queuing systems where the exogenous processes may have arbitrary and unknown distributions. We show that many such queuing design problems can generally be formulated as stochastic optimization problems where the objective and constraints are non-linear functions of expectations. The compositional structure obviates the use of classical stochastic approximation approaches where the stochastic gradients are often required to be unbiased. To this end, a constrained stochastic compositional gradient descent algorithm is proposed that utilizes a tracking step for the expected value functions. The non-asymptotic performance of the proposed algorithm is characterized by its iteration complexity. Further improvements are proposed that build upon the primal-dual saddle point algorithm to result in zero constraint violation and O(T-0.25) optimality gap. Numerical tests allow us to validate the theoretical results and demonstrate the efficacy of the proposed algorithm.

Bio: Ketan Rajawat (S'06–M'12) received his B.Tech and M.Tech degrees in Electrical Engineering from the Indian Institute of Technology (IIT) Kanpur, India, in 2007, and his Ph.D. degree in Electrical and Computer Engineering from the University of Minnesota, Minneapolis, MN, USA, in 2012. He is currently an Associate Professor in the Department of Electrical Engineering, IIT Kanpur. His research interests are in the broad areas of signal processing, robotics, and communications networks, with particular emphasis on distributed optimization and online learning. His current research focuses on the development and analysis of distributed and asynchronous optimization algorithms, online convex optimization algorithms, stochastic optimization algorithms, and the application of these algorithms to problems in machine learning, communications, and smart grid systems. He is currently serving as an Associate Editor with the IEEE Communications Letters and IEEE Transactions on Signal Processing. He is also the recipient of the 2018 INSA Medal for Young Scientists and the 2019 INAE Young Engineer Award.