Title: Theoretical Foundations and Practical Improvements for Large-Scale
Linear Programming
Abstract: Just in the last several years, we have witnessed a dramatic shift in
the way linear programs (LPs) are actually solved -- the classic methods
(simplex method and interior-point method) are being replaced by the primal-
dual hybrid gradient method (PDHG) to solve large-scale LP problems. PDHG
-- with heuristic enhancements and GPU implementation -- has been very
successful in solving large-scale LP problems; however, its performance can
have substantial variance, and an intuitive understanding of the drivers of its
performance has been lacking. In this talk I will present new results on both
the theoretical foundations and practical improvements of PDHG.
Furthermore, these results extend to general conic convex optimization. Our
analysis shows that the geometry of the primal-dual (sub-)level sets plays a
critical role in the performance of PDHG – both in theory and in practice. This
is both good and bad, because it implies that unfavorable geometry of some
instances leads to the poor performance of PDHG. To address this issue, we
show how to construct central-path-based rescaling transformations that can
markedly enhance the convergence of PDHG by favorably changing the LP
geometry. I will also present computational results that demonstrate how the
rescaling accelerates convergence to high-accuracy solutions and leads to
improved solution times for LP. Last of all, I will present some very recent
results on the “average-case” polynomial-time complexity of PDHG for LP,
which shrinks the gap between the theoretical analysis and the observed
performance of PDHG for LP.
Bio: Zikai Xiong is a final-year PhD student at the MIT Operations Research
Center, advised by Professor Robert M. Freund. His current research interests
are mainly in optimization, with twin interests in theoretical foundations and
computational practice. His research up to now has involved enhancing the
scalability of optimization algorithms for solving large-scale linear and convex
optimization -- both generically as well as on specific applications in
operations, data science and machine learning. Some of his methods have
already been implemented in the state-of-art commercial solvers. He was a
research intern studying algorithmic fairness in machine learning at JPMorgan
AI Research in the summer of 2023. Prior to MIT, he obtained a B.S. degree in
Mathematics and Applied Mathematics from Fudan University.
