On Mehrotra-Type Predictor-Corrector Algorithms
Authors:
- M. SalahiMSM. Salahi
- J. PengJPJ. Peng
- T. TerlakyTTT. Terlaky
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 18 (4) , 1377-1397
Abstract
In this paper we discuss the polynomiality of a feasible version of Mehrotra's predictor-corrector algorithm whose variants have been widely used in several interior point method (IPM)-based optimization packages. A numerical example is given that shows that the adaptive choice of centering parameter and correction terms in this algorithm may lead to small steps being taken in order to keep the iterates in a large neighborhood of the central path, which is important for proving polynomial complexity properties of this method. Motivated by this example, we introduce a safeguard in Mehrotra's algorithm that keeps the iterates in the prescribed neighborhood and allows us to obtain a positive lower bound on the step size. This safeguard strategy is also used when the affine scaling direction performs poorly. We prove that the safeguarded algorithm will terminate after at most ${\cal{O}}(n^2{\rm log} (x^0)^Ts^0/\epsilon)$ iterations. By modestly modifying the corrector direction, we reduce the iteration complexity to ${\cal{O}}(n {\rm log} (x^0)^Ts^0/\epsilon).$ To ensure fast asymptotic convergence of the algorithm, we changed Mehrotra's updating scheme of the centering parameter slightly while keeping the safeguard. The new algorithms have the same order of iteration complexity as the safeguarded algorithms but enjoy superlinear convergence as well. Numerical results using the McIPM and LIPSOL software packages are reported.
Keywords
This publication has 24 references indexed in Scilit:
- Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central pathOptimization Methods and Software, 2005
- Convergence Conditions and Krylov Subspace--Based Corrections for Primal-Dual Interior-Point MethodSIAM Journal on Optimization, 2005
- The Mizuno–Todd–Ye algorithm in a larger neighborhood of the central pathEuropean Journal of Operational Research, 2002
- Complexity of Predictor-Corrector Algorithms for LCP Based on a Large Neighborhood of the Central PathSIAM Journal on Optimization, 1999
- PCx: an interior-point code for linear programmingOptimization Methods and Software, 1999
- Solving large-scale linear programs by interior-point methods under the Matlab∗Environment†Optimization Methods and Software, 1998
- An Asymptotical $O(\sqrt{n} L)$-Iteration Path-Following Linear Programming Algorithm That Uses Wide NeighborhoodsSIAM Journal on Optimization, 1996
- The Mehrotra Predictor-Corrector Interior-Point Method As a Perturbed Composite Newton MethodSIAM Journal on Optimization, 1996
- A New Infinity-Norm Path Following Algorithm for Linear ProgrammingSIAM Journal on Optimization, 1995
- On finding a vertex solution using interior point methodsLinear Algebra and its Applications, 1991