On the exactness of sum-of-squares approximations for the cone of 5×5 copositive matrices

We investigate the hierarchy of conic inner approximations K(r)n (r∈N) for the copositive cone COPn, introduced by Parrilo (Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, PhD Thesis, California Institute of Technology, 2001). It is known that COP4=K(0)4 and that, while the union of the cones K(r)n covers the interior of COPn, it does not cover the full cone COPn if n≥6. Here we investigate the remaining case n=5, where all extreme rays have been fully characterized by Hildebrand (The extreme rays of the 5 × 5 copositive cone. Linear Algebra and its Applications, 437(7):1538--1547, 2012). We show that the Horn matrix H and its positive diagonal scalings play an exceptional role among the extreme rays of COP5. We show that equality COP5=⋃r≥0K(r)5 holds if and only if any positive diagonal scaling of H belongs to K(r)5 for some r∈N. As a main ingredient for the proof, we introduce new Lasserre-type conic inner approximations for COPn, based on sums of squares of polynomials. We show their links to the cones K(r)n, and we use an optimization approach that permits to exploit finite convergence results on Lasserre hierarchy to show membership in the new cones.

• View at arXiv

Free Full Text ( Final Version , 268kb )

See Also
article On the exactness of sum-of-squares approximations for the cone of 5 × 5 copositive matrices M. Laurent (Monique) and L.F. Vargas (Luis)