Polynomial time second order Mehrotra-type predictor-corrector algorithms

Salahi et al. [M. Salahi, J. Peng, T. Terlaky, On Mehrtora type predictor-corrector algorithms, Technical Report 2005/4, Advanced Optimization Lab, Department of Computing and Software, McMaster University, http://www.cas.mcmaster.ca/~oplab/publication, SIAM Journal on Optimization, submitted for publication] give a numerical example showing that Mehrotra's original predictor-corrector algorithm, which is the basis of interior point methods software packages, may be very inefficient in practice. This motivated Salahi et al. to come up with a safeguarded algorithm that enjoys a polynomial iteration complexity and is efficient in practice. Here we discuss a variation of Mehrotra's second order predictor-corrector algorithm [S. Mehrotra, On the implementation of a (primal-dual) interior point method, SIAM Journal on Optimization 2 (1992) 575-601] and use the example of Salahi et al. to show that the algorithm may have to take very small steps in order to remain in a certain neighborhood of the central path and subsequently needs excessively large number of iterations to stop. We then introduce a safeguard that guarantees a lower bound for the maximum step size in the corrector step of the algorithm and subsequently a polynomial number of iterations. A second modification of algorithm is proposed which enjoys even a better iteration complexity. Some limited encouraging computational results are reported.