A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms (Q930345)

The paper studies a primal-dual path following linear programming (LP) algorithm, the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm. The MTY P-C algorithm has been associated with two iteration-complexity bounds, one expressed in terms of an integral of a certain curvature of the central path of the LP, and another depending on a certain scale-invariant condition number associated with the LP constraint matrix. The further study of these bounds is among the goals of this paper that aims to relate them. More specifically, the authors of the paper establish a relationship between the two bounds of the MTY P-C algorithm by showing that the first one can be majorised by the second one. Moreover, the paper studies the geometrical structure of the LP central path and establishes a geometric result about it, which provides a rigorous justification for a claim made by Vavasis and Ye that the central path consists mainly of long but straight continuous parts, while its remaining curved part is relatively short.