  


A new iterationcomplexity bound for the MTY predictorcorrector algorithm
Renato D. C. Monteiro (monteiroisye.gatech.edu) Abstract: In this paper we present a new iterationcomplexity bound for the MizunoToddYe predictorcorrector (MTY PC) primaldual interiorpoint 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 PC algorithm started from a wellcentered interiorfeasible solution with duality gap $n \mu_0$ finds an interiorfeasible 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))$ iterationcomplexity bound for the MTY PC algorithm to find a primaldual 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 iterationcomplexity bound for the MTY PC algorithm which depends linearly on $L$ instead of $\log L$. Keywords: Interiorpoint algorithms, primaldual algorithms, pathfollowing Category 1: Linear, Cone and Semidefinite Programming Citation: Research Memorandum No.856 The Institute of Statistical Mathematics 467 MinamiAzabu, Minatoku, Tokyo 1068569 Japan October, 2002 Download: [Postscript][PDF] Entry Submitted: 10/30/2002 Modify/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  