Analytic Centers and Repelling Inequalities
R. J. Caron, H. J. Greenberg, A. G. Holder
The new concepts of repelling inequalities, repelling
paths, and prime analytic centers are introduced. A
repelling path is a generalization of the analytic
central path for linear programming, and we show
that this path has a unique limit. Furthermore, this
limit is the prime analytic center if the set of
repelling inequalities contains only those constraints
that ``shape'' the polytope. Because we allow lower
dimensional polytopes, the proof techniques are
non-standard and follow from data perturbation
analysis. This analysis overcomes the difficulty
that analytic centers of lower dimensional polytopes
are not necessarily continuous with respect to the
polytope's data representation. A second concept
introduced here is that of the ``prime analytic
center,'' in which we establish its uniqueness in
the absence of redundant inequalities. Again, this
is well known for full dimensional polytopes, but
it is not immediate for lower dimensional polytopes
because there are many different data representations
of the same polytope, each without any redundant
inequalities. These two concepts combine when we
introduce ways in which repelling inequalities can
interact.
CCM No. 142, Center for Computational Mathematics,
University of Colorado at Denver, CO 1999
Contact: [email protected]