- Postponing the Choice of the Barrier Parameter in Mehrotra-Type Predictor-Corrector Algorithms Maziar Salahi (salahimmcmaster.ca) Tama's Terlaky (terlakymcmaster.ca) Abstract: 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. Keywords: Linear Optimization, Predictor-Corrector Method, Mehrotra-Type Algorithm, Polynomial Complexity, Superlinear Convergence. Category 1: Linear, Cone and Semidefinite Programming Citation: Advanced Optimization Lab, McMaster University Report 2005/16 Download: [Postscript]Entry Submitted: 09/01/2005Entry Accepted: 09/01/2005Entry Last Modified: 09/01/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.