Linear optimization with cones of moments and nonnegative polynomials

Abstract

Let $\mathcal {A}$ be a finite subset of $\mathbb {N}^n$ and $\mathbb {R}[x]_{\mathcal {A}}$ be the space spanned by monomials $x^\alpha$ with $\alpha \in \mathcal {A}$. Let $K$ be a compact semialgebraic set of $\mathbb {R}^n$ such that a polynomial in $\mathbb {R}[x]_{\mathcal {A}}$ is positive on $K$. Denote by $\fancyscript{P}_{\mathcal {A}}(K)$ the cone of polynomials in $\mathbb {R}[x]_{\mathcal {A}}$ that are nonnegative on $K$. The dual cone of $\fancyscript{P}_{\mathcal {A}}(K)$ is $\fancyscript{R}_{\mathcal {A}}(K)$, the set of all truncated moment sequences in $\mathbb {R}^{\mathcal {A}}$ that admit representing measures supported in $K$. First, we study geometric properties of the cones $\fancyscript{P}_{\mathcal {A}}(K)$ and $\fancyscript{R}_{\mathcal {A}}(K)$ (like interiors, closeness, duality, memberships), and construct a convergent hierarchy of semidefinite relaxations for each of them. Second, we propose a semidefinite algorithm for solving linear optimization problems with the cones $\fancyscript{P}_{\mathcal {A}}(K)$ and $\fancyscript{R}_{\mathcal {A}}(K)$, and prove its asymptotic and finite convergence. Third, we show how to check whether $\fancyscript{P}_{\mathcal {A}}(K)$ and $\fancyscript{R}_{\mathcal {A}}(K)$ intersect affine subspaces; if they do, we show how to get a point in the intersections; if they do not, we prove certificates for the empty intersection.

1 Introduction

Let $\mathbb {N}$ (resp., $\mathbb {R}$) be the set of nonnegative integers (resp., real numbers), and let $\mathbb {R}[x]:=\mathbb {R}[x_1,\ldots ,x_n]$ be the ring of real polynomials in $x:=(x_1,\ldots ,x_n)$. For $\alpha :=(\alpha _1, \ldots ,\alpha _n) \in \mathbb {N}^n$, denote $x^\alpha := x_1^{\alpha _1}\cdots x_n^{\alpha _n}$ and $|\alpha |:=\alpha _1+\cdots +\alpha _n$. Let $\mathbb {R}[x]_d$ be the set of polynomials in $\mathbb {R}[x]$ with degrees $\le d$, and $K \subseteq \mathbb {R}^n$ be a set. Denote

$$\begin{aligned} \fancyscript{P}_d(K) =\{ p \in \mathbb {R}[x]_d: \, p(u) \ge 0 \,\,\forall \, u \in K \}, \end{aligned}$$

the cone of polynomials in $\mathbb {R}[x]_d$ that are nonnegative on $K$. Let

$$\begin{aligned} \mathbb {N}_d^n=\{\alpha \in \mathbb {N}^n: |\alpha | \le d\}. \end{aligned}$$

The dual space of $\mathbb {R}[x]_d$ is $\mathbb {R}^{\mathbb {N}_d^n}$, the space of truncated moment sequences (tms’) of degree $d$. A tms $y = (y_\alpha ) \in \mathbb {R}^{\mathbb {N}_d^n}$ defines a linear functional acting on $\mathbb {R}[x]_d$ as

$$\begin{aligned} \langle p, y \rangle := \sum _{|\alpha |\le d} p_\alpha y_\alpha \quad \text{ for } \text{ all } \quad p = \sum _{|\alpha |\le d} p_\alpha x^\alpha . \end{aligned}$$

It is said to admit a $K$-measure $\mu$ (i.e., $\mu$ is a Borel measure supported in $K$) if $y_\alpha = \int x^\alpha \mathtt {d}\mu$ for all $\alpha \in \mathbb {N}_d^n$. Such $\mu$ is called a K-representing measure for $y$. In applications, we are often interested in finitely atomic measures, i.e., their supports are finite sets. Denote by $\delta _u$ the Dirac measure supported at $u$. A measure $\mu$ is called r-atomic if $\mu = \lambda _1 \delta _{u_1} + \cdots + \lambda _r \delta _{u_r}$ with each $\lambda _i >0$ and $u_i \in \mathbb {R}^n$. Let $meas(y,K)$ be the set of all $K$-measures admitted by $y$. Denote

$$\begin{aligned} \fancyscript{R}_d(K) = \{ y \in \mathbb {R}^{\mathbb {N}_d^n} : \, meas(y,K) \ne \emptyset \}. \end{aligned}$$

When $K$ is compact, $\fancyscript{R}_d(K)$ is the dual cone of $\fancyscript{P}_d(K)$ (cf. Tchakaloff [44] or Laurent [28, Section 5.2]).

Linear optimization problems with cones $\fancyscript{P}_d(K)$ and $\fancyscript{R}_d(K)$ have wide applications. For instance, the minimum value of a polynomial $f \in \mathbb {R}[x]_d$ on $K$ can be found by maximizing $\gamma$ subject to $f-\gamma \in \fancyscript{P}_d(K)$; the corresponding dual problem is minimizing a linear function over the cone $\fancyscript{R}_d(K)$ (cf. Lasserre [19]). Generalized problems of moments (GPMs), proposed by Lasserre [22], are optimizing linear moment functionals over the set of measures supported in a given set and satisfying some linear constraints. GPMs are equivalent to linear optimization problems with the cone $\fancyscript{R}_d(K)$. Lasserre [22] proposed semidefinite relaxations for solving GPMs. We refer to [12, 25, 27, 28, 37, 38] for moment and polynomial optimization problems. Semidefinite programs are also very useful in representing convex sets and convex hulls, like in [10, 11, 13–15, 23, 24, 30, 43], and in solving polynomial equations, like in [20, 21, 29].

Motivations In some applications and mathematical problems, we do not have all entries of a truncated moment sequence, or we only require partial entries of a tms to satisfy certain properties. For instance, does there exist a tms $y$ that admits a measure supported in the circle $x_1^2+x_2^2=1$ and satisfy the linear equations

$$\begin{aligned} y_{22} = y_{40}+y_{04} = y_{60}+y_{06} =1\,? \end{aligned}$$

(1.1)

This is a moment problem, but it only involves five moments $y_{22}, y_{40}, y_{04}, y_{60}, y_{06}$. As we will see in Example 5.4, such a tms $y$ does not exist.

The above motivates us to consider more general settings of moment problems. Sometimes, we need to work in the space of incomplete truncated moment sequences. This leads to the $\mathcal {A}$-truncated $K$-moment problem ($\mathcal {A}$-TKMP), proposed and studied in [36]. Let $\mathcal {A}\subseteq \mathbb {N}_d^n$ be a subset. The space $\mathbb {R}^{\mathcal {A}}$ is the set of all partially truncated moment sequences, which only have moments indexed by $\alpha \in \mathcal {A}$. An element in $\mathbb {R}^{\mathcal {A}}$ is called an $\mathcal {A}$-truncated moment sequence ($\mathcal {A}$-tms). A basic concern for $\mathcal {A}$-TKMP is: does an $\mathcal {A}$-tms have a $K$-representing measure? This issue was discussed in [36]. A generalization of this question is the moment completion problem (MCP): given an $\mathcal {A}$-tms $y$, can we extend it to a tms $z \in \fancyscript{R}_d(K)$ such that it satisfies some properties?

For the above observations, we consider generalizations of the cones $\fancyscript{R}_d(K)$ and $\fancyscript{P}_d(K)$. Let $\mathcal {A}$ be a finite set in $\mathbb {N}^n$, and $\mathbb {R}[x]_{\mathcal {A}} := \text{ span }\{x^\alpha : \, \alpha \in \mathcal {A}\}$. The dual space of $\mathbb {R}[x]_{\mathcal {A}}$ is $\mathbb {R}^{\mathcal {A}}$. Define $\deg (\mathcal {A}) :=\max \{ |\alpha |: \, \alpha \in \mathcal {A}\}$. The $K$-representing measures for an $\mathcal {A}$-tms $y$ and the set $meas(y,K)$ can be defined same as before. Denote

$$\begin{aligned}\begin{array}{rcl} \fancyscript{P}_{\mathcal {A}}(K) &{}=&{} \{ p \in \mathbb {R}[x]_{\mathcal {A}}: p(u) \ge 0 \, \forall \, u \in K \}, \\ \fancyscript{R}_{\mathcal {A}}(K) &{}=&{} \{ y \in \mathbb {R}^{\mathcal {A}}: \, meas(y,K) \ne \emptyset \}. \end{array} \end{aligned}$$

Clearly, if $\mathcal {A}=\mathbb {N}_d^n$, then $\fancyscript{P}_{\mathcal {A}}(K)=\fancyscript{P}_d(K)$ and $\fancyscript{R}_{\mathcal {A}}(K) = \fancyscript{R}_d(K)$. An $\mathcal {A}$-tms $y \in \fancyscript{R}_d(K)$ if and only if it admits a $r$-atomic $K$-measure with $r\le |\mathcal {A}|$ (cf. [36, Proposition 3.3]).

The $\mathcal {A}$-TKMP has applications in solving moment problems with noncompact sets like $\mathbb {R}^n$. A classical moment problem is checking the membership in $\fancyscript{R}_d(\mathbb {R}^n)$. This question is harder than other moment problems because $\mathbb {R}^n$ is noncompact. However, it can be transformed to a compact moment problem via homogenization (cf. [9]). Note that a tms in $\mathbb {R}^{\mathbb {N}_d^n}$ can be thought of as an $\mathcal {A}$-tms in $\mathbb {R}^{\mathbb {N}_d^{n+1}}$ with $\mathcal {A}= \{ \beta \in \mathbb {N}^{n+1}: |\beta | = d\}$. Then, under some general assumptions, $y\in \fancyscript{R}_d(\mathbb {R}^n)$ if and only if $y$, as an $\mathcal {A}$-tms in $\mathbb {R}^{\mathcal {A}}$, belongs to $\fancyscript{R}_{\mathcal {A}}(\mathbb {S}^n)$ where $\mathbb {S}^n = \{ \tilde{x} \in \mathbb {R}^{n+1}: \, \Vert \tilde{x} \Vert _2 =1 \}$ is the $n$-dimensional unit sphere. We refer to [9] for more details. The latter question is an $\mathcal {A}$-TKMP with the compact set $\mathbb {S}^n$, and it can be solved by the method in [36].

The $\mathcal {A}$-TKMP has applications in sums of even powers (SOEP) of real linear forms. A form (i.e., a homogeneous polynomial) $f \in \mathbb {R}[x]_d$ ($d$ is even) is said to be SOEP if there exist $L_1,\ldots , L_r \in \mathbb {R}[x]_1$ such that $f = L_1^d+\cdots + L_r^d$ (cf. [41]). Let $Q_{n,d}$ be the cone of all SOEP forms of degree $d$. Each $f$ can be written uniquely as

$$\begin{aligned} f = \sum _{ \begin{array}{c} \alpha = (\alpha _1,\ldots , \alpha _n) \in \mathbb {N}^n \\ |\alpha | =d \end{array} } \left( {\begin{array}{c}d\\ \alpha _1,\ldots ,\alpha _n\end{array}}\right) \check{f}_\alpha x^\alpha . \end{aligned}$$

So, $f$ can be identified as an $\mathcal {A}$-tms $\check{f} \in \mathbb {R}^\mathcal {A}$ with $\mathcal {A}=\{\alpha \in \mathbb {N}^n: |\alpha |=d\}$. Indeed, $f \in Q_{n,d}$ if and only if $\check{f} \in \fancyscript{R}_{\mathcal {A}}(\mathbb {S}^{n-1})$ (cf. [36, 41]). Its dual cone $\fancyscript{P}_{\mathcal {A}}(K)$ is $P_{n,d}$, the cone of nonnegative forms in $n$ variables and of degree $d$. So, checking SOEP forms is an $\mathcal {A}$-TKMP with the compact set $\mathbb {S}^{n-1}$.

Another application of $\mathcal {A}$-TKMP is about completely positive (CP) matrices. A symmetric matrix $C \in \mathbb {R}^{n\times n}$ is CP if $C = u_1 u_1^T + \cdots + u_ru_r^T$ for $u_1,\ldots , u_r \in \mathbb {R}_+^n$ (the nonnegative orthant). Each symmetric matrix can be thought of an $\mathcal {A}$-tms in $\mathbb {R}^{\mathcal {A}}$ with $\mathcal {A}=\{\alpha \in \mathbb {N}^n: |\alpha |=2\}$. It can be shown that $C$ is CP if and only if $C$, as an $\mathcal {A}$-tms, belongs to $\fancyscript{R}_{\mathcal {A}}(K)$ with $K=\{x\in \mathbb {R}_+^n:\, x_1+\cdots +x_n=1\}$ (cf. [36]). This is also an $\mathcal {A}$-TKMP with a compact set. The dual cone is $\fancyscript{P}_{\mathcal {A}}(K)$, the cone of $n\times n$ copositive matrices. (A symmetric matrix $B$ is copositive if $x^TBx \ge 0$ for all $x \ge 0$.) We refer to [2, 8] for copositive and CP matrices. An important question is the CP-completion problem is: given a partial symmetric matrix $A$ (i.e., only its partial entries are known), we want to assign values to its unknown entries so that $A$ is CP. This problem is recently investigated by Zhou and Fan [45]. They formulated the CP-completion problem as an $\mathcal {A}$-TKMP.

Contributions Assume $\mathcal {A}\subseteq \mathbb {N}^n$ is finite and $K$ is a semialgebraic set as

$$\begin{aligned} K = \left\{ x\in \mathbb {R}^n :\, h(x) = 0, g(x) \ge 0 \right\} \!, \end{aligned}$$

(1.2)

defined by two polynomial tuples $h=(h_1,\ldots , h_{m_1})$ and $g=(g_1,\ldots , g_{m_2})$. Assume $K$ is compact and $\mathbb {R}[x]_{\mathcal {A}}$ contains a polynomial that is positive on $K$. In the recent work [36] by the author, a method is given for checking whether or not a given $\mathcal {A}$-tms $y\in \mathbb {R}^{\mathcal {A}}$ belongs to the cone $\fancyscript{R}_{\mathcal {A}}(K)$. In particular, by the method in [36], we can check whether or not a given form $f \in \mathbb {R}[x]_d$ ($d$ is even) is a sum of even powers of real linear forms, and we can check whether or not a given symmetric matrix is completely positive. In [36], the $\mathcal {A}$-tms $y$ is assumed to be known, i.e., all the entries $y_\alpha$ ($\alpha \in \mathcal {A}$) are given. However, in some applications, we often do not know all the moment values $y_\alpha$, but only know they satisfy some linear equations. For instance, how do we check whether or not there exists an $\mathcal {A}$-tms, which admits a measure supported in the circle $x_1^2+x_2^2=1$ and satisfies the linear equations (1.1)? In such occasions, we often need to know whether or not there exists $y \in \fancyscript{R}_{\mathcal {A}}(K)$ satisfying the given equations. Such questions were not discussed in [36].

Considering the above, we study more general linear optimization problems with the cone $\fancyscript{R}_{\mathcal {A}}(K)$. That is, we discuss how to minimize a linear objective function in $y \in \mathbb {R}^{\mathcal {A}}$, subject to linear equations in $y$ and the membership constraint $y \in \fancyscript{R}_{\mathcal {A}}(K)$. If the objective does not depend on $y$ (i.e., it is a constant), then the problem is reduced to checking whether or not there exists $y \in \fancyscript{R}_{\mathcal {A}}(K)$ satisfying a set of linear equations. This is a feasibility question. Linear optimization problems with the cone $\fancyscript{P}_{\mathcal {A}}(K)$ will also be studied.

First, we study properties of the cones $\fancyscript{P}_\mathcal {A}(K)$ and $\fancyscript{R}_\mathcal {A}(K)$. We characterize their interiors, prove their closeness and dual relationship, i.e., $\fancyscript{R}_\mathcal {A}(K)$ is the dual cone of $\fancyscript{P}_\mathcal {A}(K)$. We construct a convergent hierarchy of semidefnite relaxations for each of them. This will be shown in Sect. 3.

Second, we study how to solve linear optimization problems with the cones $\fancyscript{P}_\mathcal {A}(K)$ and $\fancyscript{R}_\mathcal {A}(K)$. A semidefinite algorithm is proposed for solving them. Its asymptotic and finite convergence are proved. A stopping criterion is also given. This will be shown in Sect. 4.

Third, we study how to check whether or not an affine subspace intersects the cone $\fancyscript{P}_\mathcal {A}(K)$ or $\fancyscript{R}_\mathcal {A}(K)$. If they intersect, we show how to find a point in the intersection. If they do not, we prove certificates for the empty inter-section. This will be shown in Sect. 5.

We begin with a review of some basics in the field in Sect. 2.

2 Preliminaries

Notation For $t\in \mathbb {R}$, $\lceil t\rceil$ (resp., $\lfloor t\rfloor$) denotes the smallest integer not smaller (resp., the largest integer not greater) than $t$. For $k \in \mathbb {N}$, denote $[k]:=\{1,\ldots ,k\}$. For a tms $z$, denote by $z|_{\mathcal {A}}$ the subvector of $z$ whose indices are in $\mathcal {A}$. When $\mathcal {A}=\mathbb {N}_d^n$, we simply denote $z|_d := z|_{\mathbb {N}_d^n}$. For a set $S \subseteq \mathbb {R}^n$, $|S|$ denotes its cardinality, and $int(S)$ denotes its interior. The superscript $^T$ denotes the transpose of a matrix or vector. For $u\in \mathbb {R}^N$ and $r \ge 0$, denote $\Vert u \Vert _2 := \sqrt{u^Tu}$ and $B(u,r) :=\{x\in \mathbb {R}^n \mid \Vert x-u\Vert _2 \le r\}$. For a polynomial $p\in \mathbb {R}[x]$, $\Vert p\Vert _2$ denotes the $2$-norm of the coefficient vector of $p$. For a matrix $A$, $\Vert A\Vert _F$ denotes its Frobenius norm. If a symmetric matrix $X$ is positive semidefinite (resp., definite), we write $X\succeq 0$ (resp., $X\succ 0$).

2.1 Riesz functionals, localizing matrices and flatness

Let $\mathcal {A}\subseteq \mathbb {N}^n$. An $\mathcal {A}$-tms $y$ defines a Riesz functional $\fancyscript{L}_y$ acting on $\mathbb {R}[x]_{\mathcal {A}}$ as

$$\begin{aligned} \fancyscript{L}_y \left( \sum _{\alpha \in \mathcal {A}} p_\alpha x^\alpha \right) := \sum _{\alpha \in \mathcal {A}} p_\alpha y_\alpha . \end{aligned}$$

Denote $\langle p, y \rangle := \fancyscript{L}_y(p)$ for convenience. We say that $\fancyscript{L}_y$ is K-positive if

$$\begin{aligned} \fancyscript{L}_y(p) \ge 0 \quad \forall \, p \in \fancyscript{P}_{\mathcal {A}}(K), \end{aligned}$$

and $\fancyscript{L}_y$ is strictly $K$-positive if

$$\begin{aligned} \fancyscript{L}_y(p) > 0 \quad \forall \, p \in \fancyscript{P}_{\mathcal {A}}(K): \, p|_K \not \equiv 0. \end{aligned}$$

As is well known, $\fancyscript{L}_y$ being $K$-positive is a necessary condition for $y$ to admit a $K$-measure. The reverse is also true if $K$ is compact and $\mathbb {R}[x]_{\mathcal {A}}$ is K-full (i.e., there exists $p\in \mathbb {R}[x]_{\mathcal {A}}$ such that $p>0$ on $K$) (cf. [9, Theorem 2.2]). We refer to the “Appendix” for how to check whether $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full or not.

For $q\in \mathbb {R}[x]_{2k}$, define $L_{q}^{(k)}(z)$ to be the symmetric matrix such that

$$\begin{aligned} \fancyscript{L}_z(qp^2) \, = \, p^T \left( L_{q}^{(k)}(z) \right) p \quad \forall p \in \mathbb {R}[x]: \, \deg (qp^2) \le 2k. \end{aligned}$$

(2.1)

(For convenience, we still use $p$ to denote the vector of coefficients of a polynomial $p$, indexed by monomial powers $\alpha \in \mathbb {N}^n$.) The matrix $L_{q}^{(k)}(z)$ is called the $k$th order localizing matrix of $q$ generated by $z$. When $q=1$, the matrix

$$\begin{aligned} M_k(z) := L_{q}^{(k)}(z) \end{aligned}$$

is called the $k$th order moment matrix of $z$. The rows and columns of $L_{q}^{(k)}(z)$ are indexed by $\alpha \in \mathbb {N}^n$. We refer to [25, 28] for moment and localizing matrices.

Let $K$ be as in (1.2) and $g_0=1$. A necessary condition for $z \in \fancyscript{R}_{2k}(K)$ is

$$\begin{aligned} L_{h_i}^{(k)}(z) = 0 \, ( i =1,\ldots , m_1), \quad L_{g_j}^{(k)}(z) \succeq 0 \, ( j =0,1,\ldots , m_2). \end{aligned}$$

(2.2)

(Cf. [7, 36].) Define the integer $d_K$ as ($h_i$, $g_j$ are from (1.2))

$$\begin{aligned} d_K := \max _{i \in [m_1], j \in [m_2]} \{1, \lceil \deg (h_i)/2 \rceil , \lceil \deg (g_j)/2 \rceil \} . \end{aligned}$$

(2.3)

In addition to (2.2), if $z$ also satisfies the rank condition

$$\begin{aligned} \text{ rank }\, M_{k-d_K}(z) = \text{ rank }\, M_k(z), \end{aligned}$$

(2.4)

then $z$ admits a unique $K$-measure, which is finitely atomic (cf. Curto and Fialkow [7]). For convenience, throughout the paper, we simply say $z$ is flat if (2.2) and (2.4) hold for $z$. For a flat tms, its finitely atomic representing measure can be found by solving some eigenvalue problems (cf. Henrion and Lasserre [17]). Flatness is very useful for solving truncated moment problems, as shown by Curto and Fialkow [5–7]. A nice exposition for flatness can also be found in Laurent [26].

For $z\in \mathbb {R}^{\mathbb {N}_{2k}^n}$ and $y\in \mathbb {R}^{\mathcal {A}}$, if $z|_{\mathcal {A}} = y$, we say that $z$ is an extension of $y$, or equivalently, $y$ is a truncation of $z$. Clearly, if $z$ is flat and $y=z|_\mathcal {A}$, then $y$ admits a $K$-measure. In such case, we say $z$ is a flat extension of $y$. Thus, the existence of a $K$-representing measure for $y$ can be determined by investigating whether $y$ has a flat extension or not. This approach has been exploited in [16, 36].

2.2 Ideals, quadratic modules and positive polynomials

A subset $I \subseteq \mathbb {R}[x]$ is called an ideal if $I + I \subseteq I$ and $I \cdot \mathbb {R}[x] \subseteq I$. For a tuple $p=(p_1,\ldots ,p_m)$ of polynomials in $\mathbb {R}[x]$, denote by $I(p)$ the ideal generated by $p_1,\ldots , p_m$, which is the set $p_1 \mathbb {R}[x] + \cdots + p_m \mathbb {R}[x]$. A polynomial $f$ is called a sum of squares (SOS) if there exist $f_1,\ldots ,f_k \in \mathbb {R}[x]$ such that $f=f_1^2+\cdots +f_k^2$. The cone of all SOS polynomials in $n$ variables and of degree $d$ is denoted by $\Sigma _{n,d}$. We refer to Reznick [40] for a survey on SOS polynomials.

Let $h=(h_1,\ldots ,h_{m_1})$ and $g=(g_1,\ldots ,g_{m_2})$ be as in (1.2). Denote

$$\begin{aligned} I_{\ell }(h)&= h_1 \mathbb {R}[x]_{\ell -\deg (h_1)} + \cdots + h_{m_1} \mathbb {R}[x]_{\ell -\deg (h_{m_1})},\end{aligned}$$

(2.5)

$$\begin{aligned} Q_k(g)&= \Sigma _{n,2k} + g_1 \Sigma _{n,2k-\deg (g_1)} + \cdots + g_{m_2} \Sigma _{n,2k-\deg (g_{m_2})}. \end{aligned}$$

(2.6)

Clearly, $I(h) = \cup _{k\in \mathbb {N}} I_{2k}(h)$. The union $Q(g):= \cup _{k\in \mathbb {N}} Q_k(g)$ is called the quadratic module generated by $g$. Clearly, if $f\in I(h) + Q(g)$, then $f|_K \ge 0$. The converse is also true if $p|_K >0$ and $I(h)+Q(g)$ is archimedean (i.e., there exists $R>0$ such that $R-\Vert x\Vert _2^2 \in I(h) + Q(g)$). This is called Putinar’s Positivstellensatz.

Theorem 2.1

(Putinar, [39]) Let $K$ be as in (1.2). Suppose $I(h)+Q(g)$ is archimedean. If $f\in \mathbb {R}[x]$ is positive on $K$, then $f\in I(h) + Q(g)$.

Let $h$ and $g$ be as in (1.2). Denote

$$\begin{aligned} \Phi _k(g)&:= \left\{ \left. w \in \mathbb {R}^{ \mathbb {N}_{2k}^n } \right| L_{g_j}^{(k)}(w) \succeq 0, \,\,\, j=0,1,\ldots , m_2 \right\} \end{aligned}$$

(2.7)

$$\begin{aligned} E_k(h)&:= \left\{ \left. w \in \mathbb {R}^{ \mathbb {N}_{2k}^n } \right| L_{h_i}^{(k)}(w) = 0, \ \,\, \, i=1,\ldots ,m_1 \right\} . \end{aligned}$$

(2.8)

The set $I_{2k}(h)+Q_k(g)$ is dual to $\Phi _k(g) \cap E_k(h)$ (cf. [25, 28, 36]), i.e.,

$$\begin{aligned} \langle p, z \rangle \ge 0 \qquad \forall \, p \in I_{2k}(h)+Q_k(g), \, \, \forall \, z \in \Phi _k(g) \cap E_k(h). \end{aligned}$$

(2.9)

3 Properties of $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$

This section studies geometric properties of the cones $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$.

3.1 Interiors, closedness and duality

Recall that $\mathbb {R}[x]_{\mathcal {A}}$ is K-full if there exists $p \in \mathbb {R}[x]_{\mathcal {A}}$ such that $p>0$ on $K$. The interiors of $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$ can be characterized as follows.

Lemma 3.1

Let $K \subseteq \mathbb {R}^n$ be a nonempty compact set. Suppose $\mathcal {A}\subseteq \mathbb {N}^n$ is finite and $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full. Then we have:

• (i) A polynomial $f \in \mathbb {R}[x]_{\mathcal {A}}$ lies in the interior of $\fancyscript{P}_{\mathcal {A}}(K)$ if and only if $f>0$ on $K$.

• (ii) An $\mathcal {A}$-tms $y \in \mathbb {R}^{\mathcal {A}}$ lies in the interior of $\fancyscript{R}_{\mathcal {A}}(K)$ if and only if the Riesz functional $\fancyscript{L}_y$ is strictly $K$-positive.

Proof

(i) If $f>0$ on $K$, then $f \in \text{ int }\big (\fancyscript{P}_{\mathcal {A}}(K) \big )$. This is because $f + q > 0$ on $K$ for all $q \in \mathbb {R}[x]_\mathcal {A}$ with sufficiently small coefficients (the set $K$ is compact). Conversely, suppose $f \in \text{ int }\big (\fancyscript{P}_{\mathcal {A}}(K) \big )$. Since $\mathbb {R}[x]_\mathcal {A}$ is $K$-full, there exists $p \in \mathbb {R}[x]_\mathcal {A}$ with $p>0$ on $K$. Then $f - \epsilon p \in \fancyscript{P}_{\mathcal {A}}(K)$ for some $\epsilon >0$. So, $f \ge \epsilon p > 0$ on $K$.

(ii) Let $\tau$ be a probability measure on $\mathbb {R}^n$ whose support equals $K$. (Because $K$ is nonempty and compact, such a measure always exists, as shown in Rogers [42].) For all $p \in \fancyscript{P}_{\mathcal {A}}(K)$, $p|_K \not \equiv 0$ if and only if $\int p \mathtt {d}\tau >0$. Let

$$\begin{aligned} z = \int [x]_{\mathcal {A}} \mathtt {d} \tau \in \mathbb {R}^\mathcal {A}, \quad \fancyscript{P}_{\mathcal {A}}(K,\tau ) = \left\{ p \in \fancyscript{P}_{\mathcal {A}}(K):\, \int p \mathtt {d} \tau = 1 \right\} \!. \end{aligned}$$

(The symbol $[x]_{\mathcal {A}}$ denotes the vector of monomials $x^\alpha$ with $\alpha \in \mathcal {A}$.) Note that an $\mathcal {A}$-tms $w$ is $K$-positive (resp., strictly $K$-positive) if and only if $\fancyscript{L}_w(p) \ge 0$ (resp., $>0$) for all $p \in \fancyscript{P}_{\mathcal {A}}(K,\tau )$. So, $z$ is strictly $K$-positive.

$``\Rightarrow ''$ Suppose $y \in int (\fancyscript{R}_{\mathcal {A}}(K))$. Then $w:=y-\epsilon z \in \fancyscript{R}_{\mathcal {A}}(K)$ for some $\epsilon >0$ and

$$\begin{aligned} \fancyscript{L}_y(p) = \fancyscript{L}_w(p) + \epsilon \fancyscript{L}_{z}(p) \ge \epsilon \fancyscript{L}_{z}(p) > 0 \end{aligned}$$

for all $p \in \fancyscript{P}_{\mathcal {A}}(K,\tau )$. So, $\fancyscript{L}_y$ is strictly $K$-positive.

$``\Leftarrow ''$ Suppose $\fancyscript{L}_y$ is strictly $K$-positive. The set $\fancyscript{P}_{\mathcal {A}}(K,\tau )$ is compact. Let

$$\begin{aligned} \epsilon&= \min \left\{ \fancyscript{L}_y(p) :\, p \in \fancyscript{P}_{\mathcal {A}}(K,\tau ) \right\} > 0,\\ M&= \max \left\{ |\langle z, p \rangle | :\, z \in \mathbb {R}^{\mathcal {A}}, \Vert z\Vert _2 =1, p \in \fancyscript{P}_{\mathcal {A}}(K,\tau ) \right\} . \end{aligned}$$

For all $w\in \mathbb {R}^{\mathcal {A}}$ with $\Vert w-y\Vert _2 < \frac{\epsilon }{2M}$, it holds that for all $p \in \fancyscript{P}_{\mathcal {A}}(K,\tau )$,

$$\begin{aligned} \fancyscript{L}_w(p) = \fancyscript{L}_y(p) + \fancyscript{L}_{w-y}(p) \ge (\epsilon - \Vert w-y\Vert _2 M ) > 0. \end{aligned}$$

This means that all such $w$ are $K$-positive. Because $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full, by Theorem 2.2 of [9], every such $w$ belongs to $\fancyscript{R}_{\mathcal {A}}(K)$. So, $y$ is an interior point of $\fancyscript{R}_{\mathcal {A}}(K)$. $\square$

The dual cone of $\fancyscript{P}_{\mathcal {A}}(K)$ is defined as

$$\begin{aligned} \fancyscript{P}_{\mathcal {A}}(K)^* := \{ y \in \mathbb {R}^{\mathcal {A}}: \, \langle p, y\rangle \ge 0 \,\, \forall \, p \in \fancyscript{P}_{\mathcal {A}}(K) \}. \end{aligned}$$

When $\mathcal {A}= \mathbb {N}_d^n$ and $K$ is compact, $\fancyscript{P}_d(K)^*=\fancyscript{R}_d(K)$ (cf. Tchakaloff [44], Laurent [28, Section 5.2]). For more general $\mathcal {A}$, a similar result holds.

Proposition 3.2

Let $K \subseteq \mathbb {R}^n$ be a nonempty compact set. Suppose $\mathcal {A}\subseteq \mathbb {N}^n$ is finite and $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full. Then, the cones $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$ are convex, closed and have nonempty interior. Moreover, it holds that

$$\begin{aligned} \fancyscript{R}_{\mathcal {A}}(K) = \fancyscript{P}_{\mathcal {A}}(K)^*. \end{aligned}$$

(3.1)

Proof

Clearly, $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$ are convex, and $\fancyscript{P}_{\mathcal {A}}(K)$ is closed. The $K$-fullness of $\mathbb {R}[x]_{\mathcal {A}}$ implies that there exists $p\in \fancyscript{P}_{\mathcal {A}}(K)$ with $p>0$ on $K$. So, $\fancyscript{P}_{\mathcal {A}}(K)$ has nonempty interior, since $p$ is an interior point, by Lemma 3.1.

We show that $\fancyscript{R}_{\mathcal {A}}(K)$ is closed. Let $\{y_k\}\subseteq \fancyscript{R}_{\mathcal {A}}(K)$ be a sequence such that $y_k \rightarrow y^* \in \mathbb {R}^{\mathcal {A}}$ as $k\rightarrow \infty$. Note that each $\fancyscript{L}_{y_k}$ is $K$-positive, i.e.,

$$\begin{aligned} \fancyscript{L}_{y_k}(p) = \langle p, y_k \rangle \ge 0 \, \quad \forall \, p \in \fancyscript{P}_{\mathcal {A}}(K). \end{aligned}$$

Letting $k\rightarrow \infty$ in the above, we get

$$\begin{aligned} \fancyscript{L}_{y^*}(p) = \langle p, y^* \rangle \ge 0 \, \quad \forall \, p \in \fancyscript{P}_{\mathcal {A}}(K). \end{aligned}$$

So, $\fancyscript{L}_{y^*}$ is $K$-positive. Since $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full, by Theorem 2.2 of [9], we have $y^* \in \fancyscript{R}_{\mathcal {A}}(K)$. This implies that $\fancyscript{R}_{\mathcal {A}}(K)$ is closed.

Next, we show that $\fancyscript{R}_{\mathcal {A}}(K)$ has nonempty interior. Let $z$ be the tms in the proof of Lemma 3.1(i). The Riesz functional $\fancyscript{L}_z$ is strictly $K$-positive. By Lemma 3.1, $z$ is an interior point of $\fancyscript{R}_{\mathcal {A}}(K)$.

Last, we show that (3.1) is true. Clearly, $\fancyscript{R}_{\mathcal {A}}(K) \subseteq \fancyscript{P}_{\mathcal {A}}(K)^*$. For all $y\in \fancyscript{P}_{\mathcal {A}}(K)^*$, $\fancyscript{L}_y$ is $K$-positive. Since $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full, by Theorem 2.2 of [9], we have $y \in \fancyscript{R}_{\mathcal {A}}(K)$. So, (3.1) holds. $\square$

3.2 Semidefinite relaxations

First, we consider semidefinite relaxations for the cone $\fancyscript{R}_{\mathcal {A}}(K)$. Recall the notation $\Phi _k(g),E_k(h)$ from Sect. 2.2. For each $k \in \mathbb {N}$, denote

$$\begin{aligned} \fancyscript{S}_{\mathcal {A}}^k(K) = \big \{ z|_{\mathcal {A}} :\, z \in \Phi _k(g) \cap E_k(h) \big \}. \end{aligned}$$

(3.2)

(If $k < \deg (\mathcal {A})/2$, $\fancyscript{S}_{\mathcal {A}}^k(K)$ is defined to be $\mathbb {R}^{\mathcal {A}}$, by default.) Clearly, $\fancyscript{R}_{\mathcal {A}}(K) \subseteq \fancyscript{S}_{\mathcal {A}}^k(K)$ for all $k$. This is because for every $y \in \fancyscript{R}_{\mathcal {A}}(K)$, we can always extend $y$ to a tms $z \in \fancyscript{R}_{2k}(K)$ with $z|_{\mathcal {A}} =y$ (cf. [36, Prop. 3.3]). Each $\fancyscript{S}_{\mathcal {A}}^k(K)$ is a semidefinite relaxation of $\fancyscript{R}_{\mathcal {A}}(K)$, since it is defined by linear matrix inequalities. Clearly, $\fancyscript{S}_{\mathcal {A}}^{k+1}(K) \subseteq \fancyscript{S}_{\mathcal {A}}^k(K)$ for all $k$. This results in the nesting relation:

$$\begin{aligned} \fancyscript{S}_{\mathcal {A}}^{1}(K) \supseteq \cdots \supseteq \fancyscript{S}_{\mathcal {A}}^k(K) \supseteq \fancyscript{S}_{\mathcal {A}}^{k+1}(K) \supseteq \cdots \supseteq \fancyscript{R}_{\mathcal {A}}(K). \end{aligned}$$

(3.3)

Proposition 3.3

Let $K \ne \emptyset$ be as in (1.2). Suppose $I(h)+Q(g)$ is archimedean, $\mathcal {A}\subseteq \mathbb {N}^n$ is finite and $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full. Then, it holds that

$$\begin{aligned} \fancyscript{R}_{\mathcal {A}}(K) = \bigcap _{k=1}^{\infty } \fancyscript{S}_{\mathcal {A}}^k(K). \end{aligned}$$

(3.4)

Proof

We already know that $\fancyscript{R}_{\mathcal {A}}(K) \subseteq \fancyscript{S}_{\mathcal {A}}^k(K)$ for all $k$. So, $\fancyscript{R}_{\mathcal {A}}(K)$ is contained in the intersection of the right hand side of (3.4). To prove they are indeed equal, it is enough to show that for all $y \not \in \fancyscript{R}_{\mathcal {A}}(K)$, we have $y\not \in \fancyscript{S}_{\mathcal {A}}^k(K)$ if $k$ is big enough. Choose such an arbitrary $y$. By (3.1), we know $y \not \in \fancyscript{P}_{\mathcal {A}}(K)^*$, and there exists $p_1 \in \fancyscript{P}_{\mathcal {A}}(K)$ with $\langle p_1, y \rangle < 0$. Let $p_0 \in \mathbb {R}[x]_{\mathcal {A}}$ be such that $p_0>0$ on $K$. Then, for $\epsilon >0$ small, $p_2:= p_1 + \epsilon p_0 >0$ on $K$ and $\langle p_2, y \rangle < 0$. Since $I(h)+Q(g)$ is archimedean, we have $p_2 \in Q_{k_1}(g)+I_{2k_1}(h)$ for some $k_1$, by Theorem 2.1. If $y \in \fancyscript{S}_{\mathcal {A}}^{k_1}(K)$, then $y=z|_{\mathcal {A}}$ for some $z \in \Phi _{k_1}(g) \cap E_{k_1}(h)$, and we get

$$\begin{aligned} 0> \langle p_2, y \rangle = \langle p_2, z\rangle \ge 0, \end{aligned}$$

a contradiction. The latter inequality is because $p_2 \in Q_{k_1}(g)+I_{2k_1}(h)$ and $\Phi _{k_1}(g) \cap E_{k_1}(h)$ is dual to $Q_{k_1}(g)+I_{2k_1}(h)$ (cf. (2.9)). So, $y \not \in \fancyscript{S}_{\mathcal {A}}^{k_1}(K)$, and (3.4) holds. $\square$

Proposition 3.3 shows that the semidefinite relaxations $\fancyscript{S}_{\mathcal {A}}^k(K)$ can approximate $\fancyscript{R}_{\mathcal {A}}(K)$ arbitrarily well. Indeed, we can prove $\fancyscript{S}_{\mathcal {A}}^k(K)$ converges to $\fancyscript{R}_{\mathcal {A}}(K)$ if we measure their distance by normalization. For $f \in \mathbb {R}[x]_{\mathcal {A}}$, define

$$\begin{aligned} \fancyscript{S}_{\mathcal {A}}^k(K,f)&= \{ y \in \fancyscript{S}_{\mathcal {A}}^k(K): \, \langle f, y \rangle = 1\},\\ \fancyscript{R}_{\mathcal {A}}(K,f)&= \{ y \in \fancyscript{R}_{\mathcal {A}}(K): \, \langle f, y \rangle = 1\}. \end{aligned}$$

Define the distance

$$\begin{aligned} dist \Big (\fancyscript{S}_{\mathcal {A}}^k(K,f), \fancyscript{R}_{\mathcal {A}}(K,f) \Big ) = \max _{ z \in \fancyscript{S}_{\mathcal {A}}^k(K,f) } \min _{ y\in \fancyscript{R}_{\mathcal {A}}(K,f)} \Vert z-y\Vert _2. \end{aligned}$$

(3.5)

Proposition 3.4

Let $K \ne \emptyset$ be as in (1.2) and $\mathcal {A}\subseteq \mathbb {N}^n$ be finite. Suppose $I(h)+Q(g)$ is archimedean. If $f \in \mathbb {R}[x]_{\mathcal {A}}$ is positive on $K$, then

$$\begin{aligned} dist \left( \fancyscript{S}_{\mathcal {A}}^k(K,f), \fancyscript{R}_{\mathcal {A}}(K,f) \right) \, \rightarrow \, 0 \quad \text{ as } \, k\rightarrow \infty . \end{aligned}$$

(3.6)

Proof

Since $f>0$ on $K$, there exists $\epsilon >0$ with $f-\epsilon >0$ on $K$. Since $I(h)+Q(g)$ is archimedean, by Theorem 2.1, we have $f -\epsilon \in Q_{N_1}(g)+I_{2N_1}(h)$ for some $N_1$. Similarly, there exist $R>0$ and $N_2\ge N_1$ such that for all $\alpha \in \mathcal {A}$

$$\begin{aligned} R \pm x^{\alpha } \in Q_{N_2}(g) + I_{2N_2}(h). \end{aligned}$$

For all $y\in \fancyscript{S}_{\mathcal {A}}^k(K,f)$ with $k \ge N_2$, there exists $z \in \Phi _k(g) \cap E_k(h)$ such that $z|_{\mathcal {A}} = y$. Since $\langle f-\epsilon , z \rangle \ge 0$, we get $\epsilon z_{\mathbf {0}} \le \langle f, z \rangle = \langle f, y \rangle = 1$ and

$$\begin{aligned} 0 \le \langle R \pm x^{\alpha }, z \rangle = R z_{\mathbf {0}} \pm y_\alpha . \end{aligned}$$

(Here $\mathbf {0}$ denotes the zero vector in $\mathbb {N}^n$.) This implies that $| y_{\alpha } | \le R/\epsilon$ for all $\alpha \in \mathcal {A}$. Hence, the sets $\fancyscript{S}_{\mathcal {A}}^k(K,f)$, with $k \ge N_2$, are uniformly bounded.

By (3.3), we know $dist \left( \fancyscript{S}_{\mathcal {A}}^k(K,f), \fancyscript{R}_{\mathcal {A}}(K,f) \right)$ is monotonically decreasing. Suppose otherwise (3.6) is not true. Then there exists $\tau$ such that

$$\begin{aligned} dist \left( \fancyscript{S}_{\mathcal {A}}^k(K,f), \fancyscript{R}_{\mathcal {A}}(K,f) \right) \ge \tau > 0 \end{aligned}$$

for all $k$. We can select $y^{k} \in \fancyscript{S}_{\mathcal {A}}^{k}(K,f)$ for each $k$ such tat

$$\begin{aligned} dist \left( y^{k}, \fancyscript{R}_{\mathcal {A}}(K,f) \right) \ge \tau /2. \end{aligned}$$

The sequence $\{y^{k}\}$ is bounded, because the sets $\fancyscript{S}_{\mathcal {A}}^k(K,f)$ ($k \ge N_2$) are uniformly bounded, as shown in the above. It has a convergent subsequence, say, $y^{k_i} \rightarrow \hat{y}$ as $i\rightarrow \infty$. Clearly, $\langle f, \hat{y} \rangle =1$ and $dist \left( \hat{y}, \fancyscript{R}_{\mathcal {A}}(K,f) \right) >0$. So, $\hat{y} \not \in \fancyscript{R}_{\mathcal {A}}(K,f)$. This implies $\hat{y} \not \in \fancyscript{R}_{\mathcal {A}}(K) = \fancyscript{P}_{\mathcal {A}}(K)^*$, by (3.1). So, there exists $p_0\in \fancyscript{P}_{\mathcal {A}}(K)$ such that $\langle p_0, \hat{y} \rangle < 0.$ For a small $\epsilon _0>0$, we have

$$\begin{aligned} p_1:=p_0 + \epsilon _0 f> 0 \quad \text{ on } \,\, K, \qquad \langle p_1, \hat{y} \rangle < 0. \end{aligned}$$

By Theorem 2.1, we have $p_1 \in Q_{N_3}(g)+I_{2N_3}(h)$ for some $N_3$. So, $\langle p_1, y^{k_i} \rangle \ge 0$ for all $k_i \ge N_3$. This results in

$$\begin{aligned} \langle p_1, \hat{y} \rangle = \lim _{ i \rightarrow \infty } \langle p_1, y^{k_i} \rangle \ge 0, \end{aligned}$$

which is a contradiction. Thus, (3.6) must be true. $\square$

Second, we consider semidefinite relaxations for the cone $\fancyscript{R}_{\mathcal {A}}(K)$. Denote

$$\begin{aligned} \fancyscript{Q}_{\mathcal {A}}^k(K) = \{ p \in \mathbb {R}[x]_{\mathcal {A}} : \, p \in Q_k(g)+ E_{2k}(h) \}. \end{aligned}$$

(3.7)

Clearly, $\fancyscript{Q}_{\mathcal {A}}^k(K) \subseteq \fancyscript{P}_{\mathcal {A}}(K)$ for all $k$. Suppose $K$ is compact and $\mathbb {R}[x]_\mathcal {A}$ is $K$-full. If $p$ is in the interior of $\fancyscript{P}_{\mathcal {A}}(K)$, then $p>0$ on $K$ by Lemma 3.1, and $p \in \fancyscript{Q}_{\mathcal {A}}^k(K)$ for some $k$ by Theorem 2.1, if $I(h)+Q(g)$ is archimedean. So, we get the following proposition.

Proposition 3.5

Let $K \ne \emptyset$ be as in (1.2) and $\mathcal {A}\subseteq \mathbb {N}^n$ be finite. Suppose $\mathbb {R}[x]_\mathcal {A}$ is $K$-full and $I(h)+Q(g)$ is archimedean. Then, we have

$$\begin{aligned} int\left( \fancyscript{P}_{\mathcal {A}}(K) \right) \subseteq \bigcup _{k=1}^{\infty } \fancyscript{Q}_{\mathcal {A}}^k(K) \subseteq \fancyscript{P}_{\mathcal {A}}(K). \end{aligned}$$

(3.8)

The second containment inequality in (3.8) generally cannot be strengthened to an equality. For instance, when $K = B(0,1)$ and $\mathcal {A}= \mathbb {N}^3_6$, the Motzkin polynomial $x_1^2x_2^2(x_1^2+x_2^2-3x_3^2)+x_3^6 \in \fancyscript{P}_{\mathcal {A}}(K)$ but it does not belong to $\fancyscript{Q}_{\mathcal {A}}^k(K)$ for any $k$ (cf. [33, Example 5.3]).

3.3 Checking memberships

First, checking whether $y \in \fancyscript{R}_{\mathcal {A}}(K)$ or not can be done by Algorithm 4.2 of [36]. It is based on solving a hierarchy of semidefinite relaxations about moment sequences. That algorithm has the following properties: i) If $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full and $y \in \mathbb {R}^{\mathcal {A}}$ admits no $K$-measures, then a semidefinite relaxation is infeasible. The infeasibility gives a certificate for the non-membership $y \not \in \fancyscript{R}_{\mathcal {A}}(K)$. ii) If $y$ admits a $K$-measure, then we can asymptotically get a finitely atomic $K$-representing measure for $y$, which certifies the membership $y \in \fancyscript{R}_{\mathcal {A}}(K)$; moreover, under some general conditions, we can get such a measure within finitely many steps.

Second, we discuss how to check memberships in the cone $\fancyscript{P}_{\mathcal {A}}(K)$. Clearly, a polynomial $f \in \mathbb {R}[x]_{\mathcal {A}}$ belongs to $\fancyscript{P}_{\mathcal {A}}(K)$ if and only if its minimum $f_{min}$ over $K$ is nonnegative. A standard approach for computing $f_{min}$ is to apply Lasserre’s hierarchy of semidefinite relaxations ($k=1,2,\ldots$):

$$\begin{aligned} f_k = \max \quad \gamma \qquad s.t. \qquad f-\gamma \in I_{2k}(h) + Q_k(g). \end{aligned}$$

(3.9)

Clearly, if $f_k \ge 0$ for some $k$, then $f \in \fancyscript{P}_{\mathcal {A}}(K)$. Suppose $I(h)+Q(g)$ is archimedean. For all $f \in int(\fancyscript{P}_{\mathcal {A}}(K))$, we have $f_k > 0$ for some $k$, by Proposition 3.5. For $f$ lying generically on the boundary of $\fancyscript{P}_{\mathcal {A}}(K)$ (e.g., some standard optimality conditions hold), we have $f_k \ge 0$ for some $k$ (cf. [35]). For the remaining non-generic cases, it is possible that $f_k < f_{min}$ for all $k$ (cf. [33, Examples 5.3, 5.6]).

Another method for computing $f_{min}$ is the Jacobian SDP relaxation proposed in [33]. Its basic idea is to add new polynomial equalities, by using the Jacobian of polynomials $f, h_i,g_j$. Suppose $\varphi := (\varphi _1,\ldots ,\varphi _L)=0$ is added (cf. [33, Section 2]). Under some generic conditions on $K$ but not on $f$ (cf. Assumption 2.2 of [33]), $f_{min}$ equals the optimal value of

$$\begin{aligned} \min \quad f(x) \quad \text{ s.t. } \quad \varphi (x) = 0, \, h(x) = 0, \, g(x) \ge 0. \end{aligned}$$

(3.10)

This leads to the hierarchy of stronger semidefinite relaxations ($k=1,2,\ldots$):

$$\begin{aligned} f_k^{jac} := \max \, \gamma \quad \text{ s.t. } \quad f - \gamma \in I_{2k}(h)+I_{2k}(\varphi ) + Q_k(g). \end{aligned}$$

(3.11)

An advantage of this approach is that $\{f_k^{jac}\}$ always have finite convergence to $f_{min}$ (cf. [33, Section 4]). So, we can check whether $f \in \fancyscript{P}_{\mathcal {A}}(K)$ or not by solving finitely many semidefinite relaxations.

4 Linear optimization problems

Let $K$ be as in (1.2) and $\mathcal {A}\subseteq \mathbb {N}^n$ be finite. Given $a_1, \ldots , a_m,c \in \mathbb {R}[x]_{\mathcal {A}}$ and $b\in \mathbb {R}^m$, we consider the linear optimization problem

$$\begin{aligned} \left\{ \begin{array}{rl} c^{min} := \min &{} \langle c, y \rangle \\ s.t. &{} \langle a_i, y \rangle = b_i \, (i = 1,\ldots , m), \quad y \in \fancyscript{R}_{\mathcal {A}}(K). \end{array} \right. \end{aligned}$$

(4.1)

The dual problem of (4.1) is

$$\begin{aligned} \left\{ \begin{array}{rl} b^{\max }:=\max &{} b^T\lambda \\ s.t. &{} c(\lambda ):= c - \sum _{i=1}^m \lambda _i a_i \in \fancyscript{P}_{\mathcal {A}}(K). \end{array}\right. \end{aligned}$$

(4.2)

The cones $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$ are hard to describe, but they can be approximated as close as possible by the semidefinite relaxations $\fancyscript{S}_{\mathcal {A}}^k(K)$ in (3.2) and $\fancyscript{Q}_{\mathcal {A}}^k(K)$ in (3.7), respectively (cf. Propositions 3.3, 3.5). If we relax $\fancyscript{R}_{\mathcal {A}}(K)$ by $\fancyscript{S}_{\mathcal {A}}^k(K)$, then (4.1) is relaxed to

$$\begin{aligned} \left\{ \begin{array}{rl} c^k:= \underset{y, w}{\min } &{} \langle c, y \rangle \\ s.t. &{} \langle a_i, y \rangle = b_i, \, i =1,\ldots , m \\ &{} y=w|_{\mathcal {A}}, \, w \in \Phi _k(g) \cap E_k(h). \end{array} \right. \end{aligned}$$

(4.3)

If $y$ is feasible in (4.3), then $y \in \fancyscript{S}_{\mathcal {A}}^k(K)$. The integer $k$ in (4.3) is called a relaxation order. The dual problem of (4.3) is

$$\begin{aligned} \left\{ \begin{array}{rl} b^k:= \underset{\lambda =(\lambda _1, \ldots , \lambda _m) }{\max } &{} b^T\lambda \\ s.t. \quad \, &{} c(\lambda ) \in Q_k(g) + I_{2k}(h). \end{array} \right. \end{aligned}$$

(4.4)

Clearly, $\lambda$ is feasible in (4.4) if and only if $c(\lambda ) \in \fancyscript{Q}_{\mathcal {A}}^k(K)$. Recall the notation $\Phi _k(g)$, $E_k(h)$, $Q_k(g)$, $I_{2k}(h)$ from Sect. 2.2.

Clearly, we have $c^k \le c^{min}$ and $b^k \le b^{\max }$ for all $k$. Let $(y^{*,k}, w^{*,k})$ be a minimizer of (4.3), and let $\lambda ^{*,k}$ be a maximizer of (4.4). If $y^{*,k} \in \fancyscript{R}_{\mathcal {A}}(K)$, then $c^k= c^{min}$ and $y^{*,k}$ is a minimizer of (4.1), i.e., the relaxation (4.3) is exact for solving (4.1). In such case, if $b^k = c^k$ also holds, then $b^k = b^{\max }$ and $\lambda ^{*,k}$ is a maximizer of (4.2). If the relaxation (4.3) is infeasible, then (4.1) must also be infeasible. Combining the above, we get the following algorithm.

Algorithm 4.1

A semidefinite algorithm for solving (4.1)–(4.2).

Input:  $c,a_1, \ldots , a_m \in \mathbb {R}[x]_{\mathcal {A}}$, $b \in \mathbb {R}^m$ and $K$ as in (1.2).

Output: A minimizer $y^*$ of (4.1) and a maximizer $\lambda ^*$ of (4.2), or an answer that (4.1) is infeasible.

Procedure:

• Step 0:   Let $k = \lceil \deg (\mathcal {A})/2 \rceil$.

• Step 1:   Solve the primal-dual pair (4.3)–(4.4). If (4.3) is infeasible, stop and output that (4.1) is infeasible; otherwise, compute an optimal pair $(y^{*,k},w^{*,k})$ for (4.3) and a maximizer $\lambda ^{*,k}$ for (4.4).

• Step 2:   If $y^{*,k} \in \fancyscript{R}_{\mathcal {A}}(K)$, then $y^{*,k}$ is a minimizer of (4.1); if in addition $b^k = c^k$, then $\lambda ^{*,k}$ is a maximizer of (4.2); stop and output $y^*=y^{*,k}$, $\lambda ^*=\lambda ^{*,k}$. Otherwise, let $k:=k+1$ and go to Step 1.

Remark 4.2

Checking if $y^{*,k} \in \fancyscript{R}_{\mathcal {A}}(K)$ or not is a stopping criterion for Algorithm 4.1. If there exists $t \ge \deg (\mathcal {A})/2$ such that $w^{*,k}|_{2t}$ is flat, then $y^{*,k} \in \fancyscript{R}_{\mathcal {A}}(K)$. This gives a convenient way to terminate the algorithm. It is possible that $y^{*,k}$ belongs to $\fancyscript{R}_{\mathcal {A}}(K)$ while $w^{*,k}|_{2t}$ is not flat for all $t$ (cf. Example 4.9). In such case, we can apply Algorithm 4.2 of [36] to check if $y^{*,k} \in \fancyscript{R}_{\mathcal {A}}(K)$ or not.

Feasibility and infeasibility issues of (4.1)–(4.2) are more delicate. They will be studied separately in Sect. 5. In Sect. 4.1, we prove the asymptotic and finite convergence of Algorithm 4.1. In Sect. 4.2, we present some examples.

4.1 Convergence analysis

First, we prove the asymptotic convergence of Algorithm 4.1.

Theorem 4.3

Let $K$ be as in (1.2) and $\mathcal {A}\subseteq \mathbb {N}^n$ be finite. Suppose (4.1) is feasible, (4.2) has an interior point, $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full, and $Q(g)+I(h)$ is archimedean. Then, we have:

• (i) For all $k$ sufficiently large, (4.4) has an interior point and (4.3) has a minimizing pair $(y^{*,k},w^{*,k})$.

• (ii) The sequence $\{y^{*,k}\}$ is bounded, and each of its accumulation points is a minimizer of (4.1).

• (iii) The sequence $\{b^k\}$ converges to the maximum $b^{\max }$ of (4.2).

Remark 4.4

For the classical case $\mathcal {A}= \mathbb {N}_d^n$, if one of $c,a_1,\ldots , a_m$ is positive on $K$, Lasserre [22, Theorem 1] proved $c^k \rightarrow c^{min}$ as $k \rightarrow \infty$. This can also be implied by the item (ii) of Theorem 4.3, because $c^k = \langle c, y^{*,k} \rangle$. The conclusion that each accumulation point of $\{y^{*,k}\}$ is a minimizer of (4.1) is a stronger property. Moreover, the assumption that (4.2) has an interior point is weaker than that one of $c,a_1,\ldots , a_m$ is positive on $K$. Theorem 4.3 discusses more general cases of $\mathcal {A}$.

Proof (of Theorem 4.3)

• (i) Let $\lambda ^0$ be an interior point of (4.2). Then $c(\lambda ^0) = c - \sum _{i=1}^m \lambda _i^0 a_i >0$ on $K$, by Lemma 3.1. The archimedeanness of $I(h)+Q(g)$ implies that $K$ is compact. So, there exist $\epsilon _0>0$ and $\theta > 0$ such that

  $$\begin{aligned} c(\lambda ) - \epsilon _0 > \epsilon _0 \quad \forall \, \lambda \in B(\lambda ^0,\theta ). \end{aligned}$$

  By Theorem 6 of [31], there exists $N_0>0$ such that

  $$\begin{aligned} c(\lambda ) - \epsilon _0 \in I_{2N_0}(h) + Q_{N_0}(g) \quad \forall \, \lambda \in B(\lambda ^0,\theta ). \end{aligned}$$

  So, (4.4) has an interior point for all $k\ge N_0$, and the strong duality holds between (4.3) and (4.4). Since (4.1) is feasible, the relaxation (4.3) is also feasible and has a minimizing pair $(y^{*,k}, w^{*,k})$ (cf. [1, Theorem 2.4.I]).

• (ii) First, we show that $\{y^{*,k}\}$ is a bounded sequence. Let $c(\lambda ^0)$ and $\epsilon _0$ be as in the proof of (i). The set $I_{2N_0}(h) + Q_{N_0}(g)$ is dual to $E_{2N_0}(h)\cap \Phi _{N_0}(g)$. For all $k\ge N_0$, we have $w^{*,k} \in E_{N_0}(h) \cap \Phi _{N_0}(g)$ and

  $$\begin{aligned} 0 \le \langle c(\lambda ^0) - \epsilon _0, w^{*,k} \rangle = \langle c(\lambda ^0) , w^{*,k} \rangle - \epsilon _0 \langle 1, w^{*,k} \rangle ,\\ \langle c(\lambda ^0) , w^{*,k} \rangle = \langle c , w^{*,k} \rangle - \sum _{i=1}^m \lambda _i^0 \langle a_i , y^{*,k} \rangle = \langle c , w^{*,k} \rangle - b^T \lambda ^0. \end{aligned}$$

  Since $\langle c , w^{*,k} \rangle \le c^{min}$, it holds that

  $$\begin{aligned} \langle c(\lambda ^0) , w^{*,k} \rangle \le T_0:= c^{min} - b^T \lambda ^0. \end{aligned}$$

  Combining the above, we get (denote by $\mathbf {0}$ the zero vector in $\mathbb {N}^n$)

  $$\begin{aligned} 0 \le \langle c(\lambda ^0) - \epsilon _0, w^{*,k} \rangle \le T_0 - \epsilon _0 (w^{*,k})_{\mathbf {0}}, \end{aligned}$$
  $$\begin{aligned} (w^{*,k})_{\mathbf {0}} \le T_1:=T_0/\epsilon _0. \end{aligned}$$

  Since $I(h)+Q(g)$ is archimedean, there exist $\rho >0$ and $k_1 \in \mathbb {N}$ such that

  $$\begin{aligned} \rho - \Vert x\Vert _2^2 \in I_{2k_1}(h) + Q_{k_1}(g). \end{aligned}$$

  So, for all $k\ge k_1$, we get

  $$\begin{aligned} 0 \le \langle \rho - \Vert x\Vert _2^2, w^{*,k} \rangle = \rho (w^{*,k})_{\mathbf {0}} - \sum _{|\alpha |=1} (w^{*,k})_{2\alpha }, \quad \sum _{|\alpha |=1} (w^{*,k})_{2\alpha } \le \rho T_1. \end{aligned}$$

  For each $t = 1, \ldots , k-k_1$, we have

  $$\begin{aligned} \Vert x\Vert _2^{2t-2}(\rho - \Vert x\Vert _2^2) \in I_{2k}(h) + Q_{k}(g). \end{aligned}$$

  The membership $w^{*,k} \in \Phi _k(g) \cap I_k(h)$ implies that

  $$\begin{aligned} \rho \langle \Vert x\Vert _2^{2t-2}, w^{*,k} \rangle - \langle \Vert x\Vert _2^{2t}, w^{*,k} \rangle \ge 0, \quad t = 1, \ldots , k-k_1. \end{aligned}$$

  The above then implies that

  $$\begin{aligned} \langle \Vert x\Vert _2^{2t}, w^{*,k} \rangle \le \rho ^{t} T_1, \quad t = 1, \ldots , k-k_1. \end{aligned}$$

  Let $z^k := w^{*,k}|_{2k-2k_1}$, then the moment matrix $M_{k-k_1}(z^k) \succeq 0$ and

  $$\begin{aligned} \Vert z^k\Vert _2 \le \Vert M_{k-k_1}(z^k)\Vert _F \le Trace(M_{k-k_1}(z^k)) = \sum _{i=0}^{k-k_1} \sum _{|\alpha | = i}\, (w^{*,k})_{2\alpha },\\ \sum _{|\alpha | = i}\, (w^{*,k})_{2\alpha } = \left\langle \sum _{|\alpha | = i} \,x^{2\alpha }, z^k \right\rangle \le \langle \Vert x\Vert _2^{2i}, z^{k} \rangle \le \rho ^i T_1. \end{aligned}$$

  The above then implies that

  $$\begin{aligned} \Vert z^k\Vert _2 \le (1 + \rho + \cdots + \rho ^{k-k_1}) T_1. \end{aligned}$$

  Fix $k_2>k_1$ such that $y^{*,k}$ is a subvector of $z^k|_{k_2-k_1}$. From $y^{*,k} = z^k|_{\mathcal {A}}$, we get

  $$\begin{aligned} \Vert y^{*,k}\Vert _2 \le \Vert z^k\Vert _2 \le (1 + \rho + \cdots + \rho ^{k_2-k_1}) T_1. \end{aligned}$$

  This shows that the sequence $\{y^{*,k}\}$ is bounded. Second, we show that every accumulation point of $\{y^{*,k}\}$ is a minimizer of (4.1). Let $y^*$ be such an arbitrary one. We can generally further assume $y^{*,k} \rightarrow y^*$ as $k\rightarrow \infty$. We need to show that $y^*$ is a minimizer of (4.1). Since $K$ is compact, by the archimedeanness of $I(h)+Q(g)$, we can generally assume $K \subseteq B(0,\rho )$ with $\rho <1$, up to a scaling. In the above, we have shown that

  $$\begin{aligned} \Vert z^k\Vert _2 \le T_1/(1-\rho ). \end{aligned}$$

  This implies that the sequence $\{z^k\}$ is bounded. Each tms $z^k$ can be extended to a vector in $\mathbb {R}^{\mathbb {N}_{\infty }^n}$ by adding zero entries to the tailing. The set $\mathbb {R}^{\mathbb {N}_{\infty }^n}$ is a Hilbert space, equipped with the inner product

  $$\begin{aligned} \langle u, v \rangle := \sum _{ \alpha \in \mathbb {N}^n } u_\alpha v_\alpha , \quad \forall \, u, v \in \mathbb {R}^{\mathbb {N}_{\infty }^n}. \end{aligned}$$

  So, the sequence $\{ z^k \}$ is also bounded in $\mathbb {R}^{\mathbb {N}_{\infty }^n}$. By Alaoglu’s Theorem (cf. [3, Theorem V.3.1] or [25, Theorem C.18]), it has a subsequence $\{z^{k_j} \}$ that is convergent in the weak-$*$ topology. That is, there exists $z^* \in \mathbb {R}^{\mathbb {N}_{\infty }^n}$ such that

  $$\begin{aligned} \langle f, z^{k_j} \rangle \, \rightarrow \, \langle f, z^* \rangle \quad \text{ as } j \rightarrow \infty \end{aligned}$$

  for all $f \in \mathbb {R}^{\mathbb {N}_{\infty }^n}$. Clearly, this implies that for each $\alpha \in \mathbb {N}^n$

  $$\begin{aligned} (z^{k_j})_{\alpha } \rightarrow (z^*)_{\alpha }. \end{aligned}$$

  (4.5)

  Since $z^k|_{\mathcal {A}} = y^{*,k} \rightarrow y^*$, we get $z^*|_{\mathcal {A}} = y^*$. Note that $z^{k_j} \in \Phi _{k_j}(g) \cap E_{k_j}(h)$ for all $j$. For each $r=1,2,\ldots$, if $k_j \ge 2r$, then (cf. Sect. 2.1)

  $$\begin{aligned} L_{h_i}^{(r)}(z^{(k_j)}) = 0\,(1\le i \le m_1), \quad L_{g_i}^{(r)}(z^{(k_j)})\succeq 0 \,(0\le i \le m_2). \end{aligned}$$

  Hence, (4.5) implies that for all $r=1,2,\ldots$

  $$\begin{aligned} L_{h_i}^{(r)}(z^*) = 0\,(1\le i \le m_1), \quad L_{g_i}^{(r)}(z^*)\succeq 0 \,(0\le i \le m_2). \end{aligned}$$

  This means that $z^* \in \mathbb {R}^{\mathbb {N}_{\infty }^n}$ is a full moment sequence whose localizing matrices of all orders are positive semidefinite. By Lemma 3.2 of Putinar [39], $z^*$ admits a $K$-measure. Clearly, $\langle a_i, y^*\rangle = b_i$ for all $i$. So, $y^* = z^*|_{\mathcal {A}}$ is feasible for (4.1) and $c^{min} \le \langle c, y^*\rangle$. Because (4.3) is a relaxation of (4.1) and $w^{*,k}$ is a minimizer of (4.3), it holds that

  $$\begin{aligned} c^{min} \ge \langle c, y^{*,k}\rangle , \quad k=1,2,\ldots \end{aligned}$$

  Hence, we get

  $$\begin{aligned} c^{min} \ge \lim _{k\rightarrow \infty } \langle c, y^{*,k}\rangle = \langle c, y^*\rangle . \end{aligned}$$

  Therefore, $c^{min} = \langle c, y^*\rangle$ and $y^*$ is a minimizer of (4.1).

• (iii) For each $\epsilon >0$, there exists $\lambda ^\epsilon$ such that $c(\lambda ^\epsilon ) \in \fancyscript{P}_{\mathcal {A}}(K)$ and

  $$\begin{aligned} b^{max} - \epsilon < b^T \lambda ^\epsilon \le b^{max} . \end{aligned}$$

  Let $\lambda ^0$ be as in the proof of item (i), and let $\lambda (\epsilon ) = (1-\epsilon ) \lambda ^\epsilon + \epsilon \lambda ^0$. Then $c(\lambda (\epsilon ))>0$ on $K$ and

  $$\begin{aligned} b^T\lambda (\epsilon ) = (1-\epsilon ) b^T\lambda ^\epsilon + \epsilon b^T\lambda ^0 > (1-\epsilon ) (b^{max} - \epsilon ) + \epsilon b^T\lambda ^0. \end{aligned}$$

  By Theorem 2.1, if $k$ is big enough, then $c(\lambda (\epsilon )) \in I_{2k}(h)+Q_k(g)$ and

  $$\begin{aligned} b^k > (1-\epsilon ) (b^{max} - \epsilon ) + \epsilon b^T\lambda ^0. \end{aligned}$$

  Since $b^k \le b^{max}$ for all $k$, we get $b^k \rightarrow b^{max}$ as $k \rightarrow \infty$. $\square$

Second, we prove the finite convergence of Algorithm 4.1 under a general assumption.

Assumption 4.5

Suppose $\lambda ^*$ is a maximizer of (4.2) and $c^*:=c(\lambda ^*)$ satisfies:

• (i) There exists $k_1 \in \mathbb {N}$ such that $c^* \in I_{2k_1}(h)+Q_{k_1}(g)$;

• (ii) The optimization problem

  $$\begin{aligned} \min \quad c^*(x) \quad s.t. \quad h(x) = 0, \, g(x) \ge 0 \end{aligned}$$

  (4.6)

  has finitely many KKT points $u$ on which $c^*(u)=0$.

Theorem 4.6

Let $K$ be as in (1.2). Suppose (4.1) is feasible, (4.2) has an interior point, $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full and Assumption 4.5 holds. If $w^{*,k}$ is optimal for (4.3), then $w^{*,k}|_{2t}$ is flat for all $k > t$ big enough.

Remark 4.7

If $c^*$ is generic on the boundary of the cone $\fancyscript{P}_{\mathcal {A}}(K)$, then Assumption 4.5 holds (cf. [32, 35]). For instance, if some standard optimality conditions are satisfied for the optimization problem (4.6), then Assumption 4.5 is satisfied. Theorem 4.6 implies that Algorithm 4.1 generally converges in finitely many steps. This fact has been observed in numerical experiments.

Proof (of Theorem 4.6)

The existence of a minimizer $(y^{*,k},w^{*,k})$ is shown in Theorem 4.3. Because (4.1) is feasible and (4.2) has an interior point, (4.1) has a minimizer $y^*$ and there is no duality gap between (4.1) and (4.2), i.e.,

$$\begin{aligned} 0 = \langle c, y^* \rangle - b^T\lambda ^* = \langle c^*, y^* \rangle . \end{aligned}$$

Clearly, $c^* \ge 0$ on $K$. Let $\mu ^*$ be a $K$-representing measure for $y^*$. Then, every point in $\text{ supp }(\mu ^*)$ is a minimizer of (4.6), and the minimum value is $0$. The $k$-th Lasserre’s relaxation for (4.6) is (cf. [19, 34])

$$\begin{aligned} \gamma _k := \max \quad \gamma \quad s.t. \quad c^*-\gamma \in I_{2k}(h) + Q_k(g). \end{aligned}$$

(4.7)

Then, $\gamma _k=0$ for all $k\ge k_1$. The sequence $\{\gamma _k\}$ has finite convergence. The relaxation (4.7) achieves its optimal value for all $k \ge k_1$, by Assumption 4.5 (i). The dual problem of (4.7) is

$$\begin{aligned} \min _{ w } \quad \langle c^*, w \rangle \quad s.t. \quad w \in \Phi _k(g) \cap E_k(h), w_{\mathbf {0}} = 1. \end{aligned}$$

(4.8)

By Assumption 4.5(ii), (4.6) has only finitely many critical points on which $c^*=0$. So, Assumption 2.1 in [34] for the problem (4.6) is satisfied.¹ Suppose $w^{*,k}$ is optimal for (4.3).

If $(w^{*,k})_{\mathbf {0}}=0$, then $vec(1)^T M_k(w^{*,k}) vec(1) =0$ and $M_k(w^{*,k}) vec(1) =0$, because $M_k(w^{*,k})\succeq 0$. (Here $vec(p)$ denotes the coefficient vector of a polynomial $p$.) This implies that $M_k(w^{*,k}) vec(x^\alpha )=0$ for all $|\alpha | \le k-1$ (cf. [28, Lemma 5.7]). For all $|\alpha |\le 2k-2$, we can write $\alpha = \beta + \eta$ with $|\beta |,|\eta | \le k-1$, and get

$$\begin{aligned} (w^{*,k})_\alpha = vec(x^\beta )^T M_k(w^{*,k}) vec(x^\eta ) =0. \end{aligned}$$

So, the truncation $w^{*,k}|_{2k-2}$ is flat.

If $(w^{*,k})_{\mathbf {0}}>0$, we can scale $w^{*,k}$ such that $(w^{*,k})_{\mathbf {0}}=1$. Then $w^{*,k}$ is a minimizer of (4.8) because $\langle c^*, w^{*,k} \rangle = 0$ for all $k\ge k_1$. By Theorem 2.2 of [34], $w^{*,k}$ has a flat truncation $w^{*,k}|_{2t}$ for some $t \ge \deg (\mathcal {A})/2$, for all $k$ sufficiently large. $\square$

4.2 Some examples

Semidefinite relaxations (4.3) and (4.4) can be solved by GloptiPoly 3 [18].

Example 4.8

Let $K$ be the simplex $\Delta _n = \{x\in \mathbb {R}_+^n: x_1+\cdots +x_n=1\}$ and $\mathcal {A}= \{\alpha \in \mathbb {N}^n: |\alpha | = 2\}$. Then $\fancyscript{P}_{\mathcal {A}}(\Delta _n)$ is the cone of $n\times n$ copositive matrices (denoted as $\mathtt {Co}(n)$), and $\fancyscript{R}_{\mathcal {A}}(\Delta _n)$ is the cone of $n\times n$ completely positive matrices (denoted as $\mathtt {Cp}(n)$). The simplex $\Delta _n$ is defined by the tuples $h=(x_1+\cdots +x_n - 1)$ and $g=(x_1,\ldots ,x_n)$, as in (1.2).

• (i) Let $c = (x_1+\cdots +x_6)^2$ and $a_1 = x_1x_2-x_2x_3+x_3x_4-x_5x_6+x_6x_1$. We want to know the maximum $\lambda$ such that $c - \lambda a_1 \in \mathtt {Co}(6)$. We formulate this problem in the form (4.2) and then solve it by Algorithm 4.1. For $k=2$, $y^{*,2} \in \mathtt {Cp}(6)$ (because it admits the measure $4 \delta _{(1/2,1/4,0,0,0, 1/4)}$) and $\lambda ^{*,2} = 4$. Since $c^k=b^k$ for $k=2$, we know the maximum $\lambda$ for the above is $4$.

• (ii) Consider the matrix

  $$\begin{aligned} C = \left[ \begin{array}{lllll} * &{} 1 &{} 2 &{} 3 &{} 4 \\ 1 &{} * &{} 1 &{} 2 &{} 3 \\ 2 &{} 1 &{} * &{} 1 &{} 2 \\ 3 &{} 2 &{} 1 &{} * &{} 1 \\ 4 &{} 3 &{} 2 &{} 1 &{} * \\ \end{array} \right] \end{aligned}$$

  where each $*$ means the entry is not given. We want to know the smallest trace of $C$ such that $C \in \mathtt {Cp}(5)$. We formulate this problem in the form (4.1) and then solve it by Algorithm 4.1. For $k=2$, $y^{*,2} \in \fancyscript{R}_{\mathcal {A}}(\Delta _5)$ (verified by Algorithm 4.2 of [36]). So, the minimum trace of $C \in \mathtt {Cp}(5)$ is 20.817217,² while the diagonal entries $C_{11},\ldots ,C_{55}$ are $6.031873$, $3.968627$, $0.816217$, $3.968627$, $6.031873$, respectively.

$\square$

Example 4.9

Let $K= B(0,1)$ be the unit ball in $\mathbb {R}^2$ and $\mathcal {A}= \mathbb {N}_6^4$. We want to know the maximum $\lambda _1 + \lambda _2$ such that

$$\begin{aligned} x_1^4x_2^2+6x_1^2x_2^2+4x_1x_2^4+x_2^6+x_2^2 - \lambda _1 ( x_1^3x_2^2+x_1x_2^2 ) - \lambda _2 ( x_1^2x_2^4+x_2^4) \in \fancyscript{P}_{\mathcal {A}}(K). \end{aligned}$$

We formulate this problem in the form (4.2) and then solve it by Algorithm 4.1. When $k=3$, $y^{*,3} \in \fancyscript{R}_{\mathcal {A}}(K)$ (verified by Algorithm 4.2 of [36]), and $\lambda ^{*,3}=(4,2)$. Since $c^k=b^k$ for $k=2$, the optimal $(\lambda _1,\lambda _2)$ in the above is $(4,2)$. $\square$

Example 4.10

Let $K= \mathbb {S}^2$ and $\mathcal {A}= \{\alpha \in \mathbb {N}^3: |\alpha | = 6\}$. Then, $\fancyscript{P}_{\mathcal {A}}(K)=P_{3,6}$ and $\fancyscript{R}_{\mathcal {A}}(K)$ is the cone of sextic tms’ admitting measures supported in $\mathbb {S}^2$.

• (i) The form $c = x_1^6+x_2^6+x_3^6$ lies in the interior of $P_{3,6}$. Let

  $$\begin{aligned} a_1 = x_1^2x_2^4+ x_2^2x_3^4 + x_3^2 x_1^4, \, a_2 = x_1^3x_2^3+ x_2^3x_3^3 + x_3^3 x_1^3, \, a_3 = x_1^5x_2+ x_2^5x_3 + x_3^5 x_1.\qquad \end{aligned}$$

  We want to know the maximum $\lambda _1+\lambda _2+\lambda _3$ such that

  $$\begin{aligned} c - \lambda _1 a_1 - \lambda _2 a_2 - \lambda _3 a_3 \in P_{3,6}. \end{aligned}$$

  We formulate this problem in the form (4.2) and then solve it by Algorithm 4.1. When $k=3$, $y^{*,3} \in \fancyscript{R}_{\mathcal {A}}(K)$ (it admits the measure $9 \delta _{(1,1,1)/\sqrt{3}}$), and

  $$\begin{aligned} \lambda ^{*,3}=( -1.440395, 2.218992, 0.221403). \end{aligned}$$

  Since $c^k=b^k$ for $k=2$, we know $\lambda ^{*,3}$ is optimal for the above.

• (ii) We want to know the minimum value of $\int (x_1^6+x_2^6+x_3^6) \mathtt {d} \mu$ for all measures $\mu$ supported in $\mathbb {S}^2$ such that

  $$\begin{aligned} \int x_1^3x_2^3 \mathtt {d} \mu&= \int x_2^3x_3^3 \mathtt {d} \mu = \int x_3^3x_1^3 \mathtt {d} \mu , \int x_1^2x_2^2x_3^2 \mathtt {d} \mu = 1,\\&\int (x_1^4x_2^2 + x_2^4x_3^2 + x_3^4x_1^2) \mathtt {d} \mu = 3. \end{aligned}$$

  We formulate the problem in the form (4.1) and then solve it by Algorithm 4.1. When $k=3$, $y^{*,3} \in \fancyscript{R}_{\mathcal {A}}(K)$ because it admits the measure

  $$\begin{aligned} \frac{27}{4} \left( \delta _{(1,1,1)/\sqrt{3}} + \delta _{(-1,1,1)/\sqrt{3}} + \delta _{(1,-1,1)/\sqrt{3}} + \delta _{(1,1,-1)/\sqrt{3}} \right) . \end{aligned}$$

  So, the minimum of $\int (x_1^6+x_2^6+x_3^6) \mathtt {d} \mu$ for $\mu$ satisfying the above is $3$.

$\square$

If a linear optimization problem with cone $\fancyscript{R}_{\mathcal {A}}(K)$ is given in the form (4.2), it can also be equivalently formulated in the form (4.1). For instance, given $z_0, \ldots , z_m \in \mathbb {R}^{\mathcal {A}}$ and $\ell = (\ell _1,\ldots , \ell _m) \in \mathbb {R}^m$, consider the problem

$$\begin{aligned} \left\{ \begin{array}{rl} \max &{} \ell _1 \lambda _1 + \cdots + \ell _m \lambda _m \\ s.t. &{} z_0 - \lambda _1 z_1 - \cdots - \lambda _m z_m \in \fancyscript{R}_{\mathcal {A}}(K). \end{array} \right. \end{aligned}$$

(4.9)

Let $\{p_1, \ldots , p_r\}$ be a basis of the orthogonal complement of $\text{ span }\{z_1,\ldots ,z_m\}$. Then, $y \in z_0 + \text{ span }\{z_1,\ldots ,z_m\}$ if and only if

$$\begin{aligned} p_1^T y = p_1^T z_0, \ldots , p_m^T y = p_m^T z_0. \end{aligned}$$

We can consider each $p_i$ as a polynomial in $\mathbb {R}[x]_{\mathcal {A}}$. Let $Z = \begin{bmatrix} z_1&\cdots&z_m \end{bmatrix}$. Assume $\text{ rank }(Z) = m$. If $y = z_0 -Z \lambda$, then

$$\begin{aligned} \lambda = (Z^TZ)^{-1} Z^T(z_0-y). \end{aligned}$$

Let $p_0$ be a polynomial in $\mathbb {R}[x]_{\mathcal {A}}$ such that

$$\begin{aligned} \langle p_0, y \rangle = \ell ^T (Z^TZ)^{-1} Z^T y = \ell ^T \lambda . \end{aligned}$$

Then (4.9) is equivalent to

$$\begin{aligned} \left\{ \begin{array}{rl} \min &{} \langle p_0, y \rangle \\ s.t. &{} \langle p_i, y \rangle = p_i^T z_0\,(i=1,\ldots ,m), \quad y \in \fancyscript{R}_{\mathcal {A}}(K). \end{array} \right. \end{aligned}$$

(4.10)

If $y^*$ is a minimizer of (4.10), then

$$\begin{aligned} \lambda ^* = (Z^TZ)^{-1} Z^T(z_0-y^*) \end{aligned}$$

is a maximizer of (4.9). Similarly, every linear optimization problem with cone $\fancyscript{P}_{\mathcal {A}}(K)$, which is given in the form (4.1), can also be formulated like (4.2).

Example 4.11

Let $K = \mathbb {S}^{n-1}$ and $\mathcal {A}= \{\alpha \in \mathbb {N}^n: |\alpha |=d\}$ ($d$ is even). Then $\fancyscript{R}_{\mathcal {A}}(K)$ is equivalent to $Q_{n,d}$, the cone of sums of $d$-th powers of real linear forms in $n$ variables (cf. [36, Sec. 6.2]).

• (i) The sextic form $(x_1^2+x_2^2+x_3^2)^3$ belongs to $Q_{3,4}$ (cf. [41]). We want to know the maximum $\lambda$ such that

  $$\begin{aligned} (x_1^2+x_2^2+x_3^2)^3 - \lambda (x_1^6+x_2^6+x_3^6) \in Q_{3,6}. \end{aligned}$$

  The problem is equivalent to finding the biggest $\lambda$ such that $z_0 - \lambda z_1 \in \fancyscript{R}_{\mathcal {A}}(K),$ where $z_0,z_1$ are tms’ whose entries are zeros except

  $$\begin{aligned}&(z_0)_{(6,0,0)} =(z_0)_{(0,6,0)} = (z_0)_{(0,0,6)} = 1, \quad (z_0)_{(2,2,2)} = 1/15,\\&(z_0)_{(4,2,0)} = (z_0)_{(2,4,0)} = (z_0)_{(0,4,2)} = (z_0)_{(0,2,4)} \!=\! (z_0)_{(4,0,2)} \!=\! (z_0)_{(2,0,4)} \!=\! 1/5,\\&(z_1)_{(6,0,0)} = (z_1)_{(0,6,0)} = (z_1)_{(0,0,6)} = 1. \end{aligned}$$

  We formulate this problem in the form (4.10) and then solve it by Algorithm 4.1. For $k=4$, $y^{*,4} \in \fancyscript{R}_{\mathcal {A}}(K)$ (verified by Algorithm 4.2 of [36]), and $\lambda ^{*,4}=2/3$. Since $c^k=b^k$ for $k=4$, the maximum $\lambda$ in the above is $2/3$, which confirms the result of Reznick [41, p. 146].

• (ii) We want to know the maximum $\lambda _1+\lambda _2$ such that

  $$\begin{aligned} (x_1^2+x_2^2+x_3^2)^3 - \lambda _1 (x_1^3x_2^3+x_2^3x_3^3+x_3^3x_1^3) - \lambda _2 x_1^2x_2^2x_3^2 \in Q_{3,6}. \end{aligned}$$

  The problem is equivalent to

  $$\begin{aligned} \max \quad \lambda _1+\lambda _2 \quad s.t. \quad z_0 - \lambda _1 z_1 - \lambda _2 z_2 \in \fancyscript{R}_{\mathcal {A}}(K) \end{aligned}$$

  where $z_0$ is same as in (i) and $z_1,z_2$ are tms’ whose entries are zeros except

  $$\begin{aligned} (z_1)_{(3,3,0)} = (z_1)_{(3,0,3)} = (z_1)_{(0,3,3)} = 1/20, \quad (z_2)_{(2,2,2)} = 1/90. \end{aligned}$$

  We formulate this problem in the form (4.10) and solve it by Algorithm 4.1. For $k=3$, $y^{*,3} \in \fancyscript{R}_{\mathcal {A}}(K)$ (verified by Algorithm 4.2 of [36]), and $\lambda ^{*,3}=(2,6)$. Since $c^k=b^k$ for $k=3$, we know the optimal $\lambda$ in the above is $(2,6)$. The SOEP decomposition of the polynomial $(x_1^2+x_2^2+x_3^2)^3 - 2(x_1^3x_2^3+x_2^3x_3^3+x_3^3x_1^3) - 6 x_1^2x_2^2x_3^2$ is

  $$\begin{aligned} \frac{7}{50} \sum _{ 1\le i < j\le 3 } (x_i - x_j )^6 + \sum _{ 1\le i \ne j\le 3 } \left( \left( \frac{1}{\sqrt{10}}-\frac{\sqrt{2}}{5} \right) ^{1/3} x_i + \left( \frac{1}{\sqrt{10}}+\frac{\sqrt{2}}{5} \right) ^{1/3} x_j \right) ^6. \end{aligned}$$

$\square$

5 Feasibility and infeasibility

A basic question in linear optimization is to check whether a cone intersects an affine subspace or not. For the cones $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$, this question is about checking whether the optimization problems (4.1) and (4.2) are feasible or not. If they are feasible, we want to get a feasible point; if they are not, we want a certificate for the infeasibility.

5.1 Finding feasible points

First, we discuss how to check whether (4.1) is feasible or not. Suppose $a_1,\ldots ,a_m \in \mathbb {R}[x]_{\mathcal {A}}$ and $b\in \mathbb {R}^m$ are given as in (4.1), while the objective $c$ is not necessarily given. Generally, we can assume $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full. $\big ($Otherwise, if $\mathbb {R}[x]_{\mathcal {A}}$ is not $K$-full, let $\mathcal {A}^\prime := \mathcal {A}\cup \{0\}$, then $\mathbb {R}[x]_{\mathcal {A}^\prime }$ is always $K$-full because $1 \in \mathbb {R}[x]_{\mathcal {A}^\prime }$. Since $a_1,\ldots ,a_m \in \mathbb {R}[x]_{\mathcal {A}}$, (4.1) is feasible if and only if there exists $w \in \mathbb {R}^{\mathcal {A}^\prime }$ satisfying

$$\begin{aligned} \langle a_i, w \rangle = b_i \,( 1 \le i \le m), \quad w \in \fancyscript{R}_{\mathcal {A}^\prime }(K). \end{aligned}$$

(5.1)

This is because: (i) if $y$ is feasible for (4.1), then $y$ can be extended to a tms $w \in \fancyscript{R}_{\mathcal {A}^\prime }(K)$, i.e., $y = w|_{\mathcal {A}}$ (cf. [36, Prop. 3.3]), and such $w$ satisfies (5.1); (ii) if $w$ satisfies (5.1), then the truncation $y = w|_{\mathcal {A}}$ satisfies (4.1).$\big )$

Choose $c \in \mathbb {R}[x]_{\mathcal {A}}$ such that $c>0$ on $K$. Consider the resulting optimization problems (4.1) and (4.2). For such $c$, the dual problem (4.2) has an interior point. We can apply Algorithm 4.1 to solve (4.1)–(4.2). If (4.1) is feasible, we can get a feasible point of (4.1).

Example 5.1

Let $\mathcal {A}=\mathbb {N}_6^3$ and $K=[-1, 1]^3$ be the unit cube, which is defined by $h=(0)$ and $g=(1-x_1^2,1-x_2^2,1-x_3^2)$. We want to know whether there exists a measure $\mu$ supported in $[-1,1]^3$ such that

$$\begin{aligned}&\int (x_1 x_2 + x_2x_3 + x_3x_1)\mathtt {d} \mu = 0, \, \int (x_1^2x_2^2+x_2^2x_3^2+x_3^2x_1^2) \mathtt {d} \mu = 1, \,\\&\qquad \qquad \qquad \qquad \int (x_1^3x_2^2 + x_2^3x_3^2 + x_3^3x_1^2) \mathtt {d} \mu = 1. \end{aligned}$$

Let $a_1,a_2,a_3$ be the polynomials inside the above integrals, respectively. This problem is equivalent to whether there exists $y \in \fancyscript{R}_{\mathcal {A}}([-1,1]^3)$ satisfying

$$\begin{aligned} \langle a_1, y \rangle = 0, \quad \langle a_2, y \rangle = 1, \quad \langle a_3, y \rangle = 1. \end{aligned}$$

Choose $c = \sum _{ 0 \le |\alpha | \le 3} x^{2\alpha }$. For $k=3$, $y^{*,3}$ admits the measure $\frac{1}{2} \delta _{(0, 1, -1)} + \frac{1}{6} \delta _{(1,1,1)},$ which satisfies the above. $\square$

Second, we discuss how to check whether (4.2) is feasible. Suppose $c,a_1,\ldots ,a_m \in \mathbb {R}[x]_{\mathcal {A}}$ are given, while $b$ is not necessarily. Let $k=\lceil \deg (\mathcal {A})/2 \rceil$. Solve the semidefinite feasibility problem

$$\begin{aligned} c -\lambda _1 a_1 - \cdots - \lambda _m a_m \in Q_k(g) + I_{2k}(h). \end{aligned}$$

(5.2)

If (5.2) is feasible, we can get a feasible point of (4.2); if not, let $k:=k+1$ and solve (5.2) again. Repeat this process. If the affine subspace $c + \text{ span }\{a_1,\ldots ,a_m\}$ intersects the interior of $\fancyscript{P}_{\mathcal {A}}(K)$, we can always find a feasible point of (4.2) by solving (5.2). This can be implied by Proposition 3.5, under the archimedeanness. If $c + \text{ span }\{a_1,\ldots ,a_m\}$ intersects a generic point of the boundary of $\fancyscript{P}_{\mathcal {A}}(K)$, we can also get a feasible point of (4.2) by solving (5.2) (cf. [35]). In the remaining cases, it is still an open question to find a feasible point of (4.2) by using SOS relaxations, to the best of the author’s knowledge.

Example 5.2

We want to find $\lambda _1,\lambda _2$ such that $c - \lambda _1 a_1 - \lambda _2 a_2 \in P_{3,6},$ where

$$\begin{aligned} c = x_1^2( x_1^4 + x_2^2x_3^2&- x_1^2(x_2^2+x_3^2) ), a_1 = x_2^2( x_2^4 + x_3^2x_1^2 - x_2^2(x_3^2+x_1^2) ),\\ a_2&= x_3^2( x_3^4 + x_1^2x_2^2 - x_3^2(x_1^2+x_2^2) ) . \end{aligned}$$

For $k=4$, (5.2) is feasible with $(\lambda _1, \lambda _2) = (-1,-1)$. $\square$

5.2 Infeasibility certificates

First, we prove a certificate for the infeasibility of (4.1). Suppose $a_1,\ldots ,a_m \in \mathbb {R}[x]_{\mathcal {A}}$ and $b\in \mathbb {R}^m$ are given, while $c$ is not necessarily.

Lemma 5.3

Let $K$ be as in (1.2). Then, we have:

• (i) The problem (4.1) is infeasible if (4.3) is infeasible for some order $k$; (4.3) is infeasible if there exist $\lambda$ and $k$ such that

  $$\begin{aligned} b^T\lambda < 0, \quad \lambda _1 a_1 + \cdots + \lambda _m a_m \in Q_k(g) + I_{2k}(h). \end{aligned}$$

  (5.3)

• (ii) Suppose $I(h)+Q(g)$ is archimedean and there exists $a \in \text{ span }\{a_1,\ldots ,a_m\}$ such that $a>0$ on $K$. If (4.1) is infeasible, then (5.3) holds for some $\lambda ,k$ and (4.3) is infeasible.

Proof

• (i) The problem (4.3) is a relaxation of (4.1), i.e., the set of feasible $y$ in (4.1) is contained in that of (4.3). Clearly, if (4.3) is infeasible, then (4.1) is also infeasible. If (5.3) holds for some $\lambda ,k$, then (4.3) must be infeasible, because any feasible $y$ in (4.3) would result in the contradiction

  $$\begin{aligned} 0 > b^T\lambda = \sum _{i=1}^m \lambda _i \langle a_i, y \rangle = \left\langle \sum _{i=1}^m \lambda _i a_i, y \right\rangle \ge 0. \end{aligned}$$

• (ii) Suppose (4.1) is infeasible. Consider the optimization problem

  $$\begin{aligned} \max \quad 0 \quad s.t. \quad \langle a_i, y \rangle = b_i \, (i =1,\ldots , m), \quad y \in \fancyscript{R}_{\mathcal {A}}(K). \end{aligned}$$

  (5.4)

  Its dual problem is

  $$\begin{aligned} \min _{ \lambda \in \mathbb {R}^m } \quad b^T\lambda \quad s.t. \quad \lambda _1 a_1 + \cdots + \lambda _m a_m \in \fancyscript{P}_{\mathcal {A}}(K). \end{aligned}$$

  (5.5)

  By the assumption, $\fancyscript{R}_{\mathcal {A}}(K)$ and $\fancyscript{P}_{\mathcal {A}}(K)$ are closed convex cones (cf. Proposition 3.2), and (5.5) has an interior point. So, the strong duality holds and (5.5) must be unbounded from below (cf. [1, Theorem 2.4.I]), i.e., there exists $\hat{\lambda }$ satisfying

  $$\begin{aligned} b^T \hat{\lambda } <0, \quad \hat{\lambda }_1 a_1 + \cdots + \hat{\lambda }_m a_m \in \fancyscript{P}_{\mathcal {A}}(K). \end{aligned}$$

  By the assumption, there exists $\bar{\lambda }$ such that $\bar{\lambda }_1 a_1 + \cdots + \bar{\lambda }_m a_m >0$ on $K$. For $\epsilon >0$ small, $\lambda :=\hat{\lambda } + \epsilon \bar{\lambda }$ satisfies (5.3) for some $k$, by Theorem 2.1. By item (i), we know (4.3) is infeasible.

$\square$

Here is an example for the infeasibility certificate (5.3).

Example 5.4

Let $\mathcal {A}=\mathbb {N}_6^2$ and $K=\mathbb {S}^1$ be the unit circle in $\mathbb {R}^2$, defined by $h=(x_1^2+x_2^2-1)$ and $g=(0)$ as in (1.2). We want to know whether there exists a measure $\mu$ supported in $\mathbb {S}^1$ such that

$$\begin{aligned} \int x_1^2 x_2^2 \mathtt {d} \mu = 1, \, \int (x_1^4+x_2^4) \mathtt {d} \mu = 1, \, \int (x_1^6+x_2^6) \mathtt {d} \mu = 1. \end{aligned}$$

This is equivalent to checking whether there exists $y \in \fancyscript{R}_{\mathcal {A}}(\mathbb {S}^1)$ satisfying

$$\begin{aligned} \langle a_1, y \rangle = 1, \quad \langle a_2, y \rangle = 1, \quad \langle a_3, y \rangle = 1, \quad \end{aligned}$$

with $a_1 = x_1^2x_2^2$, $a_2 =x_1^4+x_2^4$, $a_3 = x_1^6+x_2^6$. Indeed, such an $\mathcal {A}$-tms $y$ does not exist, because (5.3) is satisfied for $\lambda =(-3,1,1)$: $\lambda _1 + \lambda _2 + \lambda _3 <0$ and

$$\begin{aligned} -3a_1+a_2+a_3 = 2(x_1^2-x_2^2)^2 + (x_1^4-x_1^2x_2^2+x_2^4) h \in I_6(h) + Q_3(g). \end{aligned}$$

By Lemma 5.3, the above measure $\mu$ does not exist. $\square$

Second, we give a certificate for the infeasibility of (4.2). Suppose $c,a_1,\ldots ,a_m \in \mathbb {R}[x]_{\mathcal {A}}$ are given, while $b$ is not necessarily.

Lemma 5.5

Let $K$ be compact and $c,a_1, \ldots , a_m \in \mathbb {R}[x]_{\mathcal {A}}$ be given.

• (i) Problem (4.2) is infeasible if there exists $y$ satisfying

  $$\begin{aligned} c^Ty < 0, \quad \langle a_i, y \rangle = 0 \, (i =1,\ldots , m), \quad y \in \fancyscript{R}_{\mathcal {A}}(K). \end{aligned}$$

  (5.6)

• (ii) Suppose there does not exist $0 \ne a \in \text{ span }\{a_1,\ldots ,a_m\}$ such that $a\ge 0$ on $K$. If (4.2) is infeasible, then there exists $y$ satisfying (5.6).

Remark 5.6

Clearly, if there exists $a \in \text{ span }\{a_1,\ldots ,a_m\}$ such that $a > 0$ on $K$, then (4.2) must be feasible. Therefore, for (4.2) to be infeasible, none of polynomials in $\text{ span }\{a_1,\ldots ,a_m\}$ can be positive on $K$. So, the assumption in Lemma 5.5 (ii) is almost necessary for (4.2) to be infeasible. Indeed, it cannot be removed. For instance, consider $K = \mathbb {S}^1$ and $\mathcal {A}= \{ |\alpha | = 2\}$. Choose $c,a_1$ such that $c(\lambda ) = x_1x_2 - \lambda _1 x_1^2.$ Clearly, $c(\lambda ) \not \in \fancyscript{P}_{\mathcal {A}}( \mathbb {S}^1 )$ for all $\lambda$. For all $y \in \fancyscript{R}_{\mathcal {A}}( \mathbb {S}^1 )$, if $\langle a_1, y \rangle =0$, then $\langle c, y \rangle =0$. This is because

$$\begin{aligned} \left| \int x_1 x_2 \mathtt {d} \mu \right| \le \left( \int x_1^2 \mathtt {d} \mu \right) ^{1/2} \left( \int x_2^2 \mathtt {d} \mu \right) ^{1/2} \end{aligned}$$

for all nonnegative measure $\mu$, by the Cauchy-Schwarz inequality. So, there is no $y$ satisfying (5.6), while (4.2) is infeasible.

Proof

(of Lemma 5.5)

• (i) Suppose (5.6) holds. If (4.2) has a feasible $\lambda$, then we get

  $$\begin{aligned} 0 \le \langle c(\lambda ), y \rangle = \langle c, y \rangle - \lambda _1 \langle a_1, y \rangle - \cdots - \lambda _m \langle a_m, y \rangle = \langle c, y \rangle < 0, \end{aligned}$$

  a contradiction. So (4.2) must be infeasible if (5.6) is satisfied.

• (ii) Without loss of generality, we can assume $a_1,\ldots ,a_m$ are linearly independent in the quotient space $\mathbb {R}[x]/I(K)$ (i.e., the space of polynomial functions defined on $K$ [4], where $I(K)$ is the ideal of all polynomials $p$ such that $p \equiv 0$ on $K$). We show that there exists $T>0$ such that

  $$\begin{aligned} \fancyscript{P}_{\mathcal {A}}(K) \cap (c+\text{ span }\{a_1,\ldots ,a_m\}) \subseteq B(0,T). \end{aligned}$$

  (5.7)

  (The left above intersection might be empty.) Suppose otherwise such $T$ does not exist, then there exists a sequence $\{\lambda ^k\}$ such that $\Vert \lambda ^k\Vert _2 \rightarrow \infty$ and $c(\lambda ^k) \in \fancyscript{P}_{\mathcal {A}}(K)$ for all $k$. The sequence $\{ \lambda ^k/\Vert \lambda ^k\Vert _2 \}$ is bounded. We can generally assume $\lambda ^k/\Vert \lambda ^k\Vert _2 \rightarrow \lambda ^* \ne 0$. Clearly, $c(\lambda ^k)/\Vert \lambda ^k\Vert _2 \in \fancyscript{P}_{\mathcal {A}}(K)$ for all $k$. So,

  $$\begin{aligned} c(\lambda ^k)/\Vert \lambda ^k\Vert _2 \rightarrow a^*:= -( \lambda _1^*a_1 + \cdots + \lambda _m^*a_m ) \in \fancyscript{P}_{\mathcal {A}}(K). \end{aligned}$$

  Since $a_1,\ldots ,a_m$ are linearly independent in $\mathbb {R}[x]/I(K)$ and $\lambda ^*\ne 0$, we know $a^*|_K \not \equiv 0$ and $a^*|_K \ge 0$. This contradicts the given assumption. So (5.7) must be satisfied for some $T>0$. Let

  $$\begin{aligned} \fancyscript{C}_1 = \{ p \in \fancyscript{P}_{\mathcal {A}}(K) \mid \Vert p\Vert _2 \le T\}, \quad \fancyscript{C}_2 = c+ span\{a_1, \ldots , a_m\}. \end{aligned}$$

  By (5.7), (4.2) is infeasible if and only if $\fancyscript{C}_1 \cap \fancyscript{C}_2 = \emptyset$. Because $K$ is compact, the set $\fancyscript{C}_1$ is compact convex, and $\fancyscript{C}_2$ is closed convex. By the strict convex set separation theorem, they do not intersect if and only if there exists $y \in \mathbb {R}^{\mathcal {A}}$ and $\tau \in \mathbb {R}$ such that

  $$\begin{aligned} \langle p, y \rangle > \tau \quad \forall \, p \in \fancyscript{C}_1,\\ \langle p, y \rangle < \tau \quad \forall \, p \in \fancyscript{C}_2. \end{aligned}$$

  The first above inequality implies $\tau < 0$ and $y \in \fancyscript{R}_{\mathcal {A}}(K)$, and the second one implies $c^Ty < 0$ and $\langle a_i, y \rangle = 0$ for all $i$. Thus, this $y$ satisfies (5.6). $\square$

The certificate (5.6) can be checked by solving the feasibility problem:

$$\begin{aligned} c^Ty = -1, \quad \langle a_i, y \rangle = 0 \, (i =1,\ldots , m), \quad y \in \fancyscript{R}_{\mathcal {A}}(K). \end{aligned}$$

(5.8)

Example 5.7

Let $K=\mathbb {S}^2$ and $\mathcal {A}= \{\alpha \in \mathbb {N}^n: |\alpha | = 6\}$. Then $\fancyscript{P}_{\mathcal {A}}(K)$ equals $P_{3,6}$, the cone of nonnegative ternary sextic forms. We want to know whether there exist $\lambda _1, \lambda _2, \lambda _3$ such that

$$\begin{aligned} \underbrace{x_1^2x_2^2(x_1^2+x_2^2-4x_3^2) +x_3^6}_{c} - \lambda _1 \underbrace{x_1^3x_2^3}_{a_1} - \lambda _2 \underbrace{x_1^3x_3^3}_{a_2} - \lambda _3 \underbrace{x_2^3x_3^3}_{a_3} \in P_{3,6}. \end{aligned}$$

Indeed, there are no $\lambda _1, \lambda _2, \lambda _3$ satisfying the above. To get a certificate for this, solve the feasibility problem (5.8). It has a feasible tms $y$ that admits the finitely atomic measure $\frac{27}{4} \big ( \delta _{(1, 1, 1)/\sqrt{3}} + \delta _{(-1, 1, 1)/\sqrt{3}} + \delta _{(1, -1, 1)/\sqrt{3}} + \delta _{(1, 1, -1)/\sqrt{3}} \big ).$ $\square$

Appendix: Checking \(K\)-fullness

Recall that $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full if there exists $p \in \mathbb {R}[x]_{\mathcal {A}}$ that is positive on $K$. We can check whether $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full or not as follows. Clearly, $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full if and only if there exists $\lambda \in \mathbb {R}^{\mathcal {A}}$ such that

$$\begin{aligned} \sum _{\alpha \in \mathcal {A}} \lambda _\alpha x^\alpha - 1 \in \fancyscript{P}_{\mathcal {A}^\prime }(K), \end{aligned}$$

(6.1)

where $\mathcal {A}^\prime = \mathcal {A}\cup \{ 0 \}$. Since $1\in \fancyscript{P}_{\mathcal {A}^\prime }(K)$, $\mathbb {R}[x]_{\mathcal {A}^\prime }$ is always $K$-full. Thus, checking $K$-fullness is reduced to solving a feasibility/infeasiblity issue. This question was discussed in Sect. 5. Suppose $K$ is a compact semialgebraic set as in (1.2). If $\mathbb {R}[x]_{\mathcal {A}}$ is $K$-full, we can get a $\lambda$ satisfying (6.1) (cf. Sect. 5.1). If $\mathbb {R}[x]_{\mathcal {A}}$ is not $K$-full, we can get a certificate for nonexistence of such $\lambda$, under a general assumption (cf. Lemma 5.5).