Linear complementarity problems (LCP) generalizes 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 QP 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 posses 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.
There are still several open questions in the area of sufficient LCPs. More importantly, solution methods developed for sufficient LCPs helps us in trying to solve LCP problems with more general matrices.
e-mail: illes@math.bme.hu
homepage: https://det.math.bme.hu/illes-tibor
