A PREDICTOR CORRECTOR INFEASIBLE-INTERIOR-POINT ALGORITHM FOR LINEAR-PROGRAMMING

We present a predictor-corrector algorithm for solving a primal-dual pair of linear programming problems. The algorithm starts from an infeasible interior point and it solves the pair in O(nL) interations, where n is the number of variables and L is the size of the problems. At each iteration of the algorithm, the predictor step decreases the infeasibility and the corrector step decreases the duality gap. The main feature of the algorithm is the simplicity of the predictor step, which performs a line search along a fixed search direction computed at the beginning of the algorithm. The corrector step uses a procedure employed in a feasible-interior-point algorithm. The proof of polynomiality is also simple.