The purpose of this study is to broaden the scope of projective transformation methods in mathematical programming, both in terms of theory and algorithms. The paper starts by generalizing the concept of the analytic center of a polyhedral system of constraints to the w-center of a polyhedral system, which stands for weighted center, where there is a positive weight on the logarithmic barrier term for each inequality constraint defining the polyhedron X. It proves basic results regarding contained and containing ellipsoids centered at the w-center of the system X. The paper next shifts attention to projective transformations, and it exhibits an elementary projective transformation that transforms the polyhedron X to another polyhedron Z, and that transforms the current interior point to the w-center of the transformed polyhedron Z. The paper works throughout with a polyhedral system of the most general form, namely both inequality and equality constraints. This theory is then applied to the problem of finding the w-center of a polyhedral system X. The paper presents a projective transformation algorithm, which is an extension of Karmarkar’s algorithm, for finding the w-center of the system X. At each iteration, the algorithm exhibits either a fixed constant objective function improvement, or converges superlinearly to the optimal solution. The algorithm produces upper bounds on the optimal value at each iteration. The direction chosen at each iteration is shown to be a positively scaled Newton direction. This broadens a result of Bayer and Lagarias regarding the connection between projective transformation methods and Newton’s method. Furthermore, the algorithm specializes to Vaidya’s algorithm when used with a line-search, and so shows that Vaidya’s algorithm is superlinearly convergent as well. Finally the paper shows how the algorithm can be used to construct well-scaled containing and contained ellipsoids at near-optimal solutions to the w-center problem.
