An Interior Point Method, Based on Rank-One Updates, For Linear Programming

Jos F. Sturm and Shuzhong Zhang

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_i^k = \sqrt{x_i^k/s_i^k}$ and $v_i^k = \sqrt{x_i^k s_i^k}$ for $i=1,2,\ldots,n$. Only one element of $d^k$ is changed in each iteration, so that the work per iteration is bounded by $ O(mn) $. This feature makes the algorithm different from other partial updating schemes, where all entries of $d^k$ change in each iteration, and partial updates are made to an {\em approximation} of $d^k$ in order to compute search directions.

Report 9546/A, Econometric Institute, Erasmus University Rotterdam, the Netherlands (1995) 12 pages.