A fast symmetric penalty algorithm for the linear complementarity problem

In an earlier paper, the authors presented a new parameterization algorithm for the the linear complementarity problem. The trajectory associated with this parameterization is distinguished by a naturally defined starting point and by a piecewise characterization as a fractional polynomial function of a single parameter. In order to follow this trajectory, however one needs to isolate roots of polynomials - a computationally expensive operation. In this paper, we present an algorithm in which we parameterize one dimension at a time. This results in polynomials of degree one, which allows trivial root isolation. The algorithm stays unaffected in other key respects. For example, the average number of pieces in the trajectory is still O(n(2)), where n is the dimension of the problem space. This implies that our algorithm is competitive, in an average sense, to Lemke's method.