About

Haihao Lu is the Cecil and Ida Green Career Development Assistant Professor and an Assistant Professor of Operations Research and Statistics at the MIT Sloan School of Management. His 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. Much of his work is inspired by real-world challenges faced by leading technology companies and optimization software companies. Lu develops new first-order optimization algorithms, theoretical guarantees, and computational tools to accelerate and scale mathematical programming using modern computing architectures such as GPUs and distributed systems. His contributions include the development of algorithms like the PDLP algorithm, which has been widely adopted by industry-leading solvers and tech companies including Google, NVIDIA, and Gurobi. Additionally, he designs algorithms with provable performance guarantees for resource allocation in uncertain environments, with applications such as online advertising budget pacing, where his algorithms have been deployed by major platforms like Google and eBay. Lu's research has been recognized with several awards, including the 2026 Sloan Research Fellowship, the 2024 COIN-OR Cup, the 2024 Beale—Orchard-Hays Prize, and the INFORMS prizes, highlighting his significant impact and leadership in the field of optimization and operations research.

Research topics

• Computer Science
• Artificial Intelligence
• Mathematical optimization
• Mathematics
• Machine Learning
• Algorithm
• Engineering
• Applied mathematics
• Geometry

Selected publications

• A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG

  INFORMS journal on computing · 2026-04-06

  preprintOpen accessSenior author

  Motivated by large-scale applications, there is a recent trend of research on using first-order methods for solving LP. Among them, PDLP, which is based on a primal-dual hybrid gradient (PDHG) algorithm, may be the most promising one. In this paper, we present a geometric viewpoint on the behavior of PDHG for LP. We demonstrate that PDHG iterates exhibit a spiral pattern with a closed-form solution when the variable basis remains unchanged. This spiral pattern consists of two orthogonal components: rotation and forward movement, where rotation improves primal and dual feasibility, while forward movement advances the duality gap. We also characterize the different situations in which basis change events occur. Inspired by the spiral behavior of PDHG, we design a new crossover algorithm to obtain a vertex solution from any optimal LP solution. This approach differs from traditional simplex-based crossover methods. Our numerical experiments demonstrate the effectiveness of the proposed algorithm, showcasing its potential as an alternative option for crossover. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: T. Liu is partially supported by National Natural Science Foundation of China [Grants NSFC-72225009, 72394360, 72394365]. H. Lu is partially supported by Air Force Office of Scientific Research [Grant FA9550-24-1-0051] and Office of Naval Research [Grant N000142412735]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc . 2024.0996 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0996 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

  PublisherOA PDFDOI

• PDLP: a practical first-order method for large-scale linear programming

  Mathematical Programming Computation · 2026-05-15

  article
  PublisherDOI

• Code and Data Repository for A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG

  INFORMS journal on computing · 2026-02-10

  articleSenior author

  The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG by Tianhao Liu and Haihao Lu.

  PublisherDOI

• Active set identification and rapid convergence for degenerate primal-dual problems

  arXiv (Cornell University) · 2026-02-11

  articleOpen access

  Primal-dual methods for solving convex optimization problems with functional constraints often exhibit a distinct two-stage behavior. Initially, they converge towards a solution at a sublinear rate. Then, after a certain point, the method identifies the set of active constraints and the convergence enters a faster local linear regime. Theory characterizing this phenomenon spans over three decades. However, most existing work only guarantees eventual identification of the active set and relies heavily on nondegeneracy conditions, such as strict complementarity, which often fail to hold in practice. We characterize mild conditions on the problem geometry and the algorithm under which this phenomenon provably occurs. Our guarantees are entirely nonasymptotic and, importantly, do not rely on strict complementarity. Our framework encompasses several widely-used algorithms, including the proximal point method, the primal-dual hybrid gradient method, the alternating direction method of multipliers, and the extragradient method.

  PublisherOA PDF

• Active set identification and rapid convergence for degenerate primal-dual problems

  Open MIND · 2026-02-11

  preprint

  Primal-dual methods for solving convex optimization problems with functional constraints often exhibit a distinct two-stage behavior. Initially, they converge towards a solution at a sublinear rate. Then, after a certain point, the method identifies the set of active constraints and the convergence enters a faster local linear regime. Theory characterizing this phenomenon spans over three decades. However, most existing work only guarantees eventual identification of the active set and relies heavily on nondegeneracy conditions, such as strict complementarity, which often fail to hold in practice. We characterize mild conditions on the problem geometry and the algorithm under which this phenomenon provably occurs. Our guarantees are entirely nonasymptotic and, importantly, do not rely on strict complementarity. Our framework encompasses several widely-used algorithms, including the proximal point method, the primal-dual hybrid gradient method, the alternating direction method of multipliers, and the extragradient method.

  DOI

• An Overview of GPU-based First-Order Methods for Linear Programming and Extensions

  ArXiv.org · 2025-06-02

  preprintOpen access1st authorCorresponding

  The rapid progress in GPU computing has revolutionized many fields, yet its potential in mathematical programming, such as linear programming (LP), has only recently begun to be realized. This survey aims to provide a comprehensive overview of recent advancements in GPU-based first-order methods for LP, with a particular focus on the design and development of cuPDLP. We begin by presenting the design principles and algorithmic foundation of the primal-dual hybrid gradient (PDHG) method, which forms the core of the solver. Practical enhancements, such as adaptive restarts, preconditioning, Halpern-type acceleration and infeasibility detection, are discussed in detail, along with empirical comparisons against industrial-grade solvers, highlighting the scalability and efficiency of cuPDLP. We also provide a unified theoretical framework for understanding PDHG, covering both classical and recent results on sublinear and linear convergence under sharpness conditions. Finally, we extend the discussion to GPU-based optimization beyond LP, including quadratic, semidefinite, conic, and nonlinear programming.

  PublisherOA PDFDOI

• Optimizing Scalable Targeted Marketing Policies with Constraints

  Marketing Science · 2025-03-20 · 2 citations

  article1st authorCorresponding

  This paper introduces a novel optimization algorithm to address targeting problems with a large and complex set of constraints.

  PublisherDOI

• cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming

  ArXiv.org · 2025-07-18

  preprintOpen access1st authorCorresponding

  We introduce cuPDLPx, a further enhanced GPU-based first-order solver for linear programming. Building on the recently developed restarted Halpern PDHG for LP, cuPDLPx incorporates a number of new techniques, including a new restart criterion and a PID-controlled primal weight update. These improvements are carefully tailored for GPU architectures and deliver substantial computational gains. Across benchmark datasets, cuPDLPx achieves 2.5x-5x speedups on MIPLIB LP relaxations and 3x-6.8x on Mittelmann's benchmark set, with particularly strong improvements in high-accuracy and presolve-enabled settings. The solver is publicly available at https://github.com/MIT-Lu-Lab/cuPDLPx.

  PublisherOA PDFDOI

• Regularized Online Allocation Problems: Fairness and Beyond

  Manufacturing & Service Operations Management · 2025-02-20 · 12 citations

  article

  Problem definition: Online allocation problems with resource constraints have a rich history in operations management. In this paper, we introduce the regularized online allocation problem, a variant that includes a nonlinear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time, and for each request, a decision-maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints. Methodology/results: We design an algorithm that is simple and fast and attains good performance with stochastic and adversarial inputs. In particular, our algorithm is asymptotically optimal under stochastic i.i.d. input models, attains a fixed competitive ratio that depends on the regularizer when the input is adversarial, and can handle a sublinear amount of non-stationarity. Furthermore, the algorithm and analysis do not require convexity or concavity of the reward function and the consumption function, which allows more model flexibility. Numerical experiments confirm the effectiveness of the proposed algorithm and of regularization in an Internet advertising application. Managerial implications: Introducing a regularizer allows decision-makers to trade off separable objectives such as the economic efficiency of an allocation with ancillary, non-separable objectives such as fairness or equity of an allocation. Our results have implications for online allocation problems across many sectors, such as Internet advertising, cloud computing, and humanitarian logistics, in which fairness and equity are key considerations for managers. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0212 .

  PublisherDOI

• Software and Data for "cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia"

  Operations Research · 2025-01-01 · 1 citations

  article1st authorCorresponding
  PublisherDOI

Frequent coauthors

• Vahab Mirrokni

  26 shared

• Santiago Balseiro

  12 shared

• Robert M. Freund

  Massachusetts Institute of Technology

  10 shared

• Miles Lubin

  Google (United States)

  8 shared

• David Applegate

  8 shared

• Jinwen Yang

  8 shared

• Benjamin Grimmer

  7 shared

• Mateo Díaz

  6 shared

Labs

• MIT SloanPI

Awards & honors

• 2026 Sloan Research Fellowship
• 2024 COIN-OR Cup
• 2024 Beale—Orachard-Hays Prize for Excellence in Computation…
• INFORMS Revenue Management and Pricing Section Prize (2023)
• Michael H. Rothkopf Junior Researcher Paper Prize (2022)