An interior point method, based on rank-1 updates, for linear programming

We propose a polynomial time primal-dual potential reduction algorithm for linear programming. The algorithm generates sequences d^k and v^k rather than a primal-dual interior point (x^k,s^k), where d^k_i = √x^k_i/s^k_i and v^k_i = √x^k_is^k_i for i = 1, 2, . . . , n. Only one element of d^k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal-dual iterates x^k and s^k are not needed explicitly in the algorithm, whereas d^k and v^k are iterated so that the interior primal-dual solutions can always be recovered by aforementioned relations between (x^k,s^k) and (d^k,v^k) with improving primal-dual potential function values. Moreover, no approximation of d^k is needed in the computation of projection directions.