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^ki = √(x^ki/s^ki) and v^ki = √(x^kis^ki) 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.