A New Wide Neighborhood Primal-Dual Predictor-Corrector Interior-Point Method for Linear Programming

摘要

In this article, we present a new predictor-corrector interior-point method, based on a wide neighborhood of the central path, for linear programming problems. In the corrector step of the proposed method, we derive the step size and corrector directions that guarantee that each iteration lies in a wide neighborhood of the central path. We also prove that the algorithm has O (root n log(x(0))(T)s(0)/epsilon) iteration complexity, which coincides with the best bound derived for linear programming problems.