Optimization Online


A new iteration-complexity bound for the MTY predictor-corrector algorithm

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

Abstract: In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program $\min\{c^Tx : Ax=b, \, x \ge 0\}$ with decision variable $x \in \Re^n$, we show that the MTY P-C algorithm started from a well-centered interior-feasible solution with duality gap $n \mu_0$ finds an interior-feasible solution with duality gap less than $n \eta$ in ${\cal O}( n^2 \log ( \log (\mu_0/\eta)) + n^{3.5}\log(\chistarA + n) )$ iterations, where $\chistarA$ is a scaling invariant condition number associated with the matrix $A$. More specifically, $\chistarA$ is the infimum of all the conditions numbers ${\bar \chi}_{AD}$, where $D$ varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an ${\cal O}(n^{3.5}L_A + n^2 \log L))$ iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where $L_A$ and $L$ are the input sizes of the matrix $A$ and the data $(A, b, c)$, respectively. This contrasts well with the classical iteration-complexity bound for the MTY P-C algorithm which depends linearly on $L$ instead of $\log L$.

Keywords: Interior-point algorithms, primal-dual algorithms, path-following

Category 1: Linear, Cone and Semidefinite Programming

Citation: Research Memorandum No.856 The Institute of Statistical Mathematics 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569 Japan October, 2002

Download: [Postscript][PDF]

Entry Submitted: 10/30/2002
Entry Accepted: 10/30/2002
Entry Last Modified: 10/30/2002

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