O(nρL)-iteration and O(n3L)-operation potential reduction algorithms for linear programming

AbstractIn this paper we propose two potential reduction algorithms, which we call Algorithm 1 and Algorithm 2, for linear programming. Algorithm 1 has parameters θ in the potential function and β which determines a step size. Suppose that θ=n1−σ and β=0.2n0.5-ϱ for 0.5⩽θ⩽ϱ⩽1. Then Algorithm 1 requires at most O(nϱL) iterations and O(n3L) arithmetic operations in total. If we take θ=n and β=0.2, Algorithm 1 is similar to Ye's primal form algorithm. Algorithm 2 has a parameter θ=n1−σ for σ∈[0.5, 1]. It requires at most O(nσL) iterations and O(n3L) arithmetic operations in total. If θ=n, Algorithm 2 is similar to the long step algorithm of Anstreicher and Bosch