A new predictor–corrector algorithm for linear programming

Recently, we have introduced a new class of search directions for linear optimization problems. Using a particular element of this class, we have obtained a new polynomial-time algorithm. The self-dual embedding technique can be used to obtain a starting interior point. The algorithm can be generalized in such a way that follows a weighted path. However, predictor–corrector type algorithms are the most efficient, from the implementation point of view. Therefore, in this paper we develop a new predictor–corrector algorithm for solving linear programming problems. We prove that this algorithm finds a solution with given precision in polynomial time.