International Journal of Mathematics and Mathematical Sciences
Volume 29 (2002), Issue 2, Pages 99-113

Projective algorithms for solving complementarity problems

Caroline N. Haddad1 and George J. Habetler2

1Department of Mathematics, State University of New York at Geneseo, Geneseo 14454, NY, USA
2Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy 12180, NY, USA

Received 16 February 2001

Copyright © 2002 Caroline N. Haddad and George J. Habetler. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


We present robust projective algorithms of the von Neumann type for the linear complementarity problem and for the generalized linear complementarity problem. The methods, an extension of Projections Onto Convex Sets (POCS) are applied to a class of problems consisting of finding the intersection of closed nonconvex sets. We give conditions under which convergence occurs (always in 2 dimensions, and in practice, in higher dimensions) when the matrices are P-matrices (though not necessarily symmetric or positive definite). We provide numerical results with comparisons to Projective Successive Over Relaxation (PSOR).