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 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 signifiant decreased 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.