A predictor-corrector infeasible-interior-point algorithm for linear programming

A predictor-corrector infeasible-interior-point algorithm for linear programming

0.00 Avg rating0 Votes
Article ID: iaor1996319
Country: Netherlands
Volume: 16
Issue: 2
Start Page Number: 61
End Page Number: 66
Publication Date: Sep 1994
Journal: Operations Research Letters
Authors:
Keywords: interior point methods
Abstract:

The paper presents 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) iterations, 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.

Reviews

Required fields are marked *. Your email address will not be published.