We investigate the hierarchy of conic inner approximations Kn(r) (r∈N) for the copositive cone COPn, introduced by Parrilo (2000) [22]. It is known that COP4=K4(0) and that, while the union of the cones Kn(r) 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 (2012) [12]. 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≥0K5(r) holds if and only if every positive diagonal scaling of H belongs to K5(r) 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 Kn(r), and we use an optimization approach that permits to exploit finite convergence results on Lasserre hierarchy to show membership in the new cones.

, ,
Linear Algebra and its Applications
Polynomial Optimization, Efficiency through Moments and Algebra
CWI management

Laurent, M., & Vargas, L. (2022). On the exactness of sum-of-squares approximations for the cone of 5 × 5 copositive matrices. Linear Algebra and its Applications, 651, 26–50. doi:10.1016/j.laa.2022.06.015