sum-of-squares polynomial – Optimization Online

Semidefinite hierarchies for diagonal unitary invariant bipartite quantum states

Published: 2025/12/18

Semi-definite Programming Completely positive matrix, copositive matrix, DPS hierarchy, entanglement, Moment approach, Quantum bipartite states, semidefinite programming, Separable states, sparsity, sum-of-squares polynomial

We investigate questions about the cone $\mathrm{SEP}_n$ of separable bipartite states, consisting of the Hermitian matrices acting on $\mathbb{C}^n\otimes\mathbb{C}^n$ that can be written as conic combinations of rank one matrices of the form $xx^*\otimes yy^*$ with $x,y\in\mathbb{C}^n$. Bipartite states that are not separable are said to be entangled. Detecting quantum entanglement is a fundamental task … Read more

Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert

Published: 2023/08/19, Updated: 2024/04/28

Basic Sciences Applications, Global Optimization Applications, Semi-definite Programming polynomial models, semidefinite, sum-of-squares polynomial, symbolic regression

The discovery of scientific formulae that parsimoniously explain natural phenomena and align with existing background theory is a key goal in science. Historically, scientists have derived natural laws by manipulating equations based on existing knowledge, forming new equations, and verifying them experimentally. In recent years, data-driven scientific discovery has emerged as a viable competitor in … Read more

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

Published: 2021/10/12

Monique Laurent

Luis Felipe Vargas

Approximation Algorithms, Semi-definite Programming alpha-critical graph, copositive matrix, semidefinite programming, Shor relaxation, stable set problem, sum-of-squares polynomial

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

Published: 2021/03/17, Updated: 2021/03/24

Monique Laurent

Luis Felipe Vargas

Combinatorial Optimization, Linear, Cone and Semidefinite Programming $\alphahBccritical graph, copositive programming, finite convergence, lasserre hierarchy, motzkin-straus formulation, polynomial optimization, semidefinite programming, stable set problem, standard quadratic programming, sum-of-squares polynomial

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

Published: 2016/03/10

Etienne de Klerk

Monique Laurent

Roxana Hess

Semi-definite Programming box-constrained global optimization, generalized eigenvalue problem, jackson kernel, polynomial optimization, semidefinite programming, sum-of-squares polynomial

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