Haihao Lu.
Menu

Research

I develop optimization theory, algorithms, and software for large-scale decision-making. My research connects mathematical foundations with practical questions: how to exploit modern computing architectures, explain and improve algorithmic performance, allocate scarce resources under uncertainty, and make data-driven decisions fairer. These questions unite the four research areas below and guide collaborations with industry and public agencies.

GPU-accelerated mathematical programming

This research aims to make large-scale mathematical programming faster and more scalable by designing algorithms for modern computing architectures. Linear programming (LP) provides a starting point: simplex and interior-point methods have long dominated practice, but their reliance on sparse matrix factorizations can create computational and memory bottlenecks. The challenge is to exploit GPU parallelism while retaining the accuracy and reliability needed in optimization applications. Our approach combines inexpensive first-order iterations with adaptive restarting, preconditioning, and…Read moreShow less

This research aims to make large-scale mathematical programming faster and more scalable by designing algorithms for modern computing architectures. Linear programming (LP) provides a starting point: simplex and interior-point methods have long dominated practice, but their reliance on sparse matrix factorizations can create computational and memory bottlenecks. The challenge is to exploit GPU parallelism while retaining the accuracy and reliability needed in optimization applications.

Our approach combines inexpensive first-order iterations with adaptive restarting, preconditioning, and acceleration. Through a collaboration with researchers at Google that began in 2018, we developed PDLP, a practical LP solver introduced in 2021 and built around primal-dual hybrid gradient (PDHG) [1]. Its core iterations use sparse matrix-vector products and simple vector operations, making the approach well suited to GPUs. This foundation led to cuPDLP.jl in 2023, which demonstrated performance comparable to leading commercial solvers on standard benchmarks [2], and cuPDLPx in 2025, which delivered further substantial speedups [3]. Related work extends these ideas to convex and nonconvex quadratic programming [4, 5], as well as semidefinite programming [6].

I believe these advances have helped establish first-order methods as a practical third approach to LP alongside simplex and interior-point methods. PDLP has been deployed for routing and traffic engineering in Google's data-center networks since May 2023, enabling network-wide optimization with lower resource requirements. NVIDIA also uses cuOpt's PDLP-based LP solver for supply-chain planning, enabling rapid analysis of demand changes and supply disruptions. Implementations of the broader PDLP/PDHG approach are also available in COPT, HiGHS, NVIDIA cuOpt, Gurobi, FICO Xpress, and Artelys Knitro.

This line of research has been recognized with the 2024 Beale-Orchard-Hays Prize for PDLP, the 2024 COIN-OR Cup for cuPDLP.jl, and the 2026 INFORMS Computing Society Prize for GPU-based linear and convex quadratic optimization. My broader goal is to design optimization algorithms that exploit modern computing architectures, including GPUs and TPUs, to solve problems faster and at substantially larger scales.

Selected papers

  1. D. Applegate, M. Díaz, O. Hinder, H. Lu, M. Lubin, B. O'Donoghue, and W. Schudy (2021). Practical Large-Scale Linear Programming Using Primal-Dual Hybrid Gradient. Advances in Neural Information Processing Systems, 34, 20243–20257.
  2. H. Lu and J. Yang (2025). cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia. Operations Research, 73(6), 3440–3452.
  3. H. Lu, Z. Peng, and J. Yang (2025). cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming. Working paper.
  4. H. Lu and J. Yang (2026). A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic Programming. Mathematical Programming, 215, 771–808.
  5. Z. Chen and H. Lu (2026). PDNQP: A GPU-Based Factorization-Free Method for Large-Scale Nonconvex Quadratic Programming. Working paper.
  6. L. Ding, H. Lu, and J. Yang (2025). New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming. Working paper.
PDHG's last iterate spirals slowly toward the optimum and its average moves faster; restarting from the average (green, dashed) gets there fastest. Animation: Google Research.

Theoretical foundations of first-order optimization

My theoretical research has two complementary aims: to explain numerical performance and enhance algorithm design, and to develop concise, illuminating theory. Mathematical insights lead to faster and more reliable methods, while computational observations motivate theory that better captures how algorithms behave in practice. For linear programming, our analysis of sharpness and adaptive restarting yields optimal linear convergence rates within a broad class of primal-dual methods [1]. A refined analysis relates PDHG's convergence to local problem geometry, helping explain its practical…Read moreShow less

My theoretical research has two complementary aims: to explain numerical performance and enhance algorithm design, and to develop concise, illuminating theory. Mathematical insights lead to faster and more reliable methods, while computational observations motivate theory that better captures how algorithms behave in practice.

For linear programming, our analysis of sharpness and adaptive restarting yields optimal linear convergence rates within a broad class of primal-dual methods [1]. A refined analysis relates PDHG's convergence to local problem geometry, helping explain its practical behavior [2], while restarted Halpern PDHG provides further acceleration [3]. For infeasible problems, we show how diverging iterates yield certificates of infeasibility [4]. These results provide theoretical foundations and directly guide the design and development of fast, reliable solvers, including PDLP, cuPDLP, and cuPDLPx.

This emphasis on conceptual clarity also motivates our work on simple, reusable frameworks. Relative smoothness, relative strong convexity, and relative continuity adapt first-order methods to problem geometry beyond standard Lipschitz assumptions [5, 6]. Our unified proof for the proximal point method (PPM), PDHG, and the alternating direction method of multipliers (ADMM) exposes their common structure [7], while my high-resolution ordinary differential equation (ODE) framework connects continuous-time intuition with discrete algorithm behavior [8]. These frameworks make convergence analysis more transparent and offer insights for algorithm design and teaching. The ODE work received the 2021 INFORMS Optimization Society Young Researchers Prize.

Selected papers

  1. D. Applegate, O. Hinder, H. Lu, and M. Lubin (2023). Faster First-Order Primal-Dual Methods for Linear Programming Using Restarts and Sharpness. Mathematical Programming, 201, 133–184.
  2. H. Lu and J. Yang (2025). On the Geometry and Refined Rate of Primal-Dual Hybrid Gradient for Linear Programming. Mathematical Programming, 212, 349–387.
  3. H. Lu and J. Yang (2024). Restarted Halpern PDHG for Linear Programming. Working paper.
  4. D. Applegate, M. Díaz, H. Lu, and M. Lubin (2024). Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming. SIAM Journal on Optimization, 34(1), 459–484.
  5. H. Lu, R. M. Freund, and Y. Nesterov (2018). Relatively Smooth Convex Optimization by First-Order Methods, and Applications. SIAM Journal on Optimization, 28(1), 333–354.
  6. H. Lu (2019). 'Relative Continuity' for Non-Lipschitz Nonsmooth Convex Optimization Using Stochastic (or Deterministic) Mirror Descent. INFORMS Journal on Optimization, 1(4), 288–303.
  7. H. Lu and J. Yang (2023). On a Unified and Simplified Proof for the Ergodic Convergence Rates of PPM, PDHG and ADMM. Working paper.
  8. H. Lu (2022). An O(sr)-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems. Mathematical Programming, 194, 1061–1112.
Gradient descent–ascent iterates spiraling outward from a saddle point, compared with a closed orbit predicted by a low-resolution ODE
Schematic. On a min–max problem, the low-resolution ODE predicts a closed orbit; a higher-resolution ODE tracks the iterates as they spiral.

Online decision-making and advertising

Online resource allocation requires decisions before future demand is known. In automated bidding at Google, algorithms must decide within milliseconds how aggressively to bid across successive auctions while satisfying advertisers' budgets and return-on-spend (ROS) constraints. The challenge is to make these decisions efficiently under stochastic, non-stationary, or even adversarial uncertainty. We developed a dual mirror descent framework that learns the opportunity cost, or shadow price, of scarce resources from streaming outcomes and uses those prices to guide decisions. By applying…Read moreShow less

Online resource allocation requires decisions before future demand is known. In automated bidding at Google, algorithms must decide within milliseconds how aggressively to bid across successive auctions while satisfying advertisers' budgets and return-on-spend (ROS) constraints. The challenge is to make these decisions efficiently under stochastic, non-stationary, or even adversarial uncertainty.

We developed a dual mirror descent framework that learns the opportunity cost, or shadow price, of scarce resources from streaming outcomes and uses those prices to guide decisions. By applying online mirror descent to dual variables, it achieves simultaneous “best-of-many-worlds” guarantees across these input models [1]. Further work addresses joint budget and ROS pacing in automated bidding [2, 3] and incorporates fairness and regularized objectives into online allocation [4]. Convolutional mirror descent also connects online convex optimization with dual-based proportional-integral-derivative (PID) control, providing a theoretical foundation for feedback controllers used in practice [5].

The framework is deployed globally as a core real-time budget and ROS pacing engine in Google Ads, supporting automated bidding across Google Search, Universal App Campaigns, and Demand Gen campaigns. Replacing legacy pacing heuristics with this principled shadow-price update has significantly improved advertiser conversion value at unchanged budgets and increased on-target pacing precision across global auction traffic.

This line of research received the 2022 INFORMS Michael H. Rothkopf Junior Researcher Paper Prize (first place), the 2023 INFORMS Revenue Management and Pricing Section Prize, and an internal Google Impact Award in 2024. Beyond advertising, these methods have potential applications in resource allocation across digital marketplaces, cloud computing, and network traffic engineering.

Selected papers

  1. S. R. Balseiro, H. Lu, and V. Mirrokni (2023). The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Operations Research, 71(1), 101–119.
  2. S. R. Balseiro, K. Bhawalkar, Z. Feng, H. Lu, V. Mirrokni, B. Sivan, and D. Wang (2024). A Field Guide for Pacing Budget and ROS Constraints. Proceedings of the 41st International Conference on Machine Learning (ICML), PMLR 235, 2607–2638.
  3. G. Aggarwal, A. Badanidiyuru, S. R. Balseiro, et al. (2024). Auto-Bidding and Auctions in Online Advertising: A Survey. ACM SIGecom Exchanges, 22(1), 159–183.
  4. S. R. Balseiro, H. Lu, and V. Mirrokni (2025). Regularized Online Allocation Problems: Fairness and Beyond. Manufacturing & Service Operations Management, 27(3), 720–735.
  5. S. R. Balseiro, H. Lu, V. Mirrokni, and B. Sivan (2026). Analysis of Dual-Based PID Controllers through Convolutional Mirror Descent. Operations Research, forthcoming.
Shadow price learned by dual mirror descent rising and settling near its optimal value
Schematic. Dual mirror descent learns the shadow price of a budget from streaming requests and settles near its optimal value.

Addressing regressivity in property taxation

Property-tax regressivity is a consequential computational social science problem: owners of lower-valued homes can pay a higher share of property value in taxes. Systematic errors in automated valuation models can reinforce this inequity [1]. Research documents widespread regressivity across the United States, racial disparities in property-tax burdens, and links between inflated assessments and tax foreclosures in Detroit. These findings highlight the stakes for household financial security and social equity, motivating my work on socially responsible machine learning and operations…Read moreShow less

Property-tax regressivity is a consequential computational social science problem: owners of lower-valued homes can pay a higher share of property value in taxes. Systematic errors in automated valuation models can reinforce this inequity [1]. Research documents widespread regressivity across the United States, racial disparities in property-tax burdens, and links between inflated assessments and tax foreclosures in Detroit. These findings highlight the stakes for household financial security and social equity, motivating my work on socially responsible machine learning and operations research.

In collaboration with the Cook County Assessor's Office (CCAO), we developed a regularization method that targets regressivity during model training [2]. The method has already been adopted in CCAO's valuation workflow, where its use has substantially reduced measured assessment regressivity while maintaining comparable predictive accuracy. This collaboration brings our research into a public property assessment system serving more than five million residents.

The method will be used in future property assessments in Cook County. We are also working to extend its use to other jurisdictions across the United States, with the goal of improving assessment equity at a national scale.

Selected papers

  1. O. Candogan, F. Han, and H. Lu (2023). Achieving Fairness and Accuracy in Regressive Property Taxation. MIT Sloan Working Paper 7126-23.
  2. N. Acevedo, H. Lu, M. Wagner, and T. Sparer. Fair Property Tax: Targeting Regressivity in Machine Learning-Based Valuation. Unpublished manuscript.
Assessment ratio by home value: a standard model declines with value while a regressivity-penalized model stays flat
Schematic. A standard valuation model over-assesses lower-valued homes; penalizing regressivity during training flattens the ratio.

Other research I have been working on

Beyond these four core areas, I work with academic and industry collaborators on optimization applications in marketing, finance, energy, and computing infrastructure. Recommendation systems at eBay. Sponsored recommendations must balance platform revenue with product relevance. With eBay, we developed a ranking method based on linear programming that incorporates these objectives and operational constraints [1]. A 19-day field experiment covering approximately 329 million impressions showed higher revenue while maintaining or improving relevance. The algorithm entered production in January…Read moreShow less

Beyond these four core areas, I work with academic and industry collaborators on optimization applications in marketing, finance, energy, and computing infrastructure.

Recommendation systems at eBay. Sponsored recommendations must balance platform revenue with product relevance. With eBay, we developed a ranking method based on linear programming that incorporates these objectives and operational constraints [1]. A 19-day field experiment covering approximately 329 million impressions showed higher revenue while maintaining or improving relevance. The algorithm entered production in January 2023, demonstrating the value of optimization in a large online marketplace.

Targeted marketing. Firms must decide which promotions to offer to which customers while respecting limits on campaign volume and fairness requirements across customer groups. We developed a scalable linear programming approach to optimize these targeting policies under such constraints [2]. Using data from a field experiment with over two million customers, we demonstrate that the method makes large-scale, constrained targeted marketing problems computationally tractable.

Portfolio optimization. Portfolio construction in high-frequency trading requires balancing expected returns, risk, and trading costs across assets and time. We developed FlashFolio, a GPU-accelerated solver for single-period and multi-period portfolio problems with factor-based risk models and transaction costs, including nonlinear market impact [3]. Benchmarks using realistic market inputs show substantial speedups over a commercial solver, making larger and more detailed portfolio models practical.

Power systems with GE Vernova — ongoing work. I am working with GE Vernova to apply scalable optimization methods to power-system decision-making, translating advances in mathematical programming into tools for energy applications.

Data-center operations with Google — ongoing work. I am working with Google on optimization for data-center operations, exploring how scalable methods can improve resource allocation and operational efficiency in large computing facilities.

Selected papers

  1. H. Lu, L. Zhang, and Y. Zhu (2025). The Power of Linear Programming in Sponsored Listings Ranking: Evidence from a Large-Scale Field Experiment. Working paper.
  2. H. Lu, D. Simester, and Y. Zhu (2025). Optimizing Scalable Targeted Marketing Policies with Constraints. Marketing Science, 44(5), 1082–1103.
  3. Y. Jiang, H. Lu, Z. Peng, and J. Yang (2026). FlashFolio: A GPU-Accelerated Solver for Portfolio Optimization. Working paper.