An algorithm for the linear complementarity problem with upper and lower bounds (Q1106738)

We adapt the octahedral simplicial algorithm for solving systems of nonlinear equations to solve the linear complementarity problem with upper and lower bounds. The proposed algorithm generates a piecewise linear path from an arbitrarily chosen point \(z^ 0\) to a solution point. This path is followed by linear programming pivot steps in a system of n linear equations, where n is the size of the problem. The starting point \(z^ 0\) is left in the direction of one of the \(2^ n\) vertices of the feasible region. The ray along which \(z^ 0\) is left depends on the sign pattern of the function value at \(z^ 0\). The sign pattern of the linear function and the location of the points in comparison with \(z^ 0\) completely govern the path of the algorithm.