GRAPHS, COPOSITIVE MATRICES, AND SUMS OF SQUARES OF POLYNOMIALS

This lecture revolves around a central open question, relevant to the computation of the stability number $$\alpha (G)$$ of a graph $$G=([n],E)$$ in discrete optimization, to the cone $$\text{COP}_n$$ of copositive matrices, and to the cone $$\Sigma$$ of sums of squares of polynomials. Consider the matrix $$M_G=\alpha (G)(I+A_G)-J$$, where $$A_G$$ is the adjacency matrix of $$G$$ and $$J$$ is the all-ones matrix, and the associated polynomial $$p_G=(x^{\circ 2})^T M_G x^{\circ 2}$$ in the squared variables $$x^{\circ 2}=(x_1^2,\ldots ,x_n^2)$$. As is well-known the matrix $$M_G$$ is copositive and thus the polynomial $$p_G$$ is globally nonnegative on $$\mathbb R^n$$. The question is whether there exists a positivity certiﬁcate in the form $$(\sum _{i=1}^nx_i^2)^r p_G \in \Sigma$$ for some integer $$r\in \mathbb N$$. De Klerk and Pasechnik (2002) conjecture that the answer is positive, in fact already for $$r=\alpha (G)-1$$.

Following Parrilo (2000) let $$\mathcal K^{(r)}_n$$ consist of all symmetric matrices $$M$$ for which the associated polynomial $$(\sum _{i=1}^nx_i^2)^r (x^{\circ 2})^T M x^{\circ 2}$$ is a sum of squares. These cones form an inner approximation hierarchy of $$\text{COP}_n$$ and they are known to cover its full interior: $\text{int}(\text{COP}_n) \subseteq \bigcup _{r\ge 0} \mathcal K^{(r)}_n\subseteq \text{COP}_n.$ The above open question thus asks whether any graph matrix $$M_G$$ belongs to some cone $$\mathcal K^{(r)}_n$$, a nontrivial question since any $$M_G$$ lies on the boundary of $$\text{COP}_n$$. As one of our new results we show that the answer is positive for the class of graphs that do not have any $$\alpha$$-critical edge, which corresponds to the case when $$p_G$$ has ﬁnitely many zeros on the unit sphere.

It is known that any $$4\times 4$$ copositive matrix belongs to $$\mathcal K^{(0)}_4$$, the dual of the cone of doubly-nonnegative matrices. We show that the union of the cones $$\mathcal K^{(r)} _n$$ does not cover $$\text{COP}_n$$ if $$n\ge 6$$. However it remains open what is the situation for $$n=5$$. What we can show is that the Horn matrix $$M_{C_5}$$ plays a crucial role: it remains only to settle whether any positive diagonal scaling of the Horn matrix belongs to some cone $$\mathcal K^{(r)}_5$$.

We will discuss old and new results around the above questions and related ones, which display a nice interplay between graph structure, optimization, copositive matrices, and real algebraic geometry.

This is based on joint works [123] with Luis Felipe Vargas (CWI, Amsterdam).

References

[1]    Monique Laurent and Luis Felipe Vargas. Finite convergence of sum-of-squares hierarchies for the stability number of a graph. SIAM J. on Optimization, to appear (arXiv:2103.01574)

[2]    Monique Laurent and Luis Felipe Vargas. Exactness of Parrilo’s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph. arXiv:2109.12876.

[3]    Monique Laurent and Luis Felipe Vargas. On the exactness of sum of squares approximation 5-dimensional copositive cone. In preparation.

CWI, Amsterdam, and Tilburg University