Theorem 6.6, p. 26 — min P_nmq ≥ L_nmq, and min P_nmq ≥ u_r(γ)ᵀ H_r(γ)⁻¹ u_r(γ) when q = m = 2r

Let $n, m, q \in \mathbb N$ with $m \le n+1$ and $m \le q \le 2n-2$, let $\gamma_1, \dots, \gamma_{m-1} \in \mathbb R$, and let $\mathrm P_{nmq}$ be the problem

with optimal value $\min \mathrm P_{nmq}$ (an infimum, possibly $\pm\infty$). Then:

1. (a) $\min \mathrm P_{nmq} \ge \mathrm L_{nmq}$, where $\mathrm L_{nmq}$ is the value of the semidefinite program (6.5).
2. (b) If $q = m = 2r$, set $\gamma_0 = n$, let $H_r(\gamma) = (\gamma_{i+j-2})_{1\le i,j\le r}$ and $u_r(\gamma)^T = (\gamma_r, \dots, \gamma_{2r-1})$, so that $H_{r+1}(s) = \begin{pmatrix} H_r(\gamma) & u_r(\gamma) \\ u_r(\gamma)^T & s_{2r}\end{pmatrix}$. If $H_r(\gamma)$ is positive definite, then

Part (a) says that a single semidefinite constraint on an $n\times n$ Hankel matrix gives a lower bound on a symmetric polynomial optimization problem whose size does not grow with the degree; part (b) gives the bound in closed form in the even case.

Formalization Note The paper prints the bound of (b) as $u_r(\gamma)^T H_r(\gamma) u_r(\gamma)$, which is false: for $n = 2$, $m = q = 2$, $\gamma_1 = 1$ one has $\min \mathrm P = 1/2$ (at $x = (1/2,1/2)$) while $u^T H_1 u = n\gamma_1^2 = 2$. The paper's own proof (Schur complement on $H_{r+1}(s)$) gives the inverse, which is stated here. The hypothesis that $H_r(\gamma)$ is positive definite is added so that the inverse exists. All optimal values are infima in the extended reals. The bound $q \le 2n-2$ uses natural-number subtraction; for $n \le 1$ it forces $q = 0$.