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^{n(1 + o(1))}\), 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.

• View at Publisher

Full Text ( Author Manuscript , 1mb )