IEDA/ISOM JOINT Seminar - Online Linear Programming: Applications and Extensions
A natural optimization model that formulates many online learning, resource allocations and dynamic decision-making with uncertainty is online linear programming (OLP) where the noisy constraint column vectors, along with the objective coefficients and decision variables, are revealed and decided sequentially. We review the near optimal algorithms and theories for solving this surprisingly general class of online problems under the assumption of random order of arrivals and/or stationary distributions of the input data. Then we present few recent developments of the model/algorithm, including a fast online algorithm as a pre-solver for solving large-scale offline (binary) LPs, an interior-point online algorithm to address “fairness” for resource allocation, a provable logarithmic regret bound for the Bandits with Knapsacks (BwK) problem, an extension to online Fisher markets with a geometric aggregation of individual utilities, and how to deal with non-stationary data distributions in online learning.
Yinyu Ye is currently the K.T. Li Professor of Engineering at Department of Management Science and Engineering and Institute of Computational and Mathematical Engineering, Stanford University. His current research interests include Continuous and Discrete Optimization, Data Science and Application, Algorithm Design and Analysis, Computational Game/Market Equilibrium, Metric Distance Geometry, Dynamic Resource Allocation, and Stochastic and Robust Decision Making, etc.
He is an INFORMS (The Institute for Operations Research and The Management Science) Fellow since 2012, and has received several academic awards including: the inaugural 2006 Farkas Prize on Optimization, the 2009 IBM Faculty Award, the 2009 John von Neumann Theory Prize for fundamental sustained contributions to theory in Operations Research and the Management Sciences, the inaugural 2012 ISMP Tseng Lectureship Prize for outstanding contribution to continuous optimization (every three years), the winner of the 2014 SIAM Optimization Prize awarded (every three years), the 2015 SPS Signal Processing Magazine Best Paper Award, etc.. According to Google Scholar, his publications have been cited 51,000 times.