A New Wide Neighborhood Primal-dual Predictor-corrector Interior-point Algorithm for Linear Optimization

We present a new primal-dual predictor-corrector interior-point algorithm for linear optimization problems. In each iteration of this algorithm, we use the new wide neighborhood proposed by Darvay and Takács. Our algorithm computes the predictor direction, then the predictor direction is used to obtain the corrector direction. We show that the duality gap reduces in both predictor and corrector steps. Moreover, we conclude that the complexity bound of this algorithm coincides with the best-known complexity bound obtained for small neighborhood algorithms.

Keywords:

Linear optimization , Interior-point methods , Predictor-corrector methods , Wide neighborhood