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(t)(k) = root x(i)(k)/s(i)(k) and v(i)(k) = root x(i)(k)s(i)(k) 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. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.