Optimization Online


Postponing the Choice of the Barrier Parameter in Mehrotra-Type Predictor-Corrector Algorithms

Maziar Salahi (salahim***at***mcmaster.ca)
Tama's Terlaky (terlaky***at***mcmaster.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/2005
Entry Accepted: 09/01/2005
Entry Last Modified: 09/01/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society