Groupe d’études et de recherche en analyse des décisions


Short Steps with Kamarkar's Projective Algorithm for Linear Programming


In this paper we propose a path-following, or short-step, version of Karmarkar's algorithm for the primal and for the dual problems. We show it to converge in iterations, when the first term of Karmarkar's potential function is given the weight , with , and iterations if . Two proofs of convergence are given, one based on duality gap reductions, the other on potential reductions. The weighted version of the standard projective algorithm is also analyzed. It is interpreted as a max-step algorithm. It is known to converge in at most iterations. We study here the reduction of the duality gap when an updating of the lower bound is performed. We show it to be of a multiplicative factor at most equal to , where is a fixed parameter in the algorithm. We deduce from it that the total number of updates of the lower bound in the weighted projective algorithm is at most for .

, 24 pages