Oliver Hinder, University of Pittsburgh скачать в хорошем качестве

Oliver Hinder, University of Pittsburgh

Oliver Hinder, University of Pittsburgh, Practical Primal-Dual Hybrid Gradient for Large-Scale Linear Programming using Restarts and Other Enhancements Traditionally, linear programming (LP) is solved using Simplex or Interior Point Method whose core computational operation is factorization. Recently, there has been a push in the optimization community towards developing methods whose core computational operation is instead matrix-vector multiplications. Compared with factorization, matrix-vector multiplications are less likely to run out of memory on large-scale problems and are easily parallelized. However, there is a major drawback to these methods: they are often slow at finding high-accuracy solutions. This talk addresses this issue. Our method, PDLP, is based on primal-dual hybrid gradient, popularized by Chambolle and Pock (2011), and adds several important enhancements. One of these enhancements, which will be the focal point of the talk, is restarts. Restarts are already a popular method for unconstrained optimization; we show they are also extremely useful both in theory and practice for primal-dual methods. In particular, one can prove that PDHG’s runtime improves from O(κ^2 log(1/epsilon)) to O(κ log(1/epsilon)) using an adaptive restart scheme where κ is the condition number and epsilon is the desired accuracy. Finally, we evaluate the performance of PDLP on 383 LP instances derived from MIPLIB 2017. Compared with SCS, an ADMM based solver, with a target of 10^{-8} relative accuracy and 1 hour time limit, PDLP achieves a 6.3x reduction in the geometric mean of solve times and 4.6x reduction in the number of instances unsolved (from 227 to 49). Furthermore, we highlight standard benchmark instances and a large-scale application (PageRank) where our open-source prototype of PDLP, written in Julia, outperforms a commercial LP solver.