  


Postponing the Choice of the Barrier Parameter in MehrotraType PredictorCorrector Algorithms
Maziar Salahi (salahimmcmaster.ca) Abstract: In \cite{SPT} the authors considered a variant of Mehrotra's predictorcorrector 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, PredictorCorrector Method, MehrotraType 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/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  