A Modified Layered-Step Interior-Point Algorithm for Linear Programming

The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrix A. The main drawback of the algorithm is the use of an unknown big constant XA in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when an well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primmal-dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye.