Projective Transformations for Interior Point Methods, Part II: Analysis of An Algorithm for Finding the Weighted Center of a Polyhedral System

摘要

In Part II of this study, the basic theory of Part I is applied to the problem of finding the w-center of a polyhedral system X . We present a projective transformation algorithm, analagous but more general than Karmarkar's algorithm, for finding the w-center of X . The algorithm exhibits superlinear convergence. At each iteration, the algorithm either improves the objective function (the weighted logarithmic barrier function) by a fixed amount, or at a linear rate of improvement. This linear rate of improvement increases to unity, and so the algorithm is superlinearly convergent. The algorithm also updates an upper bound on the optimal objective value of the weighted logarithmic barrier function at each iteration. The direction chosen at each iteration is shown to be positively proportional to the projected Newton direction. This has two consequences. On the theoretical side, this broadens a result of Bayer and Lagarias regarding the connection between projective transformation methods and Newton's method. In terms of algorithms it means that our algorithm specializes to Vaidya's algorithm if it is used with a line search, and so we see that Vaidya's algorithm is superlinearly convergent as well. Finally, we show how to use the algorithm to construct well-scaled containing and contained ellipsoids centered at near-optimal solutions to the w-center problem. After a fixed number of iterations, the current iterate of the algorithm can be used as an approximate w-center, and one can easily construct well-scaled containing and contained ellipsoids centered at the current iterate, whose scale factor is of the same order as for the w-center itself. Keywords: analytic center, w-center, projective transformation,Newton method, ellipsoid, linear program.