On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm (Q688920)

Two versions of the `primal projective algorithm for linear programs' are given that use a weighted Karmarkar potential function. This potential is defined with respect to a strict lower bound to the optimal objective function value. The first solves the linear programming problem in the standard form of Karmarkar and the second computes a `weighted analytic center' of a certain dual polytope. For both algorithms a convergence analysis is given. A certain part of the article is devoted to the construction of a class of inner and outer ellipsoids for the dual polytope. It is shown that such a pair of homothetic dual ellipsoids can be constructed as soon as an interior feasible point sufficiently `deep' in the polytope is obtained. This approach extends results of Sonnevend.