A potential-reduction variant of Renegar's short-step path-following method for linear programming (Q811094): Difference between revisions

The authors propose a new polynomial potential-reduction method for linear programming. This method can be interpreted as a large-step pathfollowing method. A line search is performed along the Newton direction with respect to \textit{J. Renegar}'s strictly convex potential function [Math. Program, Ser. A 40, No.1, 59-93 (1988; Zbl 0654.90050)] if the iterate is far away from the central trajectory. In the other case the lower bound for the optimal value will be updated. Depending on this updating scheme, the iteration bound is proved to be O(\(\sqrt{n}L)\) or O(nL). The method differs from the previous potential- reduction method in the choice of the potential function and the search direction.