2
$\begingroup$

This is a crosspost of mathoverflow/345282

I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy: $$\inf_{x\in\mathbb{R}^n}\quad p(x)$$ where $p$ is a polynomial of even degree degree, $d=2\ell$.

  1. The approach of Lasserre, which relies on Putinar's Nullstellensatz, requires to restrict to an archimedean domain, which can be done by adding the constraint $\|x\|^2\leq a$ for a sufficiently large $a$. This approach is described e.g. in Theorem 5.5. of this lecture, and yields the hierarchy:

$$ \begin{align}\tag{$P_r$} \sup &\quad \lambda\\ s.t. &\quad p(x)-\lambda = q(x) + \sigma(x) (a-\sum_i x_i^2)\\ &\quad \text{for some SOS polynomials $p$,$\sigma$}\\ &\quad \text{of degree at most $2(\ell+r)$ and $2(\ell+r-1)$, respectively.} \end{align} $$

  1. The approach of Reznick, which is described e.g. in this lecture, and consists in expressing $p(x)-p^*$ as a rational function (the ratio between a SOS polynomial and $(1+\|x\|^2)^r$ for increasing values of $r$):

$$ \begin{align}\tag{$Q_r$} \sup &\quad \lambda\\ s.t. &\quad (1+\sum_i x_i^2)^r \ (p(x)-\lambda) = q(x)\\ &\quad \text{for some SOS polynomials $p$ of degree $2(\ell+r).$} \end{align} $$

So my question is: Are these two approaches related / equivalent? Is it known if one approach converges faster than the other one?

$\endgroup$