GPU-Accelerated First-Order Methods for Linear Programming and Beyond

Abstract

Can first-order methods and GPUs solve traditional mathematical optimization problems at scale? For decades, this seemed unlikely: conventional wisdom held that reliable LP solvers depended on simplex or interior-point methods and sparse factorizations, while first-order methods were considered too slow or inaccurate. This talk traces the PDLP research line from CPU-based PDLP through GPU-based cuPDLP to cuPDLPx. I will explain how GPU-friendly sparse matrix-vector operations, restarted primal-dual algorithms, and careful numerical design together achieve high accuracy, robustness, and competitive end-to-end performance. I will also discuss theoretical guarantees for linear convergence and infeasibility detection. Computational results cover standard LP benchmarks and practical applications, including problems with hundreds of millions of variables or nonzeros. Beyond its academic contributions, this line of research has helped drive a broader shift toward GPU-based first-order methods across the optimization solver ecosystem. These methods complement simplex and interior-point algorithms and become especially compelling at very large scales. Time permitting, I will conclude with extensions to convex quadratic and semidefinite programming.

Bio

Haihao 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. His research lies at the intersection of optimization, computation, and data science, with a focus on advancing the computational and mathematical frontiers of large-scale optimization. Much of his work is inspired by challenges faced by leading technology and optimization software companies, including the development of scalable first-order solvers and data-driven optimization methods for resource allocation. His research has generated substantial revenue in practical applications and advanced the state of practice in large-scale optimization. His honors include a Sloan Research Fellowship, INFORMS Computing Society Prize, the COIN-OR Cup, the Beale–Orchard-Hays Prize, the INFORMS Optimization Society Young Researchers Prize, first place in the INFORMS Michael H. Rothkopf Junior Research Paper Prize, and the INFORMS Revenue Management and Pricing Section Prize. Before joining MIT Sloan, he was an Assistant Professor at the University of Chicago Booth School of Business and a faculty researcher on Google Research’s large-scale optimization team. He received his PhD in Mathematics and Operations Research from MIT in 2019.