The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and Zhao, namely the integral ${\int_{\nu_f}^{\nu_i} \kappa(\nu)/\nu \, d\nu}$, where $\{ w(\nu): \nu \in [\nu_f,\nu_i] \}$ is the traversed portion of the central path $\{w(\nu): \nu>0\}$ and the quantity $\kappa(\nu)$ is a certain curvature measure of the path at $w(\nu)$. The second iteration complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scaling invariant condition number $\chistarA$ associated with the LP constraint matrix $A$. In this paper, we establish a relationship between these bounds by showing that the the improper integral ${\int^{\infty}_0 \kappa(\nu)/\nu \, d \nu}$ is bounded by ${\cal O}(n^{3.5} \log(n+\chistarA))$. We also establish another geometric result about the central path showing that the points on the path with curvature larger than a given threshold value $\bar\kappa>0$ lie in ${\cal O}(n^2)$ intervals, each with logarithmic length bounded by ${\cal O}(n\log(\chistarA+n) + \log \bar\kappa^{-1})$. This result gives a rigorous geometric justification based on the curvature $\kappa(\cdot)$ of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the path consists of ${\cal O}(n^2)$ long but straight continuous parts while the remaining curved portion of the path has a “logarithmic length” bounded by ${\cal O}(n^3 \log(\chibarA+n)$, where $\chibarA \ge \chistarA$ is another (not scaling invariant) condition number associated with $A$.
Citation
manuscript, School of ISyE, Georgia Tech, Atlanta, GA 30332