  


On MehrotraType PredictorCorrector Algorithms
Maziar Salahi (salahimmcmaster.ca) Abstract: In this paper we discuss the polynomiality of Mehrotratype predictorcorrector algorithms. We consider a variant of the original prototype of the algorithm that has been widely used in several IPM based optimization packages, for which no complexity result is known to date. By an example we show that in this variant the usual Mehrotratype adaptive choice of the parameter $\mu$ might force the algorithm to take many small steps to keep the iterates in a certain neighborhood of the central path, which is essential to prove the polynomiality of the algorithm. This example has motivated us to incorporate a safeguard in the algorithm that keeps the iterates in the prescribed neighborhood, while it allows us to warrantee a minimal step size. This safeguard strategy is used also when the affine scaling step performs poorly that forces the algorithm to take pure centering steps. We proved that the modified algorithm, in the worst case, will terminate after at most $\O(n^2\log\frac{(x^0)^Ts^0}{\epsilon})$ iterations. By slightly modifying the Newton system in the corrector step, we reduce the iteration complexity to $\O(n\log \frac{(x^0)^Ts^0}{n}).$ To ensure the asymptotic convergence of the algorithm, we changed Mehrotra's heuristic slightly. The new algorithms have the same iteration complexity as the previous one, but enjoy superlinear convergence rate as well. Keywords: Linear Optimization, PredictorCorrector Method, InteriorPointMethods, MehrotraType Algorithm, Polynomial Complexity, Superlinear Convergence Category 1: Linear, Cone and Semidefinite Programming Citation: Technical Report, 2005/4$, Advanced Optimization Lab. Department of Computing and Software, McMaster University,http://www.cas.mcmaster.ca/~oplab/publication. Download: [PDF] Entry Submitted: 03/30/2005 Modify/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  