We propose a polynomial time primal-dual potential reduction algorithm for linear programming. Unlike any other interior point method, the new algorithm is based on a rank-one updating scheme for sequentially computing the projection matrices. For a standard linear programming problem, the number of operations required is [TeX: ${\\cal O}(mn)$] per main iteration and the overall computational complexity is [TeX: ${\\cal O}(mn^{2.5}L)$].

, ,
Econometric Institute Research Papers
Erasmus School of Economics

Sturm, J. F., & Zhang, S. (1995). An interior point method, based on rank-one updates, for linear programming (No. EI 9546-/A). Econometric Institute Research Papers. Retrieved from http://hdl.handle.net/1765/1360