Copositivity tests based on the linear complementarity problem

Carmo Brás, Gabriele Eichfelder, Joaquim Júdice

Research output: Contribution to journalArticle

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)461-493
Number of pages33
JournalComputational Optimization And Applications
Volume63
Issue number2
DOIs
Publication statusPublished - 1 Mar 2016

Keywords

  • Complementarity problems
  • Conic optimization
  • Copositivity
  • Linear programming

Fingerprint Dive into the research topics of 'Copositivity tests based on the linear complementarity problem'. Together they form a unique fingerprint.

Cite this