In \cite{SPT} the authors considered a variant of Mehrotra’s predictor-corrector algorithm that has been widely used in several IPMs based optimization packages. By an example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of the algorithm. This observation motivated them to incorporate a safeguard in their algorithmic scheme that gives a warranted lower bound for the maximum step size at each iteration. In this paper we propose a different approach that enables us to have control on the iterates. Our new approach is based on postponing the choice of the barrier parameter and does not require any safeguard strategy like the one in \cite{SPT}. To do so, first we fix a step size in the corrector step, then by solving a one dimensional optimization problem we estimate the barrier parameter. Finally, using the estimated barrier parameter it computes the maximum step size that can be taken and makes the next iterate. We proved that for the feasible case in the worst case, our new algorithm stops after at most $O\left(n^2\log \frac{n}{\epsilon}\right)$ iterations without any safeguard strategy. We further modified the proposed algorithm by slightly modifying the Newton system that has to be solved in the corrector step. This modified variant enjoys better iteration complexity i.e., $O\left(n\log \frac{n}{\epsilon}\right)$. The superlinear convergence of both algorithms are established. Finally, we report some limited encouraging numerical results.
Citation
Advanced Optimization Lab, McMaster University Report 2005/16