Interior point methods are not worse than Simplex

Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
36 Downloads (Pure)

Abstract

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound $O(2^{n}n^{15}\log n)$ for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most $O(n^{15}\log n)$ times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths. From the existence of a line segment in the wide neighborhood we derive strong implications on the structure of the corresponding segment of the central path. Our algorithm is able to detect this structure from the local geometry at the current iterate, and constructs a step direction that descends along this segment. The bound $O(n^{15}\log n)$ that applies for arbitrarily long line segments is derived from a combinatorial progress measure. Our algorithm falls into the family of layered least squares interior point methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to previous layered least squares methods that partition the kernel of the constraint matrix into coordinate subspaces, our method creates layers based on a general subspace providing more flexibility. Our result also implies the same bound on the number of iterations of the trust region interior point method by Lan, Monteiro, and Tsuchiya (SIOPT 2009).
Original languageEnglish
Title of host publication2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages267-277
Number of pages11
ISBN (Electronic)978-1-6654-5519-0
ISBN (Print)978-1-6654-5520-6
DOIs
Publication statusPublished - Oct 2022

Publication series

NameIEEE Annual Symposium on Foundations of Computer Science (FOCS)
PublisherIEEE
Number63
Volume2022
ISSN (Print)1523-8288
ISSN (Electronic)2575-8454

Keywords

  • n/a OA procedure

Fingerprint

Dive into the research topics of 'Interior point methods are not worse than Simplex'. Together they form a unique fingerprint.

Cite this