Computing certificates for complete positivity (Achill Schürmann, University of Rostock)

A key problem in computer proofs based on solutions from copositive optimization, is checking whether or not a given quadratic form is completely positive or not. In this talk we describe the first known algorithm for arbitrary rational input. It is based on a suitable adaption of Voronoi’s Algorithm and the underlying theory from positive definite to copositive quadratic forms. We observe several similarities with the classical theory, but also some differences, in particular for three and more variables. A key element and currently the main bottleneck in our algorithm is an adapted shortest vector computation, asking for all nonnegative integer vectors attaining the copositive minimum of a given copositive quadratic form.

(based on joint work with Valentin Dannenberg, Alexander Oertel, Mathieu Dutour Sikiric and Frank Vallentin)