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

Abstract

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
JournalCentral European Journal of Operations Research
DOIs
Publication statusE-pub ahead of print - 6 Mar 2021

Keywords

  • Copositive matrix
  • Face
  • Monotone
  • Standard simplex

Fingerprint

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