zbMATH — the first resource for mathematics

Solution of general linear complementarity problems via nondifferentiable concave minimization. (English) Zbl 0895.90167
Summary: Finite termination, at a 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 solved without failure 80 consecutive cases of the LCP formulation of the knapsack feasibilty problem, ranging in size between 10 and 3000.

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)