## 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.

Contact: sturm@opres.few.eur.nl