Analytic centers and repelling inequalities

Analytic centers and repelling inequalities

0.00 Avg rating0 Votes
Article ID: iaor20032061
Country: Netherlands
Volume: 143
Issue: 2
Start Page Number: 268
End Page Number: 290
Publication Date: Dec 2002
Journal: European Journal of Operational Research
Authors: , ,
Keywords: interior point methods, complementarity
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.