Electrical Engineering Seminar
Friday, October 25
11:00am - 12:00pm
SEC LL2.221

"First-order Methods for Linear and Quadratic Programming"
Haihao Lu, Assistant Professor of Operations Research & Statistics, Massachusetts Institute of Technology
 

Abstract: In this talk, I will talk about the recent ongoing trend of research on new first-order methods for scaling up and speeding up linear programming (LP) and quadratic programming (QP). The state-of-the-art solvers for LP and QP are mature and reliable at delivering accurate solutions. However, these methods do not scale up with modern computational resources such as GPUs and distributed computing. The computational bottleneck of these methods is matrix factorization, which usually requires significant memory usage and cannot be directly applied with modern computing resources. In contrast, first-order methods (FOMs) only require matrix-vector multiplications, which work well on these modern computing infrastructures and have massively 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 modern computational resources, i.e., distributed computing and/or GPUs. I’ll discuss how we can achieve this by explaining: (i) the intuitions about designing FOMs for LP; (ii) theoretical results, including complexity theory, condition number theory, infeasibility detection, and how theory can lead to better computation and better understanding of the algorithm’s performance; (iii) numerical results of the proposed algorithm on large instances and modern computing architectures; (iv) large-scale applications. After that, I’ll also talk about how to extend it to QP. I’ll conclude the talk with open questions and new directions on this line of research.

Bio: Haihao (Sean) Lu is an assistant professor of operations research and statistics at MIT. 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 Beale—Orachard-Hays Prize, INFORMS Optimization Society Young Researchers Prize, INFORMS Revenue Management and Pricing Section Prize and INFORMS Michael H. Rothkopf Junior Research Paper Prize (first place).