Perfect Copositive Matrices

点击翻译按钮获取中文摘要

In this project we develop a theory of perfect copositive matrices. These matrices can be used, for example, to discretize the convex cone of copositive matrices in a systematic way. This results in possible applications in copositive optimization, such as the algorithmic calculation of rational certificates for completely positive matrices. A central component of our project — and important for algorithmic applications of the new theory — is the investigation of the neighborhood graph of perfect copositive matrices. This graph appears as an edge graph of a polyhedral surface, whose facets are determined by minimal vectors of copositive matrices. For the algorithmic treatment of the neighborhood graph it is therefore essential to compute minimal vectors of copositive matrices. For this important task new approaches are developed and tested. These new algorithms for determining minimal vectors themselves have the potential for interesting future applications.As part of the project, we will develop various implementations of algorithms and compare them extensively with known approaches. Towards the end we aim to publish software that is easy to use, together with an associated data set of test instances for future research.