Copositivity tests based on the Linear Complementarity Problem

Citation:
Brás, C., G. Eichfelder, and J. Júdice. "Copositivity tests based on the Linear Complementarity Problem." Computational Optimization and Applications. 63.2 (2016): 461-493.

Abstract:

We present copositivity tests based on new necessary and sufficient conditions which require the solution of linear complementarity problems (LCP). We propose methodologies involving Lemke’s method, an enumerative algorithm and a linear mixed-integer programming formulation to solve the required LCPs. Moreover, we discuss a new necessary condition for (strict) copositivity based on solving a linear program, which can be used as a preprocessing step. The algorithms with these three different variants are thoroughly applied to test matrices from the literature and to max-clique instances with matrices of order up to 496×496. We compare our procedures with three other copositivity tests from the literature as well as with a general global optimization solver. The numerical results are very promising and equally good and in many cases better than the results reported elsewhere.

Related External Link