On monotonicity and search strategies in face-based copositivity detection algorithms

B.G. Tóth*, E.M.T. Hendrix, L.G. Casado

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)


Over the last decades, algorithms have been developed for checking copositivity of a matrix. Methods are based on several principles, such as spatial branch and bound, transformation to Mixed Integer Programming, implicit enumeration of KKT points or face-based search. Our research question focuses on exploiting the mathematical properties of the relative interior minima of the standard quadratic program (StQP) and monotonicity. We derive several theoretical properties related to convexity and monotonicity of the standard quadratic function over faces of the standard simplex. We illustrate with numerical instances up to 28 dimensions the use of monotonicity in face-based algorithms. The question is what traversal through the face graph of the standard simplex is more appropriate for which matrix instance; top down or bottom up approaches. This depends on the level of the face graph where the minimum of StQP can be found, which is related to the density of the so-called convexity graph.

Original languageEnglish
Pages (from-to)1071-1092
JournalCentral European Journal of Operations Research
Issue number3
Early online date6 Mar 2021
Publication statusPublished - Sep 2022


  • Copositive matrix
  • Face
  • Monotone
  • Standard simplex


Dive into the research topics of 'On monotonicity and search strategies in face-based copositivity detection algorithms'. Together they form a unique fingerprint.

Cite this