Maintaining Closeness to the Analytic Center of a Polytope by Perturbing Added Hyperplanes

摘要

In this work we consider a region R in R~n given by a finite number of linear inequalities and having nonempty interior. We assume a point x~° is given, which is close in certain norm to the analytic center of R, and that a new linear inequality is added to those defining R. It is constructively shown how to obtain a perturbation of the right-hand side of this inequality such that the point x~° is still close, in the same norm, to the analytic center of this perturbed polytope. This fact plays a central role in interior point postoptimality techniques for linear programming involving methods of centers.