Dynamic Learning Algorithms for Online Linear/Non-linear Optimization Problems

Zizhuo Wang

Date and Time: 

Tuesday, September 1, 2015 - 4:00pm

Event Location: 

Mohler Lab, Room 453

In this talk, we consider two online optimization problems. The first one is the online linear programming problem. In this problem, the underlying optimization problem is a linear program, however, its constraint matrix is revealed column by column along with the corresponding
objective coefficient and a decision variable has to be set each time a column is revealed without observing the future inputs. The goal is to maximize the overall objective function. In this talk, we provide a near-optimal algorithm for this general class of online problems under the assumption of random order of arrival of the columns and some mild conditions on the size of the LP right-handside input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Due to the feature of dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst-case example showing that the performance of our algorithm is near-optimal.

We then extend the scope of our learning algorithm to solve a generalization of one special case of the online linear program, the online matching problem. In the generalization, the objective function no longer needs to be linear, but could be general concave functions. This formulation has important applications in online adwords allocation problem when there is a convex under-delivery cost, or the click-through rate is concave in the number of impressions. We show that our algorithm is still near-optimal under some conditions on the inputs. Some numerical results are shown to validate the efficiency of our approach.

Bio Sketch: 

Dr. Zizhuo Wang is an Assistant Professor from the Department of Industrial and Systems Engineerig (ISyE) at the University of Minnesota. He received his Ph.D. in Operations Research from Stanford University in 2012. Prior to that, he graduated from Department of Mathematical Sciences in Tsinghua University at 2007 and obtained his M.S. in Mathematical Finances in 2011 from Stanford University. His research interests mainly focus on optimization and stochastic modeling, especially with applications to pricing and revenue management.