%A O. L. Mangasarian
%T Solution of General Linear Complementarity Problems via Nondifferentiable Concave Minimization
%D November 1996
%R 96-10
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X Finite termination, at point satisfying the minimum principle
necessary optimality condition, is established for a stepless
(no line search) successive linearization algorithm (SLA) for
minimizing a nondifferentiable concave function on a polyhedral set.
The SLA is then applied to the
general linear complementarity problem (LCP), formulated as
minimizing a piecewise-linear concave error function on
the usual polyhedral feasible region defining the LCP. When the
feasible region is nonempty, the concave error function always has
a global minimum at a vertex, and the minimum is zero if and
only if the LCP is solvable. The SLA terminates at
a solution or stationary point of the problem in a finite
number of steps. A special case of the proposed algorithm
\cite{man:95} solved without failure 80 consecutive cases of the LCP
formulation of the knapsack feasibilty problem,
ranging in size between 10 and 3000.