A probabilistic analysis of a measure of combinatorial complexity for the central curve

A probabilistic analysis of a measure of combinatorial complexity for the central curve

0.00 Avg rating0 Votes
Article ID: iaor20011032
Country: Germany
Volume: 87
Issue: 1
Start Page Number: 177
End Page Number: 187
Publication Date: Jan 2000
Journal: Mathematical Programming
Authors: ,
Abstract:

We investigate certain combinatorial properties of the central curve associated with interior point methods for linear optimization. We define a measure of complexity for the curve in terms of the number of turns, or changes of direction, that it makes in a geometric sense, and then perform an average case analysis of this measure for P-matrix linear complementarity problems. We show that the expected number of nondegenerate turns taken by the central curve is bounded by n2 − n, where the expectation is taken with respect to a sign-invariant probability distribution on the problem data. As an alternative measure of complexity, we also consider the number of times the central curve intersects with a wide class of algebraic hypersurfaces, including such objects as spheres and boxes. As an example of the results obtained, we show that the primal and dual variables in each coordinate of the central curve cross each other at most once, on average. As a further example, we show that the central curve intersects any sphere centered at the origin at most twice, on average.

Reviews

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