On a class of least-element complementarity problems

The present paper studies the linear complementarity problem of finding vectorsx andy inR₊ⁿ such thatc + Dx + y 0,b – x 0 andx^T(c + Dx + y) = y^T(b – x) = 0 whereD is aZ-matrix andb > 0. Complementarity problems of this nature arise, for example, from the minimization of certain quadratic functions subject to upper and lower bounds on the variables. Two least-element characterizations of solutions to the above linear complementarity problem are established first. Next, a new and direct method to solve this class of problems, which depends on the idea of least-element solution is presented. Finally, applications and computational experience with its implementation are discussed.Research partially supported by the National Science Foundation Grant MCS 71-03341 A04 and the Air Force Office of Scientific Research Contract F 44620 14 C 0079.