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/2005
Entry Accepted: 03/30/2005
Entry Last Modified: 04/07/2005

Modify/Update this entry