A polynomial primal-dual Dikin-type algorithm for linear programming

In this paper we present a new primal-dual affine scaling method for linear programming. The method yields a strictly complementary optimal solution pair, and also allows a polynomial-time convergence proof. The search direction is obtained by using the original idea of Dikin, namely by minimizing the objective function (which is the duality gap in the primal-dual case), over some suitable ellipsoid. This gives rise to completely new primal-dual affine scaling directions, having no obvious relation with the search directions proposed in the literature so far. The new directions guarantee a significant decrease in the duality gap in each iteration, and at the same time they drive the iterates to the central path. In the analysis of our algorithm we use a barrier function which is the natural primal-dual generalization of Karmarkar's potential function. The iteration bound is O(nL), which is a factor O(L) better than the iteration bound of an earlier primal-dual affine scaling method (Monteiro, Adler and Resende 1990).