×

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.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite