Polynomial Primal-Dual Dikin-Type Algorithm for Linear Programming

摘要

In the paper the authors 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 the algorithm the authors 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. (Copyright (c) 1993 by Faculty of Technical Mathematics and Informatics, Delft, The Netherlands.)