- On Mehrotra-Type Predictor-Corrector Algorithms Maziar Salahi (salahimmcmaster.ca) Jiming Peng (pengjmcmaster.ca) Tamas Terlaky (terlakymcmaster.ca) Abstract: In this paper we discuss the polynomiality of Mehrotra-type predictor-corrector algorithms. We consider a variant of the original prototype of the algorithm that has been widely used in several IPM based optimization packages, for which no complexity result is known to date. By an example we show that in this variant the usual Mehrotra-type adaptive choice of the parameter $\mu$ might force the algorithm to take many small steps to keep the iterates in a certain neighborhood of the central path, which is essential to prove the polynomiality of the algorithm. This example has motivated us to incorporate a safeguard in the algorithm that keeps the iterates in the prescribed neighborhood, while it allows us to warrantee a minimal step size. This safeguard strategy is used also when the affine scaling step performs poorly that forces the algorithm to take pure centering steps. We proved that the modified algorithm, in the worst case, will terminate after at most $\O(n^2\log\frac{(x^0)^Ts^0}{\epsilon})$ iterations. By slightly modifying the Newton system in the corrector step, we reduce the iteration complexity to $\O(n\log \frac{(x^0)^Ts^0}{n}).$ To ensure the asymptotic convergence of the algorithm, we changed Mehrotra's heuristic slightly. The new algorithms have the same iteration complexity as the previous one, but enjoy superlinear convergence rate as well. Keywords: Linear Optimization, Predictor-Corrector Method, Interior-Point-Methods, Mehrotra-Type Algorithm, Polynomial Complexity, Superlinear Convergence Category 1: Linear, Cone and Semidefinite Programming Citation: Technical Report, 2005/4\$, Advanced Optimization Lab. Department of Computing and Software, McMaster University,http://www.cas.mcmaster.ca/~oplab/publication. Download: [PDF]Entry Submitted: 03/30/2005Entry Accepted: 03/30/2005Entry Last Modified: 04/07/2005Modify/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.