Optimization Online


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

Renato D. C. Monteiro (monteiro***at***isye.gatech.edu)
Takashi Tsuchiya (tsuchiya***at***sun312.ism.ac.jp)

Abstract: 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$.

Keywords: Interior-point algorithms, primal-dual algorithms, path-following, central path, layered least squares steps, condition number, polynomial complexity, crossover events, scale-invariance, predictor-corrector, affine scaling, strongly polynomial, linear programming, curvature.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Linear, Cone and Semidefinite Programming

Citation: manuscript, School of ISyE, Georgia Tech, Atlanta, GA 30332

Download: [Compressed Postscript][PDF]

Entry Submitted: 09/30/2005
Entry Accepted: 09/30/2005
Entry Last Modified: 09/30/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society