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

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

## Jean-Louis Goffin et Jean-Philippe Vial

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