ON THE COMPUTATION OF WEIGHTED ANALYTIC CENTERS AND DUAL ELLIPSOIDS WITH THE PROJECTIVE ALGORITHM

The primal projective algorithm for linear programs with unknown optim al objective function value is extended to the case where one uses a w eighted Karmarkar potential function. This potential is defined with r espect to a strict lower bound to the optimum. The minimization of thi s potential when the lower bound is kept fixed, yields a primal and a dual feasible solution. The dual solution is the weighted analytic cen ter of a certain dual polytope. Finally one exhibits a pair of homothe tic dual ellipsoids that extends results obtained by Sonnevend, Todd, Ye, Freund and Anstreicher.