Interior Point Methods Are Not Worse than Simplex

We develop a new “subspace layered least squares” interior point method (IPM) for solving linear programs. Applied to an n-variable linear program in standard form, the iteration complexity of our IPM is up to an O(n ^1.5 log n) factor upper bounded by the straight-line complexity (SLC) of the linear program. This term refers to the minimum number of segments of any piecewise linear curve that traverses the wide neighborhood of the central path, a lower bound on the iteration complexity of any IPM that follows a piecewise linear trajectory along a path induced by a self-concordant barrier. In particular, our algorithm matches the number of iterations of any such IPM up to the same factor O(n ^1.5 log n). As our second contribution, we show that the SLC of any linear program is upper bounded by 2 ⁿ(1+o ⁽¹⁾⁾, which implies that our IPM's iteration complexity is at most exponential. This is in contrast to existing iteration complexity bounds that depend on either bit complexity or condition measures; these can be unbounded in the problem dimension. We achieve our upper bound by showing that the central path is well-approximated by a combinatorial proxy we call the max central path, which consists of 2n shadow vertex simplex paths. Our upper bound complements the lower bounds of Allamigeon et al. [SIAM J. Appl. Algebra Geom., 2 (2018), pp. 140-178] and Allamigeon, Gaubert, and Vandame [No self-concordant barrier interior point method is strongly polynomial, 2022], who constructed linear programs with exponential SLC. Finally, we show that each iteration of our IPM can be implemented in strongly polynomial time. Along the way, we develop a deterministic algorithm that approximates the singular value decomposition of a matrix in strongly polynomial time to high accuracy, which may be of independent interest.