Prof. Haihao Lu
Massachusetts Institute of Technology
Talk: GPU-Accelerated Linear Programming and Beyond
Abstract: In this talk, I will discuss recent research trends on first-order methods for scaling and accelerating linear programming (LP), convex quadratic programming (QP), and semidefinite programming (SDP) using GPUs. While state-of-the-art solvers for these problems are mature and reliable in delivering high-accuracy solutions, they are not well suited to modern computational architectures, particularly GPUs. A key bottleneck lies in matrix factorization, which is memory-intensive and difficult to parallelize effectively on GPUs. In contrast, first-order methods rely primarily on matrix-vector multiplications, which are highly compatible with GPU architectures and have driven significant advances in large-scale machine learning over the past decade. I will discuss how this paradigm can be leveraged to scale LP and QP solvers, covering: (i) empirical behavior of first-order methods for LP; (ii) computational results on GPUs; and (iii) theoretical insights, including complexity and condition number analysis, and how these inform algorithm design and performance. If time permits, I will also touch on extensions to QP and SDP.
Biography: Haitao Lu is the Cecil and Ida Green career development assistant professor, and an assistant professor of Operations Research/Statistics at the MIT Sloan School of Management. Before joining MIT Sloan, he was an assistant professor at the University of Chicago Booth School of Business and a faculty researcher at Google Research's large-scale optimization team. He obtained his PhD degree in Mathematics and Operations Research at MIT in 2019. Prof. Lu's research lies at the intersection of optimization, computation, and data science, with a focus on pushing the computational and mathematical frontiers of large-scale optimization. His research has been recognized by several research awards, including COIN-OR Cup, the Beale—Orachard-Hays Prize, the INFORMS Optimization Society Young Researchers Prize, the INFORMS Michael H. Rothkopf Junior Research Paper Prize (first place), and the INFORMS Revenue Management and Pricing Section Prize.
