An infeasible-interior-point potential-reduction algorithm for linear programming

This paper studies a new potential-function and an infeasible-interior-point method based on this function for the solution of linear programming problems. This work is motivated by the apparent gap between the algorithms with the best worst-case complexity and their most successful implementations. For example, analyses of interior-point algorithms are usually carried out by imposing several regularity assumptions on the problem, but implementations can solve problems which do not satisfy these assumptions. Furthermore, most state-of-the-art implementations incorporate heuristic tricks, but these modifications are rarely addressed in the theoretical analysis of the algorithms. The method described here and its analysis have the flexibility to integrate any heuristic technique for implementation while maintaining the important polynomial complexity feature.