ORIE Colloquium: Haihao (Sean) Lu (MIT)
Location
Frank H. T. Rhodes Hall 253
Description
GPU-Accelerated Linear Programming and Beyond
In this talk, I will talk about the recent trend of research on new first-order methods for scaling up and speeding up linear programming (LP) and convex quadratic programming (QP) with GPUs. The state-of-the-art solvers for LP and QP are mature and reliable at delivering accurate solutions. However, these methods are not suitable for modern computational resources, particularly GPUs. The computational bottleneck of these methods is matrix factorization, which usually requires significant memory usage and is highly challenging to take advantage of the massive parallelization of GPUs. In contrast, first-order methods (FOMs) only require matrix-vector multiplications, which work well on GPUs and have already accelerated machine learning training during the last 15 years. This ongoing line of research aims to scale up and speed up LP and QP by using FOMs and GPUs. I’ll discuss how we can achieve this by explaining: (i) the behaviors of FOMs for LP; (ii) computational results on GPUs and the broad impact of the algorithms in solver industry; (iii) theoretical results, including complexity theory and condition number theory, and how theory can lead to better computation and better understanding of the algorithm’s performance. If time permits, I’ll also talk about how to extend it to QP.
Bio:
Haihao (Sean) Lu is an assistant professor of operations research and statistics at the MIT Sloan School of Management. His research interests are extending the computational and mathematical boundaries of methods for solving large-scale optimization problems in data science, machine learning, and operations research. Before joining MIT, he was a faculty at the University of Chicago Booth School of Business, and a faculty visitor at Google Research's large-scale optimization team. He obtained his Ph.D. in operations research and mathematics at MIT in 2019. His research has been recognized by a few research awards, including the Beale — Orachard-Hays Prize, INFORMS Optimization Society Young Researchers Prize, INFORMS Revenue Management and Pricing Section Prize, COIN-OR (computational infrastructure for operations research) cup winner, and INFORMS Michael H. Rothkopf Junior Research Paper Prize (first place).