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

The authors give a polynomial upper bound for the average number of turning points of the central curve used in interior point methods for solving \(P-\)matrix linear complementarity problems. The expectation is taken with respect to a sign-invariant probability distribution on the problem data. The number of turning points is intended as a measure of the complexity of the central curve followed by interior point methods. With the same technique of proof based on the Bezout's Theorem the result is extended to the average number of intersection points of the central curve with other algebraic surfaces not only describing turning points, for instance spheres centered on the origin, boxes, etc.