Matrix copositivity has an important theoretical background. Over the last decades, the use of algorithms to check copositivity has made a big progress. Methods are based on 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 unit simplex and illustrate with numerical instances that exploiting monotonicity in algorithms may speed up the search. For face-based algorithms the question is what traversal through the face graph of the unit simplex is more appropriate for which matrix instance.
Citation
Universidad de Málaga, 3 April 2020
Article
View On monotonicity and search traversal in copositivity detection algorithms