2022/06/17 by Xavier Allamigeon, Daniel Dadush, Allamigeon, Xavier +7 · 2 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Mathematical Programming #Vehicle Routing Optimization Methods
paper · doi:10.48550/arxiv.2206.08810
openalex publication_date 2022/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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(n1.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(n1.5log n). As our second contribution, we show that the SLC of any linear program is upper bounded by 2n + o(1), which implies that our IPM's iteration complexity is at most exponential. This 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, Benchimol, Gaubert, and Joswig (SIAGA 2018), and Allamigeon, Gaubert, and Vandame (STOC 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.