Groupe d’études et de recherche en analyse des décisions

Symmetric tensor approximation hierarchies for the completely positive cone

Hongbo Dong University of Iowa, États-Unis

We construct two approximation hierarchies for the completely positive cone based on symmetric tensors. We show that one hierarchy corresponds to dual cones of a known polyhedral approximation hierarchy for the copositive cone, and the other hierarchy corresponds to dual cones of a known semidefinite approximation hierarchy for the copositive cone. As an application, we consider a class of bounds on the stability number of a graph obtained from the polyhedral approximation hierarchy, and we construct a primal optimal solution with its tensor lifting for each such linear program. We also discuss several potential research directions based on this work.