Sufficient linear complementarity problems: algorithms and computational results

Linear complementarity problems (LCP) generalize some fundamental problems of mathematical optimization like linear programming (LP) problem, linearly constrained quadratic programming (LQP) problem and some other. It admits an enormous number of applications in economics, engineering, science, and many other fields. After all these, it is not surprising that LCPs are usually NP-complete problems (S.J. Chung, 1989).

The three most significant classes of algorithms for solving LCP problems are: pivot algorithms (PA), interior point algorithms (IPA) and continuation methods. Because, both PA and IPA have been developed earlier for LP and LQP problems it is quite natural idea to test them on LCP problems, as well.

Concept of sufficient matrices, as generalization of positive semidefinite matrices, has been introduced 30 years ago by Cottle et al. (1989). LCPs with sufficient matrices possess many important properties, like the solution set is convex and polyhedral; guarantees the finiteness of PAs and (pseudo) polynomial behaviour of the IPAs.

The largest matrix class where the interior point algorithms (IPA) are polynomial is the class of P*(κ)-matrices, for given nonnegative real parameter κ. The union for all possible κ parameters of P*(κ)-matrices forms the class of P*-matrices. This class of matrices has been introduced by Kojima et al. in 1991. Known IPAs for LCPs with P*(κ)-matrices under the interior point assumption, possess polynomial iteration complexity depending on the problem size n, parameter κ and the bit length L of the rational data of the LCP.

After all of these, it is a natural question: What is the relation between the sufficient and P*-matrices? Väliaho (1996) proved that the P*-matrices are exactly those which are sufficient. Unfortunately, there are two important, negative results related to sufficient matrices. P. Tseng (2000) proved that decision problem related to the membership of matrices for P0- and column sufficient matrices are all co-NP-complete. While de Klerk and Eisenberg-Nagy showed that there exists such P*(κ)-matrices for which the κ value is exponential in the size n of the problem.

Furthermore, for sufficient LCPs, it is meaningful to introduce dual LCP problem and it can be proved that from sufficient primal- and dual LCP problem, exactly one has solution, that is an interesting, nice and (quite) new generalization of the old Farkas’ lemma.

More importantly, solution methods developed for sufficient LCPs helps us in trying to solve LCPs with more general matrices.

After a short overview of some developments in the last 30 years in sufficient LCPs, we are focusing on recent algorithmic and computational results using a new generation of IPAs.

Share this Event