Abstract:

In interior point methods, there is an inconsistency between theory and practice: fast algorithms in practice may actually render
 worse complexity bounds. We proposed a new Mehrotratype predictorcorrector interior point algorithm for linear programming. The O(nL)iteration complexity of the algorithm was given, the same as the best complexity result for any interior point method. The numerical experiments show that this algorithm has a superior practical performance.

Key words:  linear programming, interior point methods, Mehrotratype predictorcorrector algorithm, wide neighborhood algorithm, polynomial complexity