Exactness of Parrilo’s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph

De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour … Read more

Finite convergence of sum-of-squares hierarchies for the stability number of a graph

We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp.875–892], who conjectured convergence to $\alpha(G)$ in $r=\alpha(G) -1$ steps. Even the weaker conjecture claiming finite convergence is still open. … Read more

Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It … Read more