Back

G-89-26

On the Computation of Weighted Analytic Centers and Dual Ellipsoids with the Projective Algorithm

and

BibTeX reference

The primal projective algorithm for linear programs with unknown optimal objective function value is extended to the case where one uses a weighted Karmarkar potential function. This potential is defined with respect to a strict lower bound to the optimum. It is first shown that the minimization of this potential when the lower bound is kept fixed, yields a primal and a dual solution; the dual solution is shown to be the weighted analytic center of a certain dual polytope, or equivalently the analytic center of a similar polytope where the defining inequalities are repeated a number of times equal to their respective weights. The projective algorithm is then presented in two versions: the first one solves, with a given precision threshold, the linear programming problem; the other version algorithm computes the weighted analytic center. An analysis of convergence showing the polynomiality of these algorithms is developed. Finally one exhibits a pair of homothetic dual ellipsoids that generalizes results obtained by Sonnevend, Todd and Ye.

, 23 pages