A rank one updating interior algorithm for linear programming

Abstract EN

In this paper we propose an interior point algorithm for linear programming which requires 0(n3L) arithmetic operations.

Since Karmarkar presented a new polynomial time algorithm for linear programming, many interior point algorithms have been developed.

Karmarkar’s algorithm requires at most O(nL) iterations and 0(n15) arithmetic operations on average in each iteration.

The algorithm proposed in this paper requires 0(nL) iterations like Karmarkar’s algorithm, but it only requires 0(n2) arithmetic operations in each iteration.

As for the revised simplex algorithm, we store an inverse matrix in the algorithm and update it by at most rank one at each iteration.