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.