First Order Methods for Linear Programming: Theory, Computation, and Applications

3/17/22 | 4:15pm | E25-111


 

 

 

 

Haihao Lu

Assistant Professor of Operations Management
University of Chicago


Abstract: Linear programming (LP) is a fundamental tool in operations research with wide applications in practice. The state-of-the-art LP solvers are essentially based on either simplex method or barrier method, which are quite mature and reliable at delivering highly accurate solutions. However, it is highly challenging to further scale up these two methods. The computational bottleneck of both methods is the matrix factorization when solving linear equations, which requires significantly more memory usage and cannot be directly applied on the modern computing resources, i.e., distributed computing and/or GPUs. In contrast, first-order methods (FOMs) only require matrix-vector multiplications, which work very well on these modern computing infrastructures and have massively accelerated the machine learning training process during the last 15 years. In this talk, I’ll present new FOMs for LP. On the computational side, I’ll present a comprehensive numerical study on the proposed FOMs. On the theory side, I’ll present new techniques that improve the existing complexity of FOMs for LP and show that the proposed algorithms achieve the optimal convergence rate in the class of FOMs. If time permitted, I’ll characterize the convergence behaviors of our algorithms for solving (primal and/or dual) infeasible problems, which are crucial in LP solvers but have been overlooked in the FOM literature. I’ll conclude the talk with open questions and new directions on this line of research. Part of this research was done at Google.

Bio: Haihao (Sean) Lu is an assistant professor of Operations Management at the University of Chicago Booth School of Business. His research interests are in extending the computational and mathematical boundaries of methods for solving the large-scale optimization problems that arise in data science, machine learning, and operations research. Before joining Booth, he was a visiting researcher at Google Research large-scale optimization team, where he primarily worked on designing and implementing a huge-scale linear programming solver. He obtained his Ph.D degree in Operations Research and Applied Mathematics at MIT in 2019. He is the winner of INFORMS Optimization Society Young Researcher Prize (2021).

Event Time: 

2022 - 16:15