TL;DR
This paper proves that standard interior point methods for linear programming, specifically those using log-barrier functions, are not "strongly polynomial." This means their runtime can grow exponentially with the problem size, not just the input bit length, by constructing a specific family of linear programs with this property.
What Problem Does This Paper Address?
The paper tackles a fundamental question in computational optimization: can linear programming (LP) be solved in "strongly polynomial time"? This means an algorithm's runtime should be polynomial in the number of variables and constraints, independent of the magnitude of the input numbers (bit length). While interior point methods (IPMs) are polynomial in the bit model, it was an open question whether they could achieve strong polynomiality. Specifically, the authors investigate whether the number of iterations for path-following IPMs could be bounded polynomially by the number of variables and constraints. They also address a conjecture by Deza, Terlaky, and Zinchenko regarding the "total curvature" of the central path, which serves as a measure of LP problem difficulty.
Methods
The core of the paper's methodology lies in tropical geometry. The authors construct a family of linear programs, denoted $LW_r(t)$, parameterized by $r$ and $t$. They then analyze the "central path" of these programs. The key innovation is to "tropicalize" this central path. This involves:
- Puiseux Series Field: Working with a field of generalized real Puiseux series, which allows for formal parameters like $t$ and provides a structure that behaves like real numbers but with a non-Archimedean valuation.
- Valuation Map: Applying a valuation map (similar to taking the leading term of a series) to transform classical LP objects (like central paths and polyhedra) into their "tropical" counterparts.
- Tropical Geometry Tools: Utilizing concepts like tropical polyhedra, tropical segments, and tropical barycenters to analyze the structure of the tropicalized central path.
- Metric Properties: Developing metric estimates (e.g., Hausdorff distance) to relate the behavior of the classical central path to its tropical counterpart.
- Combinatorial Analysis: The tropical approach allows for a combinatorial analysis of the central path's structure, revealing its piecewise-linear nature and the number of "turns" or segments.
This tropicalization allows them to derive combinatorial lower bounds on the number of iterations and the total curvature, which are then translated back to the original LP problem.
Datasets
Not discussed in the paper. The paper introduces a family of constructed linear programs ($LW_r(t)$) for theoretical analysis, rather than using existing datasets.
Key Insights and Ideas
- Tropicalization as a Complexity Tool: The paper demonstrates the power of tropical geometry in analyzing the worst-case complexity of algorithms. By transforming continuous geometric objects into discrete, combinatorial ones, they can derive lower bounds that are hard to obtain otherwise.
- Exponential Complexity is Real: The constructed $LW_r(t)$ family provides concrete examples showing that standard log-barrier IPMs can indeed require an exponential number of iterations. This directly disproves the possibility of strong polynomiality for this class of algorithms.
- Central Path Curvature as a Complexity Measure: The paper shows that the "total curvature" of the central path for their constructed problems grows exponentially with $r$. This disproves a conjecture about the linear boundedness of this curvature.
- Piecewise-Linear Structure: The tropical central path is shown to be piecewise linear, composed of "tropical segments." The number of these segments directly relates to the number of iterations.
- "Long and Winding" Paths: The name $LW_r(t)$ (long and winding) aptly describes the nature of the central paths constructed, which exhibit many sharp turns and a complex structure when viewed tropically.
Key Results
- Theorem A: The total curvature of the central path for the $LW_r(t)$ family is exponential in $r$ for sufficiently large $t$.
- Theorem B (Corollary 31): Any primal-dual path-following interior point algorithm using a log-barrier function that stays within a "wide neighborhood" of the central path requires an exponential number of iterations on the $LW_r(t)$ family. Specifically, the number of iterations is lower-bounded by $\Omega(2^r)$.
- Disproof of Conjecture: The results disprove the conjecture that the total curvature of the central path is linearly bounded by the number of constraints.
Limitations and Future Work
- Specific Algorithm Class: The results apply to primal-dual path-following interior point methods using log-barrier functions and staying in a "wide neighborhood" of the central path. The authors suggest that the approach might be extendable to other barrier functions or even infeasible interior point methods.
- Parameter Dependence: The exponential lower bounds are derived for specific parameter choices ($t$ sufficiently large, $\theta$ within a certain range). The exact conditions for these bounds are carefully analyzed.
- Generalization: The authors mention that their tropicalization approach is likely applicable to other problems in computational complexity, particularly those sensitive to input bit length. They also suggest exploring tropical curvature for arbitrary paths and tropical hypersurfaces.
- Experimental Verification: The paper includes a section on "Combinatorial Experiments" that provides hints and observations for small values of $r$, suggesting that the constructed polytopes exhibit properties consistent with the theoretical findings, though these are not formal proofs.
Summary updated