On the expected number of linear complementarity cones intersected by random and semi-random rays

Lemke's algorithm for the linear complementarity problem follows a ray which leads from a certain fixed point (traditionally, the point (1,, 1)^T) to the point given in the problem. The problem also induces a set of 2ⁿ cones, and a question which is relevant to the probabilistic analysis of Lemke's algorithm is to estimate the expected number of times a (semi-random) ray intersects the boundary between two adjacent cones. When the problem is sampled from a spherically symmetric distribution this number turns out to be exponential. For ann-dimensional problem the natural logarithm of this number is equal to ln()n+o(n), where is approximately 1.151222. This number stands in sharp contrast with the expected number of cones intersected by a ray which is determined by two random points (call itrandom). The latter is only (n/2)+1. The discrepancy between linear behavior (under the random assumption) and exponential behavior (under the semi-random assumption) has implications with respect to recent analyses of the average complexity of the linear programming problem. Surprisingly, the semi-random case is very sensitive to the fixed point of the ray, even when that point is confined to the positive orthant. We show that for points of the form (, ²,, ⁿ)^T the expected number of facets of cones cut by a semi-random ray tends to 1/8n²+3/8n when tends to zero.This work was done while the author was visiting Stanford University and XEROX-PARC and was supported in part by the National Science Foundation under grants MCS-8300984, ECS-8218181 and ECS-8121741.