- A new iteration-complexity bound for the MTY predictor-corrector algorithm Renato D. C. Monteiro (monteiroisye.gatech.edu) Takashi Tsuchiya (tsuchiyasun312.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/2002Entry Accepted: 10/30/2002Entry Last Modified: 10/30/2002Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.