Speaker: Dr. Shizhen Zhao Purdue University
Time: 2017-11-16 10:30-2017-11-16 11:30
Venue: FIT 1-222

Abstract:

Uncertainty exits all the time in many network systems, and may significantly hurt system robustness. Existing uncertainty-management approaches either have very high complexity (e.g., curse of dimensionality in dynamic programming), or do not provide worst-case performance guarantee (e.g., Lyapunov optimization, Receding Horizon Control), or do not deal with sequential decisions (e.g., Robust Optimization). We propose to use online algorithms to make robust sequential decisions under future uncertainty. Simple online algorithms can provide worst-case performance guarantee for sequential decisions even if nothing is known about the future uncertainty. However, such performance guarantee is usually weak because of no future knowledge.

In this talk, we discuss how to use "partial future knowledge" to design better online algorithms, in the context of peak-minimizing EV charging. The key challenge here is to decide what partial future knowledge to obtain, and how to best utilize such partial future knowledge to provide stronger performance guarantee. From methodology point of view, we first propose a 2-level increasing precision model (2-IPM), to capture partial future knowledge. We then develop a powerful computational approach that can compute the optimal competitive ratio under 2-IPM over any online algorithm, and also online algorithms that can achieve the optimal competitive ratio. From algorithm point of view, we note a dilemma for online algorithm design: an online algorithm with good competitive ratio may exhibit poor average-case performance. We then propose a new Algorithm-Robustification procedure that can convert an online algorithm with good average-case performance to one with both the optimal competitive ratio and good average-case performance. We have validated our solution using both rigorous analysis and real-data simulation.

Short Bio:

Shizhen Zhao received his B.S. from Shanghai Jiao Tong University, China in 2010, and Ph.D. degree under the supervision of Prof. Xiaojun Lin, from Purdue University, West Lafayette, IN, in 2015. He is currently working on Google's large-scale network infrastructure. His research interests are in the analysis, control and optimization of data center networks, smart grid, and wireless networks. He has published papers on top conferences, including MOBICOM 2011, INFOCOM 2012/2014/2015/2016, and top journals, including IEEE/ACM Transactions on Networking and IEEE Transactions on Automatic Control.