On the complexity of matrix Putinar’s Positivstellensätz

Lei Huang Department of Mathematics, University of California San Diego () [email protected]

Abstract

This paper studies the complexity of matrix Putinar’s Positivstellensätz on the semialgebraic set that is given by the polynomial matrix inequality. When the quadratic module generated by the constrained polynomial matrix is Archimedean, we prove a polynomial bound on the degrees of terms appearing in the representation of matrix Putinar’s Positivstellensätz. Estimates on the exponent and constant are given. As a byproduct, a polynomial bound on the convergence rate of matrix sum-of-squares relaxations is obtained, which resolves an open question raised by Dinh and Pham. When the constraining set is unbounded, we also prove a similar bound for the matrix version of Putinar–Vasilescu’s Positivstellensätz by exploiting homogenization techniques.

keywords:

Polynomial matrix, polynomial optimization, matrix Putinar’s Positivstellensätz, matrix sum-of-squares relaxations

{MSCcodes}

90C23, 65K05, 90C22, 90C26

1 Introduction

Optimization with polynomial matrix inequalities has broad applications [6, 12, 16, 17, 18, 25, 47, 48, 57, 58]. A fundamental question to solve it globally is how to efficiently characterize polynomial matrices that are positive semidefinite on the semialgebraic set described by the polynomial matrix inequality. To be more specific, given an $\ell$ -by- $\ell$ symmetric polynomial matrix $F(x)$ in $x:=(x_{1},\dots,x_{n})$ and a semialgebraic set $K$ , how can we certify that $F\succeq 0$ on $K$ ? Here, the set $K$ is given as

(1.1)

K=\{x\in\mathbb{R}^{n}\mid G(x)\succeq 0\},

where $G(x)$ is an $m$ -by- $m$ symmetric polynomial matrix.

When $F(x)$ is a scalar polynomial (i.e., $\ell=1$ ) and $G(x)$ is a diagonal matrix whose diagonal entries are polynomials $g_{1}(x)$ , $\dots$ , $g_{m}(x)$ , $K$ can be equivalently described as

(1.2)

K=\{x\in\mathbb{R}^{n}\mid g_{1}(x)\geq 0,\dots,g_{m}(x)\geq 0\}.

Then, it reduces to the classical Positivstellensätz in real algebraic geometry and polynomial optimization. A polynomial $p$ is said to be a sum of squares (SOS) if $p=p_{1}^{2}+\dots+p_{t}^{2}$ for polynomials $p_{1},\dots,p_{t}$ . Schmüdgen [49] proved that if $K$ is compact and $F>0$ on $K$ , then there exist SOS polynomials $\sigma_{\alpha}$ such that

(1.3)

F=\sum\limits_{\alpha\in\{0,1\}^{m}}\sigma_{\alpha}g_{1}^{\alpha_{1}}\cdots g_{m}^{\alpha_{m}}.

When the quadratic module of scalar polynomials $\mbox{QM}[G]$ generated by $G$ is Archimedean (a condition slightly stronger than compactness, refer to Section 2.2), Putinar [42] showed that if $F>0$ on $K$ , then there exist SOS polynomials $\sigma_{0},\sigma_{1},\dots,\sigma_{m}$ such that

(1.4)

F=\sigma_{0}+\sigma_{1}g_{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+\cdots+}\sigma_{m}g_{m},

which is referred to as Putinar’s Positivstellensätz in the literature.

The complexities of the above scalar Positivstellensätze have been studied extensively. Suppose that $K\subseteq(-1,1)^{n}$ and the degree of $F$ is $d$ . For the degree $d$ , denote

\mathbb{N}_{d}^{n}:=\left\{\alpha\in\mathbb{N}^{n}\mid\left.\alpha_{1}+\cdots+\alpha_{n}\leq d\right\}.\right.

For a polynomial $p=\sum\limits_{\alpha\in\mathbb{N}_{d}^{n}}p_{\alpha}\frac{|\alpha|!}{\alpha_{1}!\cdots\alpha_{n}!}x^{\alpha}$ , denote the norm $\|p\|=\max\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}|p_{\alpha}|}:\alpha\in\mathbb{N}_{d}^{n}\}.$ It was shown in [51] that if ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}F\geq F_{\min}>0}$ on $K$ , then for

k\geq cd^{2}\left(1+\left(d^{2}n^{d}\frac{\|F\|}{F_{\min}}\right)^{c}\right),

there exist SOS polynomials $\sigma_{\alpha}$ with $\deg(\sigma_{\alpha}g_{1}^{\alpha_{1}}\cdots g_{m}^{\alpha_{m}})\leq k$ such that (1.3) holds. Here, $c$ is a positive constant that depends on the constraining polynomials $g_{1},\dots,g_{m}$ . Based on the above bound, Nie and Schweighofer [39] proved that if $\mbox{QM}[G]$ is Archimedean, there exists a constant $c>0$ , depending on $g_{1},\dots,g_{m}$ , such that if

(1.5)

k\geq c\exp\left(\left(d^{2}n^{d}\frac{\|F\|}{F_{\min}}\right)^{c}\right),

then (1.4) holds for some SOS polynomials $\sigma_{0}$ , $\dots$ , $\sigma_{m}$ with $\deg(\sigma_{0})\leq k$ , $\deg(\sigma_{i}g_{i})\leq k$ $(i=1,\dots,m)$ . Recently, Baldi and Mourrain improved the exponent bound (1.5) to a polynomial bound. It was shown in [2] that the same result holds if

(1.6)

k\geq\gamma d^{3.5nL}\left(\frac{\|F\|_{\max}}{F_{\min}}\right)^{2.5nL}.

In the above, $\gamma$ is a positive constant depending on $n$ , $g_{1},\dots,g_{m}$ , $L$ is the Łojasiewicz exponent associated with $g_{1},\dots,g_{m}$ and $\|F\|_{\max}$ is the max norm on the cube $[-1,1]^{n}$ . The bound (1.6) has been further improved in [3] by removing the dependency of the exponent on the dimension $n$ and providing estimates on the constant $\gamma$ . There exist better degree bounds when the set $K$ is specified, see [1, 4, 12, 53, 54, 55]. We also refer to [29] when $F,g_{1},\dots,g_{m}$ admit the correlative sparse sparsity.

Based on Putinar’s Positivstellensätz, Lasserre [31] introduced the Moment-SOS hierarchy for solving polynomial optimization and proved its asymptotic convergence. The above degree bounds give estimates on the convergence rates of the Moment-SOS hierarchy directly. We also refer to [8, 20, 21, 23, 36, 37, 46] for the finite convergence of the Moment-SOS hierarchy under some regular assumptions.

When $F$ , $G$ are general polynomial matrices, a matrix version of Putinar’s Positivstellensätz was provided in [28, 48]. Let $\mathbb{R}[x]:=\mathbb{R}\left[x_{1},\ldots,x_{n}\right]$ be the ring of polynomials in $x:=\left(x_{1},\ldots,x_{n}\right)$ with real coefficients. A polynomial matrix $S(x)$ is SOS if $S(x)=H(x)^{T}H(x)$ for some polynomial matrix $H(x)$ . The set of all $\ell$ -by- $\ell$ SOS polynomial matrices in $x$ is denoted as $\Sigma[x]^{\ell}$ . The quadratic module of $\ell$ -by- $\ell$ polynomial matrices generated by $G(x)$ is the set

\mbox{QM}[G]^{\ell}:=\left\{S+\sum_{i=1}^{t}P_{i}^{T}GP_{i}\mid t\in\mathbb{N},~{}S\in\Sigma[x]^{\ell},~{}P_{i}\in\mathbb{R}[x]^{m\times\ell}\right\}.

The set $\mbox{QM}[G]^{\ell}$ is Archimedean if there exists a scalar $r>0$ such that $(r-\|x\|_{2}^{2})\cdot I_{\ell}\in\mathrm{QM}[G]^{\ell}$ . When the quadratic module $\mbox{QM}[G]^{\ell}$ is Archimedean, it was proved in [28, 48] that if $F\succ 0$ on $K$ , then we have that $F\in\mbox{QM}[G]^{\ell}$ . For the case that $F$ is a polynomial matrix and $G$ is diagonal (i.e., $K$ is as in (1.2)), the exponential bound (1.5) was generalized to the matrix case in [15]. There are specific estimates on degree bounds when $G$ is a simple set defined by scalar polynomial inequalities. We refer to [12] for the sphere case and refer to [55] for the boolean hypercube case. When $G$ is a general polynomial matrix, the complexity of matrix Putinar’s Positivstellensätz is open, to the best of the author’s knowledge. We also refer to [7, 27, 50] for other types of SOS representations for polynomial matrices.

Contributions

This paper studies the complexity of matrix Putinar’s Positivstellensätz. Throu-
ghout the paper, we assume that

K\subseteq\{x\in\mathbb{R}^{n}\mid 1-\|x\|_{2}^{2}\geq 0\},

unless otherwise specified. Denote the scaled simplex

(1.7)

\bar{\Delta}:=\left\{x\in\mathbb{R}^{n}\mid 1+x_{1}\geq 0,\ldots,1+x_{n}\geq 0,\sqrt{n}-x_{1}-\cdots-x_{n}\geq 0\right\}.

Note that the set $K\subset\bar{\Delta}$ in our settings. The degree of the polynomial matrix $G$ is denoted by $d_{G}$ , i.e.,

(1.8)

d_{G}=\max\{\deg(G_{ij}),~{}1\leq i,j\leq m\}.

For a positive integer $m$ , denote

(1.9)

\theta(m)=\sum\limits_{i=1}^{m}\left(\prod_{k=m+1-i}^{m}\frac{k(k+1)}{2}\right).

Let $\|F\|_{B}$ be the Bernstein norm of $F$ on the scaled simplex $\bar{\Delta}$ (see Section 3 for details).

The following is our main result. It generalizes the recent results of scalar Putinar’s Positivstellensätz, as shown in [2, 3], to the matrix case and provides the first degree bound for matrix Putinar’s Positivstellensätz.

Theorem 1.1.

Let $K$ be as in (1.1) with $m\geq 2$ . Suppose $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix of degree $d$ , and $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mbox{QM}[G]^{\ell}$ . If $F(x)\succeq F_{\min}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}I_{\ell}}\succ 0$ on $K$ , then for

(1.10)

k\geq C\cdot{8}^{7\eta}\cdot 3^{6(m-1)}\theta(m)^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14\eta}\left(\frac{\|F\|_{B}}{F_{\min}}\right)^{7\eta+3},

there exists an $\ell$ -by- $\ell$ SOS matrix $S$ and polynomial matrices $P_{i}\in\mathbb{R}[x]^{m\times\ell}$ $(i=1,\dots,t)$ with

\deg(S)\leq k,~{}\deg(P_{i}^{T}GP_{i})\leq k~{}(i=1,\dots,t),

such that

(1.11)

F=S+P_{1}^{T}GP_{1}+\cdots+P_{t}^{T}GP_{t}.

In the above, $\kappa,\eta$ are respectively the Łojasiewicz constant and exponent in (5.3), and $C>0$ is a constant independent of $F$ , $G$ . Furthermore, the Łojasiewicz exponent can be estimated as

\eta\leq(3^{m-1}d_{G}+1)(3^{m}d_{G})^{n+\theta(m)-2}.

The positivity certificate (1.11) can be applied to construct matrix SOS relaxations for solving polynomial matrix optimization [16, 48]. As a byproduct of Theorem 1.1, we can obtain a polynomial bound on the convergence rate of matrix SOS relaxations (see Theorem 5.7), which resolves an open question raised in [10].

When $F(x)$ is a scalar polynomial and $G(x)$ is diagonal with diagonal entries $g_{1}(x),\dots,g_{m}(x)\in\mathbb{R}[x]$ , it was shown in [3] that if $F\geq F_{\min}>0$ on $K$ , then $f$ admits a representation as in (1.4) for

k\geq C\cdot 2^{\eta}\cdot n^{2}md_{G}^{6}d^{2\eta}\kappa^{7}\left(\frac{\|F\|_{B}}{F_{\min}}\right)^{7\eta+3},

where $\kappa,\eta$ are respectively the Łojasiewicz constant and exponent, and $C>0$ is a constant independent of $F$ , $G$ . Comparing this with the bound as in Theorem 1.1, one important additional factor is $3^{6(m-1)}\theta(m)^{3}$ . This comes from the estimates on the quantity and degree bounds of scalar polynomials that can be used to describe the polynomial matrix inequality $G(x)\succeq 0$ . Please see Section 4 for details. The other additional factors such as ${8}^{7\eta}$ , $d^{14\eta}$ are artifacts of the proof technique. They primarily arise from the degree estimates of $h_{i}g_{i}$ in Theorem 3.5. Since we want the constant $C$ to be independent of $F$ and $G$ , we retain all these factors in Theorem 1.1.

Remark. The assumption that $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mbox{QM}[G]^{\ell}$ is not serious. When the quadratic module $\mbox{QM}[G]^{\ell}$ is Archimedean, i.e., $(r-\|x\|_{2}^{2})\cdot I_{\ell}\in\mathrm{QM}[G]^{\ell}$ for some $r>0$ , we have that $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mathrm{QM}[G(\sqrt{r}x)]^{\ell}$ . Theorem 1.1 remains true with $F,G$ replaced by $F(\sqrt{r}x)$ , $G(\sqrt{r}x)$ .

When $K$ is unbounded, the Putinar-type SOS representation may not hold. For the scalar case (i.e., $F\in\mathbb{R}[x]$ and $K$ is as in (1.2)), it was shown in [43, 44] that if the highest degree homogeneous term of $F$ is positive definite in $\mathbb{R}^{n}$ and $F>0$ on $K$ , then there exists a degree $k$ such that $(1+\|x\|_{2}^{2})^{k}F$ has a representation (1.4), which is referred to as Putinar-Vasilescu’s Positivstellensätz. A polynomial complexity for this type of representation was proved by Mai and Magron [35]. Recently, a matrix version of Putinar–Vasilescu’s Positivstellensätz was established in [11].

In the following, we state a bound similar to that in Theorem 1.1 for matrix Putinar–Vasilescu’s Positivstellensätz. Let $F^{hom}$ denote the highest degree homogeneous term of $F$ . The homogenization of $F$ is denoted by $\widetilde{F}$ , i.e., $\widetilde{F}(\tilde{x}):=x_{0}^{\deg(F)}F(x/x_{0})$ for $\tilde{x}:=(x_{0},x)$ . The notation $\lambda_{\min}(A)$ denotes the smallest eigenvalue of the matrix $A$ .

Theorem 1.2.

Let $K$ be as in (1.1) with $m\geq 2$ . Suppose that $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix of degree $d$ . If $F(x)\succ 0$ on $K$ and $F^{hom}\succ 0$ on $\mathbb{R}^{n}$ , then for

k\geq C\cdot{8}^{7\eta}\cdot 3^{6(m-1)}(\theta(m)+2)^{3}(n+1)^{2}(\lceil d_{G}/2\rceil)^{6}\kappa^{7}d^{14\eta}\left(\frac{\|\widetilde{F}\|_{B}}{\widetilde{F}_{\min}}\right)^{7\eta+3},

there exists an $\ell$ -by- $\ell$ SOS matrix $S$ and polynomial matrices $P_{i}\in\mathbb{R}[x]^{m\times\ell}$ $(i=1,\dots,t)$ with

\deg(S)\leq 2k+d,~{}\deg(P_{i}^{T}GP_{i})\leq 2k+d~{}(i=1,\dots,t),

such that

(1.12)

(1+\|x\|_{2}^{2})^{k}F=S+P_{1}^{T}GP_{1}+\cdots+P_{t}^{T}GP_{t}.

In the above, $\kappa$ , $\eta$ are respectively the Łojasiewicz constant and exponent in (5.8), $C>0$ is a constant independent of $F$ , $G$ , and $\widetilde{F}_{\min}$ is the optimal value of the optimization

(1.13)

\left\{\begin{array}[]{rl}\min&\lambda_{\min}(\widetilde{F}(\tilde{x}))\\ \mathit{s.t.}&(x_{0})^{2\lceil d_{G}/2\rceil-d_{G}}\widetilde{G}(\tilde{x})\succeq 0,\\ &x_{0}^{2}+x^{T}x=1.\\ \end{array}\right.

Furthermore, the Łojasiewicz exponent can be estimated as

\eta\leq(2\cdot 3^{m-1}\lceil d_{G}/2\rceil+1)(2\cdot 3^{m}\lceil d_{G}/2\rceil)^{n+\theta(m)-1}.

For unbounded optimization, the positivity of $F^{\hom}$ is also crucial for obtaining SOS-type representations because it reflects the behavior of $F$ at infinity (e.g., see [22]). The quantity $\widetilde{F}_{\min}$ is the optimal value of the homogenized optimization (1.15). It is an important quantity for evaluating the positivity of $F$ on the unbounded set $K$ , as it reflects not only the behavior of $F$ on $K$ but also its behavior at infinity. Suppose that $F(x)\succeq F_{\min}\cdot I_{\ell}\succ 0$ on $K$ , $F^{hom}\succeq F_{\min}^{\prime}\cdot I_{\ell}\succ 0$ on $\mathbb{R}^{n}$ , and $\tilde{x}=(x_{0},x)\in\mathbb{R}^{n+1}$ is a feasible point of (1.15). One can see that $x/x_{0}\in K$ and $\widetilde{F}(\tilde{x})=x_{0}^{d}F(x/x_{0})\succeq x_{0}^{d}F_{\min}\cdot I_{\ell}$ for all feasible $\tilde{x}$ with $x_{0}\neq 0$ , and $\widetilde{F}(\tilde{x})\succeq F^{\prime}_{\min}\cdot I_{\ell}$ for all feasible $\tilde{x}$ with $x_{0}=0$ . However, it is impossible to bound $\widetilde{F}_{\min}$ from below with $F^{hom}$ and $F_{\min}^{\prime}$ , since $\widetilde{F}_{\min}$ can be arbitrarily close to $0$ . For instance, consider the scalar polynomial $F(x)=(x-\epsilon)^{2}+1$ and $K=\mathbb{R}$ . Note that for $x_{0}^{2}+x^{2}=1$ , we have $\widetilde{F}(x_{0},x)=(x-\epsilon\cdot x_{0})^{2}+x_{0}^{2}=1+\epsilon^{2}\cdot x_{0}^{2}-2\epsilon\cdot x_{0}\cdot x$ . Let $x_{0}=\sin\theta$ , $x=\cos\theta$ . Then, it follows that

\begin{array}[]{ll}\widetilde{F}(x_{0},x)=1+\epsilon^{2}\cdot\sin^{2}\theta-2\cdot\epsilon\cdot\sin\theta\cos\theta&=1+\frac{\epsilon^{2}}{2}\cdot(1-\cos(2\theta))-\epsilon\cdot\sin(2\theta)\\ &=1+\frac{\epsilon^{2}}{2}-\sqrt{\epsilon^{2}+\frac{\epsilon^{4}}{4}}\sin(2\theta+\phi),\end{array}

for some $\phi\in[0,2\pi]$ . This implies that $\widetilde{F}_{\min}=1+\frac{\epsilon^{2}}{2}-\sqrt{\epsilon^{2}+\frac{\epsilon^{4}}{4}}$ . One can verify that $1+\frac{\epsilon^{2}}{2}-\sqrt{\epsilon^{2}+\frac{\epsilon^{4}}{4}}\rightarrow 0$ , as $\epsilon\rightarrow\infty$ , while $F_{\min}=F_{\min}^{\prime}=1$ for arbitrary $\epsilon$ .

The following result is a direct corollary of Theorem 1.2. Its proof is deferred to Section 5.2.

Corollary 1.3.

Let $K$ be as in (1.1) with $m\geq 2$ . Suppose that $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix with $\deg(F)=d$ . If $F\succeq 0$ on $K$ , then for any $\varepsilon>0$ , we have

(1+\|x\|_{2}^{2})^{k}(F+\varepsilon\cdot(1+\|x\|_{2}^{2})^{\lceil\frac{d+1}{2}\rceil}I_{\ell})\in\mbox{QM}[G]_{k}^{\ell},

provided that $k\geq C\cdot\varepsilon^{-7\eta-3}.$ Here, $\eta$ is the Łojasiewicz exponent in (5.8), and $C>0$ is a constant that depends on $F$ , $G$ .

Outline of the proofs

The proof of Theorem 1.1 involves three major steps:

Step 1. When $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix and $K$ is described by finitely many scalar polynomial inequalities (i.e., $K$ is as in (1.2) ), we establish a polynomial bound on degrees of terms appearing in matrix Putinar’s Positivstellensätz (see Theorem 3.5). It improves the exponential bound given by Helton and Nie [15]. The proof closely follows the idea and strategies of [2, 3], adapting it to the matrix setting. This proof is provided in Section 3 and is completed in three steps:

Step 1a. We perturb $F$ into a polynomial matrix $P$ such that $P$ is positive definite on the scaled simplex $\bar{\Delta}$ . To be more specific, we prove that there exist $\lambda>0$ and $h_{i}\in\Sigma[x]$ $(i=1,\dots,m)$ with controlled degrees such that

P(x):=F(x)-\lambda\sum_{i=1}^{m}h_{i}(x)g_{i}(x)I_{\ell}\succeq\frac{1}{4}F_{\min}\cdot I_{\ell},~{}~{}\forall~{}x\in\bar{\Delta}.

This step uses a result by Baldi-Mourrain-Parusinski [3, Proposition 3.2] about the approximation of a plateau by SOS polynomials, and some estimates on the matrix Bernstein norm (see Lemma 3.3).

Step 1b. Using the dehomogenized version of matrix Polya’s Positivstellensätz in terms of the Bernstein basis (see Lemma 3.1), we show that there exist matrices $P_{\alpha}^{(k)}\succ 0$ such that

P=\sum_{\alpha\in\mathbb{N}^{n}_{k}}P_{\alpha}^{(k)}B_{\alpha}^{k}(x),

and provide an estimate on $k$ .

Step 1c. Note that the factors of $B_{\alpha}^{k}(x)$ satisfy $1-x_{1},\dots,1-x_{n},\sqrt{n}-x_{1}-\cdots-x_{n}\in\mbox{QM}[1-\|x\|_{2}^{2}]_{2}$ . We know that $P\in\mbox{QM}[1-\|x\|_{2}^{2}]^{\ell}$ . Consequently, a polynomial bound on the degrees of terms appearing in matrix Putinar’s Positivstellensätz can be derived from the assumption that $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mbox{QM}[G]^{\ell}$ .

Step 2. When $K$ is described by a polynomial matrix inequality (i.e., $K$ is as in (1.1)), we show that $K$ can be equivalently described by finitely many scalar polynomial inequalities with exact estimates on the quantity and degrees, by exploiting a proposition due to Schmüdgen [50]. Additionally, these polynomials belong to the quadratic module generated by $G(x)$ in $\mathbb{R}[x]$ . This is discussed in Section 4.

Step 3. Finally, we prove Theorem 1.1 by applying the main result from Step 1 (i.e., Theorem 3.5) to $F$ and the equivalent scalar polynomial inequalities for $K$ obtained in Step 2. We refer to Section 5 for details.

The proof of Theorem 1.2 relies on Theorem 1.1 and homogenization techniques.

The remaining of the paper is organized as follows. Section 2 presents some backgrounds. Section 5 provides the proofs of Theorems 1.1, 1.2 and studies the convergence rate of matrix SOS relaxations. Conclusions and discussions are drawn in Section 6.

2 Preliminaries

2.1 Notations

The symbol $\mathbb{N}$ (resp., $\mathbb{R}$ ) denotes the set of nonnegative integers (resp., real numbers). Let $\mathbb{R}[x]:=\mathbb{R}\left[x_{1},\ldots,x_{n}\right]$ be the ring of polynomials in $x:=\left(x_{1},\ldots,x_{n}\right)$ with real coefficients and let $\mathbb{R}[x]_{d}$ be the ring of polynomials with degrees $\leq d$ . For $\alpha=(\alpha_{1},\ldots,\alpha_{n})\in\mathbb{N}^{n}$ and a degree $d$ , denote $|\alpha|\coloneqq\alpha_{1}+\cdots+\alpha_{n}$ , $\mathbb{N}_{d}^{n}:=\left\{\alpha\in\mathbb{N}^{n}\mid|\alpha|\leq d\right\}.$ For a polynomial $p$ , the symbol $\deg(p)$ denotes its total degree. For a polynomial matrix $P=(P_{ij}(x))\in\mathbb{R}[x]^{\ell_{1}\times\ell_{2}}$ , its degree is denoted by $\deg(P)$ , i.e.,

\deg(P):=\max\{\deg(P_{ij}(x)),~{}1\leq i\leq\ell_{1},1\leq j\leq\ell_{2}\}.

For a real number $t,\lceil t\rceil$ denotes the smallest integer greater than or equal to $t$ . For a matrix $A$ , $A^{T}$ denotes its transpose and $\|A\|_{2}$ denotes the spectral norm of $A$ . A symmetric matrix $X\succeq 0$ (resp., $X\succ 0$ ) if $X$ is positive semidefinite (resp., positive definite). For a smooth function $p$ in $x$ , its gradient is denoted by $\nabla p$ .

2.2 Some basics in real algebraic geometry

In this subsection, we review some basics in real algebraic geometry. We refer to [7, 16, 27, 28, 33, 38, 48, 50] for more details.

A polynomial matrix $S$ is said to be a sum of squares (SOS) if $S=P^{T}P$ for some polynomial matrix $P(x)$ . The set of all $\ell$ -by- $\ell$ SOS polynomial matrices in $x$ is denoted as $\Sigma[x]^{\ell}$ . For a degree $k$ , denote the truncation

\Sigma[x]_{k}^{\ell}\,\coloneqq\,\left\{\sum_{i=1}^{t}P_{i}^{T}P_{i}\mid t\in\mathbb{N},~{}P_{i}\in\mathbb{R}[x]^{\ell\times\ell},~{}2\deg(P_{i})\leq k\right\}.

For an $m$ -by- $m$ symmetric polynomial matrix $G$ , the quadratic module of $\ell$ -by- $\ell$ polynomial matrices generated by $G(x)$ in $\mathbb{R}[x]^{\ell\times\ell}$ is

\mbox{QM}[G]^{\ell}=\left\{S+\sum_{i=1}^{t}P_{i}^{T}GP_{i}\mid t\in\mathbb{N},~{}S\in\Sigma[x]^{\ell},~{}P_{i}\in\mathbb{R}[x]^{m\times\ell}\right\}.

The $k$ th degree truncation of $\mbox{QM}[G]^{\ell}$ is

(2.1)

\mbox{QM}[G]_{k}^{\ell}=\left\{S+\sum_{i=1}^{t}P_{i}^{T}GP_{i}\mid t\in\mathbb{N},~{}S\in\Sigma[x]^{\ell}_{k},~{}P_{i}\in\mathbb{R}[x]_{\lceil k/2-\deg(G)/2\rceil}^{m\times\ell}\right\}.

Note that $\Sigma[x]^{\ell}\subseteq\mbox{QM}[G]^{\ell}$ . For the case $\ell=1$ , we simply denote

\Sigma[x]_{k}:=\Sigma[x]_{k}^{1},~{}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}~{}\mbox{QM}[G]:=\mbox{QM}[G]^{1}},~{}\mbox{QM}[G]_{k}:=\mbox{QM}[G]_{k}^{1}.

The quadratic module $\mathrm{QM}[G]^{\ell}$ is said to be Archimedean if there exists $r>0$ such that $\left(r-\|x\|_{2}^{2}\right)\cdot I_{\ell}\in\mathrm{QM}[G]^{\ell}.$ The polynomial matrix $G$ determines the semialgebraic set

K:=\left\{x\in\mathbb{R}^{n}\mid G(x)\succeq 0\right\}.

If $\mbox{QM}[G]^{\ell}$ is Archimedean, then the set $K$ must be compact. However, when $K$ is compact, it is not necessarily that $\mbox{QM}[G]^{\ell}$ is Archimedean (see [26]). The following is known as the matrix-version of Putinar’s Positivstellensätz.

Theorem 2.1 ([28, 48]).

Suppose that $G$ is an $m$ -by- $m$ symmetric polynomial matrix and $\mbox{QM}[G]^{\ell}$ is Archimedean. If the $\ell$ -by- $\ell$ symmetric polynomial matrix $F\succ 0$ on $K$ , then we have $F\in\mbox{QM}[G]^{\ell}$ .

2.3 Some technical propositions

In this subsection, we present several useful propositions that are used in our proofs. The following is the classical Łojasiewicz inequality.

Corollary 2.2 ([5, 34]).

Let $A$ be a closed and bounded semialgebraic set, and let $f$ and $g$ two continuous semialgebraic functions from $A$ to $\mathbb{R}$ such that $f^{-1}(0)\subseteq g^{-1}(0)$ . Then there exist two positive constants $\eta$ , $\kappa$ such that:

|g(x)|^{\eta}\leq\kappa|f(x)|,~{}\forall x\in A.

The smallest constant $\eta$ is called the Łojasiewicz exponent and $\kappa$ is the corresponding Łojasiewicz constant.

The Markov inequality below can be used to estimate gradients of polynomials.

Theorem 2.3 ([3, 30]).

Let $\bar{\Delta}$ be the scaled simplex as in (1.7) and let $p\in\mathbb{R}[x]$ be a polynomial with degree $\leq d$ . Then:

\max_{x\in\bar{\Delta}}\|\nabla p(x)\|_{2}\leq\frac{2d(2d-1)}{\sqrt{n}+1}\max_{x\in\bar{\Delta}}|p(x)|.

The following theorem is a slight variation of [14, Theorem 3.3], which gives explicit Łojasiewicz exponents for basic closed semialgebraic sets.

Theorem 2.4 ([14]).

Suppose that $g_{1},\dots,g_{s},h_{1},\dots,h_{l}\in\mathbb{R}[x]_{d}$ and let

S:=\{x\in\mathbb{R}^{n}\mid h_{1}(x)=\cdots=h_{l}(x)=0,g_{1}(x)\geq 0,\ldots,g_{s}(x)\geq 0\}\neq\emptyset.

Then for any compact set $K\subset\mathbb{R}^{n}$ , there is a constant $c>0$ such that for all $x\in K$ ,

d(x,S)^{\mathcal{R}(n+l+s-1,d+1)}\leq-c\cdot\min\{g_{1}(x),\dots,g_{s}(x),h_{1}(x),-h_{1}(x),\dots,h_{l}(x),-h_{l}(x),0\},

where $d(x,S)$ is the Euclidean distance to the set $S$ and $\mathcal{R}(n,d)=d\cdot(3d-3)^{n-1}$ .

3 Degree bounds for scalar polynomial inequalities

In this section, we consider the case where $G(x)$ is a diagonal matrix with diagonal entries $g_{1},\dots,g_{m}\in\mathbb{R}[x]$ . Then, the set $K$ as in (1.1) can be equivalently described as

(3.1)

K=\{x\in\mathbb{R}^{n}\mid g_{1}(x)\geq 0,\dots,\dots,g_{m}(x)\geq 0\}.

If the symmetric polynomial matrix $F(x)\succ 0$ on $K$ , we prove a polynomial bound on the degrees of terms appearing in matrix Putinar’s Positivstellensätz. This improves the exponential bound shown by Helton and Nie [15]. The proof essentially generalizes the idea and strategies used in [2, 3] to the matrix case. We refer to Step 1 in the section ‘Outlines of proofs’ for an overview of the proof.

Let $\Delta^{n}$ be the $n$ -dimensional standard simplex, i.e.,

\Delta^{n}=\{x\in\mathbb{R}^{n}\mid x_{1}+\dots+x_{n}=1,x_{1}\geq 0,\dots,x_{n}\geq 0\}.

Denote the scaled simplex by

\bar{\Delta}=\left\{x\in\mathbb{R}^{n}\mid\sqrt{n}-x_{1}-\cdots-x_{n}\geq 0,1+x_{1}\geq 0,\ldots,1+x_{n}\geq 0\right\}.

For a degree $t$ , let $\{B_{\alpha}^{(t)}(x):\alpha\in\mathbb{N}^{n}_{t}\}$ be the Bernstein basis of degree $t$ on $\bar{\Delta}$ , i.e.,

(3.2)

B_{\alpha}^{(t)}(x)=\frac{t!}{\alpha_{1}!\cdots\alpha_{n}!}(n+\sqrt{n})^{-t}\left(\sqrt{n}-x_{1}-\cdots-x_{n}\right)^{t-|\alpha|}\left(1+x_{1}\right)^{\alpha_{1}}\cdots\left(1+x_{n}\right)^{\alpha_{n}},

For a degree $t\geq d$ , the $\ell\times\ell$ symmetric polynomial matrix $F$ of degree $d$ can be expressed in the Bernstein basis $\{B_{\alpha}^{(t)}(x):\alpha\in\mathbb{N}^{n}_{t}\}$ as

F=\sum_{\alpha\in\mathbb{N}_{t}^{n}}F_{\alpha}^{(t)}B_{\alpha}^{(t)}(x),

where $F_{\alpha}^{(t)}$ are $\ell$ -by- $\ell$ symmetric matrices. The Bernstein norm of $F$ with respect to $\{B_{\alpha}^{(t)}(x):\alpha\in\mathbb{N}^{n}_{t}\}$ is defined as

\|F\|_{B,t}=\max\{\|F_{\alpha}^{(t)}\|_{2}:~{}\alpha\in\mathbb{N}^{n}_{t}\}.

For convenience, we denote $\|F\|_{B,d}$ simply as $\|F\|_{B}$ . Similarly, $F$ can also be expressed in the monomial basis $\{x^{\alpha}:\alpha\in\mathbb{N}^{n}_{d}\}$ as

F=\sum_{\alpha\in\mathbb{N}_{d}^{n}}F_{\alpha}\frac{d!}{\alpha_{1}!\cdots\alpha_{n}!}x^{\alpha}.

The spectral norm of $F$ is defined as $\|F\|_{2}=\max\{\|F_{\alpha}\|_{2}:~{}\alpha\in\mathbb{N}^{n}_{d}\}.$ For $f(x)\in\mathbb{R}[x]_{d_{1}}$ , $g(x)\in\mathbb{R}[x]_{d_{2}}$ and $\ell_{1}\geq\ell_{2}\geq d_{1}$ , the following is a basic property of the Bernstein norm (see [13], [3, Lemma 1.5]):

(3.3)

\max\limits_{s\in\bar{\Delta}}|f(s)|\leq\|f\|_{B,\ell_{1}}\leq\|f\|_{B,\ell_{2}},~{}~{}\|fg\|_{B,d_{1}+d_{2}}\leq\|f\|_{B,d_{1}}\|g\|_{B,d_{2}}.

Suppose that $p(x)$ is a homogeneous polynomial with $\deg(p)=d$ . Polya’s Positivstellensätz [40, 41] states that if $p(x)\geq p_{\min}>0$ on the standard simplex $\Delta^{n}$ , then the polynomial $(x_{1}+\cdots+x_{n})^{k}p(x)$ has only positive coefficients if $k>d(d-1)\frac{\|p\|}{2p_{\min}}-d.$ This result has been generalized to the matrix case by Scherer and Hol [48]. It was shown in [48, Theorem 3] that if $F(x)$ is an $\ell$ -by- $\ell$ homogeneous symmetric polynomial matrix with $\deg(F)=d$ and $F(x)\succeq F_{\min}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}I_{\ell}}\succ 0$ on $\triangle^{n}$ , then for $k>d(d-1)\frac{\|F\|_{2}}{2F_{\min}}-d,$ all coefficient matrices of $(x_{1}+\cdots+x_{n})^{k}F(x)$ in the monomial basis are positive definite.

In the following, we present a dehomogenized version of matrix Polya’s Positivstellensätz in terms of the Bernstein basis.

Lemma 3.1.

Suppose $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix with $\deg(F)=d$ . If $F(x)\succeq F_{\min}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}I_{\ell}}\succ 0$ on $\bar{\Delta}$ , then for

k>d(d-1)\frac{\|F\|_{B}}{2F_{\min}}-d,

all coefficient matrices of $F(x)$ in the Bernstein basis $\{B_{\alpha}^{(k+d)}(x):\alpha\in\mathbb{N}^{n}_{k+d}\}$ are positive definite.

Proof 3.2.

Suppose that $F$ can be expressed in the Bernstein basis $\{B_{\alpha}^{(d)}(x):\alpha\in\mathbb{N}^{n}_{d}\}$ as

F=\sum_{\alpha\in\mathbb{N}^{n}_{d}}F_{\alpha}^{(d)}B_{\alpha}^{(d)}(x),

where $F_{\alpha}^{(d)}$ are $\ell$ -by- $\ell$ symmetric matrices. Denote

\widehat{F}(y_{1},\dots,y_{n+1})=\sum_{\alpha\in\mathbb{N}^{n}_{d}}F_{\alpha}^{(d)}\frac{d!}{\alpha_{1}!\cdots\alpha_{n}!}y^{\alpha}y_{n+1}^{d-|\alpha|}.

For each $(y_{1},\dots,y_{n+1})\in\Delta^{n+1}$ , let

x_{i}=(n+\sqrt{n})y_{i}-1~{}(i=1,\dots,n).

Then we know that

\begin{array}[]{ll}\sqrt{n}-\sum\limits_{i=1}^{n}x_{i}=\sqrt{n}-\sum\limits_{i=1}^{n}((n+\sqrt{n})y_{i}-1)&=\sqrt{n}+n-(n+\sqrt{n})\sum\limits_{i=1}^{n}y_{i}\\ &=(\sqrt{n}+n)(1-\sum\limits_{i=1}^{n}y_{i})\\ &\geq 0,\\ \end{array}

which implies that $x=(x_{1},\dots,x_{n})\in\bar{\Delta}$ . By computations, we have that for $(y_{1},\dots,y_{n+1})\in\Delta^{n+1}$ , the following holds

\widehat{F}(y_{1},\dots,y_{n+1})=\sum_{\alpha\in\mathbb{N}^{n}_{d}}F_{\alpha}^{(d)}B_{\alpha}^{(d)}(x)=F(x)\succeq F_{\min}\cdot I_{\ell}.

Hence, $\widehat{F}\succeq F_{\min}\cdot I_{\ell}$ on $\Delta^{n+1}$ . It follows from [48, Theorem 3] that for $k>d(d-1)\frac{\|\widehat{F}\|_{2}}{2F_{\min}}-d$ , all coefficient matrices of $(y_{1}+\cdots+y_{n+1})^{k}\widehat{F}(y_{1},\dots,y_{n+1})$ in the monomial basis are positive definite, i.e., there exist $P_{\alpha}\succ 0$ such that

(y_{1}+\cdots+y_{n+1})^{k}\widehat{F}(y_{1},\dots,y_{n+1})=\sum_{\alpha\in\mathbb{N}_{k+d}^{n}}P_{\alpha}\frac{(k+d)!}{\alpha_{1}!\cdots\alpha_{n}!}y_{1}^{\alpha_{1}}\cdots y_{n}^{\alpha_{n}}(y_{n+1})^{k+d-|\alpha|}.

By substituting

y_{i}=\frac{x_{i}+1}{n+\sqrt{n}}~{}(i=1,\dots,n),\,y_{n+1}=1-\frac{1}{n+\sqrt{n}}\left(\sum\limits_{i=1}^{n}x_{i}+n\right)

into the above identity, we obtain

F(x_{1},\dots,x_{n})=\sum_{\alpha\in\mathbb{N}_{k+d}^{n}}P_{\alpha}B_{\alpha}^{(k+d)}(x).

Since $\|\widehat{F}\|_{2}=\|F\|_{B}$ , the conclusion follows.

Lemma 3.3.

Suppose $P(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix with $\deg(P)=d_{P}$ . Let $\xi\in\mathbb{R}^{\ell}$ with $\|\xi\|_{2}=1$ , and denote

P^{(\xi)}(x):=\xi^{T}P(x)\xi.

Then, we have that $\|P^{(\xi)}\|_{B,d_{P}}\leq\|P\|_{B}$ . Furthermore, there exists $\xi_{0}\in\mathbb{R}^{\ell}$ with $\|\xi_{0}\|_{2}=1$ such that $\|P^{(\xi_{0})}\|_{B,d_{P}}=\|P\|_{B}$ .

Proof 3.4.

Suppose that $P$ can be expressed in the Bernstein basis $\{B_{\alpha}^{(d_{P})}(x):\alpha\in\mathbb{N}^{n}_{d_{P}}\}$ as

P=\sum_{\alpha\in\mathbb{N}^{n}_{d_{P}}}P_{\alpha}^{(d_{P})}B_{\alpha}^{(d_{P})}(x),

where $P_{\alpha}^{(d_{P})}$ are $\ell$ -by- $\ell$ symmetric matrices. Note that

\begin{array}[]{ll}\|P^{(\xi)}\|_{B,d_{P}}=\|\xi^{T}P(x)\xi\|_{B,d_{P}}&=\|\sum\limits_{\alpha\in\mathbb{N}^{n}_{d_{P}}}\xi^{T}P_{\alpha}^{(d_{P})}\xi B_{\alpha}^{(d_{P})}(x)\|_{B,d_{P}}\\ &=\max\{|\xi^{T}P_{\alpha}^{(d_{P})}\xi|:~{}\alpha\in\mathbb{N}^{n}_{d_{P}}\}\\ &\leq\max\{\|P_{\alpha}^{(d_{P})}\|_{2}:~{}\alpha\in\mathbb{N}^{n}_{d_{P}}\}=\|P\|_{B}.\end{array}

Thus, we have $\|P^{(\xi)}\|_{B,d_{P}}\leq\|P\|_{B}.$ Since there exists $\xi_{0}\in\mathbb{R}^{\ell}$ with $\|\xi_{0}\|_{2}=1$ such that

\|P\|_{B}=\max\{|\xi_{0}^{T}P_{\alpha}^{(d_{P})}\xi_{0}|:~{}\alpha\in\mathbb{N}^{n}_{d_{P}}\},

then we have that

\|P^{(\xi_{0})}\|_{B,d_{P}}=\max\{|\xi_{0}^{T}P_{\alpha}^{(d_{P})}\xi_{0}|:~{}\alpha\in\mathbb{N}^{n}_{d_{P}}\}=\|P\|_{B}.

Denote

(3.4)

\mathcal{G}(x)=-\min\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{g_{1}(x)}{\left\|g_{1}\right\|_{B}}},\ldots,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{g_{m}(x)}{\left\|g_{m}\right\|_{B}}},0\right).

For $x\in\mathbb{R}^{n}$ , let $d(x,K)$ denote the Euclidean distance to the set $K$ , i.e.,

d(x,K)=\min\{\|x-y\|_{2},\,\,y\in K\}.

If $\mathcal{G}(x)=0$ , then we have $x\in K$ and $d(x,K)=0$ . The distance function $d(x,K)$ is a continuous semialgebraic function (see [5, Proposition 2.2.8], [14, Proposition 1.8]). By Corollary 2.2, there exist positive constants $\eta$ , $\kappa$ such that the following Łojasiewicz inequality holds:

(3.5)

d(x,K)^{\eta}\leq\kappa\mathcal{G}(x),\quad\forall x\in\bar{\Delta}.

Note that

d_{G}=\max\{\deg(g_{1}),\dots,\deg(g_{m})\}.

In the following, we prove a polynomial bound on the degrees of terms appearing in matrix Putinar’s Positivstellensätz when $K$ is given by finitely many scalar polynomial inequalities, which improves the exponential bound established in [15]. Recall that the quadratic module of scalar polynomials generated by $G(x)$ in $\mathbb{R}[x]$ is denoted by $\mbox{QM}[G]$ (see Section 2.2).

Theorem 3.5.

Let $G(x)$ be a diagonal matrix with diagonal entries $g_{1},\dots,g_{m}\in\mathbb{R}[x]$ and let $K$ be as in (3.1). Suppose that $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix with $\deg(F)=d$ , and $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mbox{QM}[G]^{\ell}$ . If $F(x)\succeq F_{\min}\cdot I_{\ell}\succ 0$ on $K$ , then $F\in\mbox{QM}[G]_{k}^{\ell}$ for

(3.6)

k\geq C\cdot{8}^{7\eta}m^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14\eta}\left(\frac{\|F\|_{B}}{F_{\min}}\right)^{7\eta+3}.

In the above, $\kappa$ , $\eta$ are respectively the Łojasiewicz constant and exponent in (3.5) and $C>0$ is a constant independent of $F$ , $g_{1},\dots,g_{m}$ . Furthermore, the Łojasiewicz exponent can be estimated as $\eta\leq(d_{G}+1)(3d_{G})^{n+m-2}$ .

Remark. At a feasible point $x\in K$ , the Mangasarian–Fromovitz constraint qualification (MFCQ) holds if there exists a direction $v\in\mathbb{R}^{n}$ such that $\nabla g_{j}(x)^{T}v>0$ for all active inequality constraints $g_{j}(x)=0$ . The linear independence constraint qualification (LICQ) holds at $x$ if the set of gradient vectors $\nabla g_{j}(x)$ of all active constraints is linearly independent. It was shown in [45] that if the MFCQ holds at every $x\in K$ , then the Łojasiewicz exponent, as in (3.5), is equal to 1. Since the MFCQ is weaker than the LICQ, we know that if the LICQ holds at every $x\in K$ , the Łojasiewicz exponent $\eta=1$ (see also [2, 3])¹¹1The author would like to thank the referee for pointing out this fact.. Then, under the assumptions of Theorem 3.5, we have that ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}F}\in\mbox{QM}[G]_{k}^{\ell}$ if

(3.7)

k\geq C\cdot m^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14}\left(\frac{\|F\|_{B}}{F_{\min}}\right)^{10}.

Proof 3.6.

Without loss of generality, we assume that $\left\|g_{i}\right\|_{B}=1$ for $i=1,\dots,m$ . Otherwise, we can scale $g_{i}$ by $1/\|g_{i}\|_{B}$ . We remark that scaling $g_{i}$ does not change $\kappa$ , since we normalize $g_{i}$ in $\mathcal{G}$ and $(g_{i}(x)/\|g_{i}\|_{B})/(\|g_{i}(x)/\|g_{i}\|_{B}\|_{B})=g_{i}(x)/\|g_{i}\|_{B}$ . Thus, the bound remains unchanged. Let

\delta=\frac{1}{{8}^{\eta}\kappa d^{2\eta}}\left(\frac{F_{\min}}{\|F\|_{B}}\right)^{\eta},~{}v=\frac{\delta F_{\min}}{20m\|F\|_{B}},~{}\lambda=5\|F\|_{B}/\delta.

For the above $\delta$ , $v$ , it follows from [3, Proposition 3.2] that there exists $h_{i}\in\mathbb{R}[x]$ such that for $x\in\bar{\Delta}$ , we have that

(i)

if $g_{i}(x)\geq 0,\left|h_{i}(x)\right|\leq 2v$ .
(ii)

if $g_{i}(x)\leq-\delta,\left|h_{i}(x)\right|\geq\frac{1}{2}$ .
(iii)

$\left\|h_{i}\right\|_{B}\leq 1$ .
(iv)

$h_{i}\in\Sigma[x]_{k}$ with $k\leq 10^{5}nd_{G}^{2}\delta^{-2}v^{-1}$ .

Let

P=F-\lambda\sum_{i=1}^{m}h_{i}g_{i}I_{\ell}.

In the following, we show that $P\succeq\frac{1}{4}F_{\min}\cdot I_{\ell}$ on $\bar{\Delta}$ . Equivalently, for a fixed $x\in\bar{\Delta}$ , we prove that for each $\xi\in\mathbb{R}^{\ell}$ with $\|\xi\|_{2}=1$ , the following holds:

(3.8)

F^{(\xi)}(x)-\lambda\sum_{i=1}^{m}h_{i}(x)g_{i}(x)=\xi^{T}(F(x)-\lambda\sum_{i=1}^{m}h_{i}(x)g_{i}(x)I_{\ell})\xi\geq\frac{1}{4}F_{\min}.

In the above, $F^{(\xi)}(x):=\xi^{T}F(x)\xi.$

Case I. Suppose that $F^{(\xi)}(x)\leq\frac{3F_{\min}}{4}$ . Then, we know that $x\notin K$ . Let $x^{*}\in K$ be a vector such that $\|x-x^{*}\|_{2}=d(x,K)$ . Since $F(x^{*})\succeq F_{\min}\cdot I_{\ell}$ , we have that

\begin{array}[]{ll}\frac{F_{\min}}{4}\leq F^{(\xi)}(x^{*})-F^{(\xi)}(x)&\leq\max\limits_{s\in\bar{\Delta}}\|\nabla F^{(\xi)}(s)\|_{2}\|x-x^{*}\|_{2}\\ &\leq\frac{2d(2d-1)}{\sqrt{n}+1}\|x-x^{*}\|_{2}\max\limits_{s\in\bar{\Delta}}|F^{(\xi)}(s)|,\\ \end{array}

where the last inequality follows from Theorem 2.3. Since $\max\limits_{s\in\bar{\Delta}}|F^{(\xi)}(s)|\leq\|F^{(\xi)}\|_{B,d}$ (see (3.3)), it holds that

(3.9)

F_{\min}\leq\max_{s\in\bar{\Delta}}|F^{(\xi)}(s)|\leq\|F^{(\xi)}\|_{B,d}\leq\|F\|_{B},

where the last inequality is due to Lemma 3.3. Then, we know that

\frac{F_{\min}}{4}\leq\frac{2d(2d-1)}{\sqrt{n}+1}\|F^{(\xi)}\|_{B,d}\|x-x^{*}\|_{2}\leq 2d^{2}\|F\|_{B}\|x-x^{*}\|_{2}.

By the Łojasiewicz inequality (3.5), we have that

\mathcal{G}(x)\geq\kappa^{-1}d(x,K)^{\eta}\geq\kappa^{-1}\|x-x^{*}\|_{2}^{\eta}\geq\frac{1}{{8}^{\eta}\kappa d^{2\eta}}(\frac{F_{\min}}{\|F\|_{B}})^{\eta}=\delta.

From the definition of the function $\mathcal{G}(x)$ as in (3.4), there exists $i_{0}\in\{1,\dots,m\}$ such that $g_{i_{0}}(x)\leq-\delta$ . Since $h_{i_{0}}(x)$ is an SOS (see item (iv)) and $g_{i_{0}}(x)\leq-\delta$ , we have $h_{i_{0}}(x)\geq\frac{1}{2}$ by item (ii). Note that

-h_{i_{0}}(x)g_{i_{0}}(x)\geq\frac{1}{2}\delta,~{}-h_{i}(x)g_{i}(x)\geq-2v\cdot\max\limits_{s\in\bar{\Delta}}|g_{i}(s)|\geq-2v\cdot\|g_{i}\|_{B}=-2v~{}(i=1,\dots,m).

In the above, we use the inequality (3.3). Then, we have that

	$\displaystyle F^{(\xi)}(x)-\lambda\sum_{i=1}^{m}h_{i}(x)g_{i}(x)$	$\displaystyle\geq F^{(\xi)}(x)+\lambda\cdot\frac{1}{2}\delta-2\lambda v(m-1)$
		$\displaystyle\geq F^{(\xi)}(x)+\lambda\frac{\delta}{4}+\lambda\left(\frac{\delta}{4}-2v(m-1)\right).$

One can see from the relation (3.9) that $F^{(\xi)}(x)\geq-\|F^{(\xi)}\|_{B,d}$ and $F_{\min}\leq\|F\|_{B}$ , which implies that

\frac{\delta}{4}-2v(m-1)\geq\frac{\delta}{4}-2vm\geq\frac{\delta}{4}-\frac{\delta F_{\min}}{10\|F\|_{B}}\geq\frac{\delta}{4}-\frac{\delta}{10}>0,

\lambda\frac{\delta}{4}=\frac{5}{4}\|F\|_{B}\geq\frac{5}{4}\|F^{(\xi)}\|_{B,d}.

Then, it follows that

	$\displaystyle F^{(\xi)}(x)-\lambda\sum_{i=1}^{m}h_{i}(x)g_{i}(x)$	$\displaystyle\geq F^{(\xi)}(x)+\lambda\frac{\delta}{4}+\lambda\left(\frac{\delta}{4}-2v(m-1)\right)$
		$\displaystyle\geq-\\|F^{(\xi)}\\|_{B,d}+\frac{5}{4}\\|F^{(\xi)}\\|_{B,d}$
		$\displaystyle\geq\frac{1}{4}\\|F^{(\xi)}\\|_{B,d}\geq\frac{1}{4}\max_{s\in\bar{\Delta}}\|F^{(\xi)}(s)\|$
		$\displaystyle\geq\frac{1}{4}F_{\min},$

where the second inequality follows from the inequality (3.3).

Case II. Suppose that $F^{(\xi)}(x)\geq\frac{3F_{\min}}{4}$ . Note that $-h_{i}(x)g_{i}(x)\geq-2v\cdot\|g_{i}\|_{B}=-2v$ for $i=1,\dots,m$ , and

2m\lambda v=2m\cdot\frac{\delta F_{\min}}{20m\|F\|_{B}}\cdot 5\|F\|_{B}/\delta=\frac{1}{2}F_{\min}.

Then, we have that

F^{(\xi)}(x)-\lambda\sum_{i=1}^{m}h_{i}(x)g_{i}(x)\geq\frac{3}{4}F_{\min}-2m\lambda v\geq\frac{1}{4}F_{\min}.

This concludes the proof of (3.8).

Since $\xi\in\mathbb{R}^{n}$ with $\|\xi\|_{2}=1$ is arbitrary, we have $P(x)\succeq\frac{1}{4}F_{\min}\cdot I_{\ell}$ on $\bar{\Delta}$ . Note that $x$ can be any fixed point in $\bar{\Delta}$ , we know that $P(x)\succeq\frac{1}{4}F_{\min}\cdot I_{\ell}$ for all $x\in\bar{\Delta}$ . Since $\deg(h_{i})\leq 10^{5}nd_{G}^{2}\delta^{-2}v^{-1}$ for $i=1,\dots,m$ , we have that

\begin{array}[]{ll}\deg(h_{i}g_{i})\leq 10^{5}nd_{G}^{3}\delta^{-2}v^{-1}&\leq 2\cdot 10^{6}mnd_{G}^{3}\delta^{-3}\frac{\|F\|_{B}}{F_{\min}}\\ &\leq 2\cdot 10^{6}\cdot{8}^{3\eta}mnd_{G}^{3}\kappa^{3}d^{6\eta}(\frac{\|F\|_{B}}{F_{\min}})^{3\eta+1}.\\ \end{array}

By Lemma 3.3, there exists $\xi_{0}\in\mathbb{R}^{n}$ with $\|\xi_{0}\|_{2}=1$ such that $\|P\|_{B}=\|\xi_{0}^{T}P\xi_{0}\|_{B,\deg(P)}$ . Then, we obtain that

\begin{array}[]{ll}\|P\|_{B}=\|\xi_{0}^{T}P\xi_{0}\|_{B,\deg(P)}&=\|F^{(\xi_{0})}-\lambda\sum_{i=1}^{m}h_{i}g_{i}\|_{B,\deg(P)}\\ &\leq\|F^{(\xi_{0})}\|_{B,\deg(P)}+\lambda\sum_{i=1}^{m}\|h_{i}g_{i}\|_{B,\deg(P)}\\ &\leq\|F^{(\xi_{0})}\|_{B,\deg(F)}+\lambda\sum_{i=1}^{m}\|h_{i}\|_{B,\deg(P)-\deg(g_{i})}\|g_{i}\|_{B,\deg(g_{i})}\\ &\leq\|F\|_{B}+\lambda m\leq(1+5\delta^{-1}m)\|F\|_{B}\\ &\leq{8}^{\eta+1}m\kappa d^{2\eta}(\frac{\|F\|_{B}}{F_{\min}})^{\eta}\|F\|_{B},\\ \end{array}

where the second inequality is due to the inequality (3.3). Note that

\begin{array}[]{ll}\deg(P)=\deg(F-\lambda\sum_{i=1}^{m}h_{i}g_{i}I_{\ell})&=\max\{\deg(F),\deg(h_{i}g_{i})~{}(i=1,\dots,m)\}\\ &\leq\max\{d,2\cdot 10^{6}\cdot{8}^{3\eta}mnd_{G}^{3}\kappa^{3}d^{6\eta}(\frac{\|F\|_{B}}{F_{\min}})^{3\eta+1}\}\\ &=2\cdot 10^{6}\cdot{8}^{3\eta}mnd_{G}^{3}\kappa^{3}d^{6\eta}(\frac{\|F\|_{B}}{F_{\min}})^{3\eta+1}.\end{array}

It follows from Lemma 3.1 that all coefficient matrices of $P(x)$ in the Bernstein basis $\{B_{\alpha}^{(k)}(x):\alpha\in\mathbb{N}_{k}^{n}\}$ are positive definite, for

\begin{array}[]{ll}k&\geq(16\cdot 10^{6})^{2}\cdot{8}^{7\eta}m^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14\eta}(\frac{\|F\|_{B}}{F_{\min}})^{7\eta+3}\\ &>\left(2\cdot 10^{6}\cdot{8}^{3\eta}mnd_{G}^{3}\kappa^{3}d^{6\eta}(\frac{\|F\|_{B}}{F_{\min}})^{3\eta+1}\right)^{2}{8}^{\eta+2}m\kappa d^{2\eta}(\frac{\|F\|_{B}}{F_{\min}})^{\eta}\frac{\|F\|_{B}}{F_{\min}}\\ &\geq\deg(P)^{2}\frac{\|P\|_{B}}{\frac{1}{2}F_{\min}},\\ \end{array}

i.e., there exist matrices $P_{\alpha}^{(k)}\succ 0$ such that

F-\lambda\sum_{i=1}^{m}h_{i}g_{i}I_{\ell}=\sum_{\alpha\in\mathbb{N}_{k}^{n}}P_{\alpha}^{(k)}B_{\alpha}^{k}(x).

In the following, we show that $\sqrt{n}-x_{1}-\cdots-x_{n}\in\mbox{QM}[1-\|x\|_{2}^{2}]_{2}$ . Consider the optimization

(3.10)

\left\{\begin{array}[]{rl}\min&\sqrt{n}-x_{1}-\cdots-x_{n}\\ \mathit{s.t.}&1-\|x\|_{2}^{2}\geq 0.\\ \end{array}\right.

One can verify that the optimal value of (3.10) is 0. Since $\sqrt{n}-x_{1}-\cdots-x_{n}$ and $-(1-\|x\|^{2})$ are SOS convex and the feasible set has an interior point, it follows from [32, Theorem 3.3] that the lowest order SOS relaxation of (3.10) is exact and the optimal values of all SOS relaxations are achievable. Consequently, we have that $\sqrt{n}-x_{1}-\cdots-x_{n}\in\mbox{QM}[1-\|x\|_{2}^{2}]_{2}$ . Similarly, we know that $1+x_{1},\cdots,1+x_{n}\in\mbox{QM}[1-\|x\|_{2}^{2}]_{2}$ . Hence, we have

\left(\sqrt{n}-x_{1}-\cdots-x_{n}\right)^{k-|\alpha|}\left(1+x_{1}\right)^{\alpha_{1}}\cdots\left(1+x_{n}\right)^{\alpha_{n}}\in\mbox{QM}[1-\|x\|_{2}^{2}]_{2(k-|\alpha|)+2\alpha_{1}+\dots+2\alpha_{n}}=\mbox{QM}[1-\|x\|_{2}^{2}]_{2k}.

Then, from the definition of $B_{\alpha}^{k}(x)$ , we have $B_{\alpha}^{k}(x)\in\mbox{QM}[1-\|x\|_{2}^{2}]_{2k}$ . Since $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mbox{QM}[G]_{k_{0}}^{\ell}$ for some $k_{0}>0$ , it follows that $1-\|x\|_{2}^{2}\in\mbox{QM}[G]_{k_{0}}$ , and thus $B_{\alpha}^{k}(x)\in\mbox{QM}[1-\|x\|_{2}^{2}]_{2k+k_{0}}$ . Then, the conclusion holds for sufficiently large $C$ . Note that

K=\left\{x\in\mathbb{R}^{n}\mid\frac{g_{1}(x)}{\left\|g_{1}\right\|_{B}}\geq 0,\dots,\frac{g_{m}(x)}{\left\|g_{m}\right\|_{B}}\geq 0\right\}.

It follows from Theorem 2.4 that $\eta\leq(d_{G}+1)(3d_{G})^{n+m-2}$ .

4 A scalar representation for polymomial matrix inequalities

In this section, we provide exact estimates on the quantity and degree bounds for polynomials $d_{1},\dots,d_{t}$ with $d_{1},\dots,d_{t}\in\mbox{QM}[G]$ , such that the polynomial matrix inequality $G(x)\succeq 0$ can be equivalently described by the scalar polynomial inequalities $d_{1}\geq 0$ , $\dots$ , $d_{t}\geq 0$ . This serves as a quantitative version of the following proposition due to Schmüdgen [50].

Proposition 1 (Proposition 9, [50]).

Let $G(x)$ be an $m$ -by- $m$ symmetric polynomial matrix and $G(x)\neq 0$ . Then there exist $m$ -by- $m$ diagonal polynomial matrices $D_{r}$ , $m$ -by- $m$ symmetric polynomial matrices $X_{\pm r}$ and polynomials $z_{r}\in$ $\Sigma[x],r=1,\ldots,t$ , such that:

(i)

$X_{+r}X_{-r}=X_{-r}X_{+r}=z_{r}I,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}D_{r}}=X_{-r}GX_{-r}^{T},z_{r}^{2}G=X_{+r}D_{r}X_{+r}^{T}$ ,
(ii)

For $x\in\mathbb{R}^{n}$ , $G(x)\succeq 0$ if and only if $D_{r}(x)\succeq 0$ for all $r=1,\ldots,t$ .

Let $K=\{x\in\mathbb{R}^{n}\mid G(x)\succeq 0\}.$ A direct corollary of Proposition 1 is that there exist finitely many polynomials in $\mbox{QM}[G]$ such that $K$ can be equivalently described by these polynomials. We also refer to [7, Proposition 5] for a generalization of Proposition 1, where the author considers the case that $K$ can be described by possibly infinitely many polynomial matrix inequalities. Denote

\theta(m)=\sum\limits_{i=1}^{m}\left(\prod_{k=m+1-i}^{m}\frac{k(k+1)}{2}\right).

Recall that $d_{G}=\max\{\deg(G_{ij}),~{}1\leq i,j\leq m\}.$ In the following, we provide a quantitative version of Proposition 1.

Theorem 4.1.

Suppose $G(x)$ is an $m$ -by- $m$ symmetric polynomial matrix with $m\geq 2$ . Then there exist $d_{1},d_{2},\dots,d_{\theta(m)}\in QM[G]_{3^{m-1}d_{G}}$ such that

K=\{x\in\mathbb{R}^{n}\mid d_{1}(x)\geq 0,\dots,d_{\theta(m)}(x)\geq 0\}.

Proof 4.2.

We prove the result by applying induction on the matrix size $m$ . Suppose that $m=2$ and $G(x)=[G_{ij}(x)]_{i,j=1,2}$ . In the following, we show that the inequality $G(x)=[G_{ij}(x)]_{i,j=1,2}\succeq 0$ can be equivalently described as

G_{11}\geq 0,~{}G_{22}\geq 0,~{}G_{11}(G_{11}G_{22}-G_{12}^{2})\geq 0,

G_{11}+2G_{12}+G_{22}\geq 0,~{}G_{22}(G_{11}G_{22}-G_{12}^{2})\geq 0,

(G_{11}+2G_{12}+G_{22})((G_{11}+2G_{12}+G_{22})G_{22}-(G_{12}+G_{22})^{2})\geq 0.

If $G(x)\succeq 0$ , we know that $G_{11}(x)\geq 0$ , $G_{22}(x)\geq 0$ , $G_{11}(x)\cdot G_{22}(x)-G_{12}(x)^{2}\geq 0$ , which imply the above inequalities. Suppose $x\in\mathbb{R}^{n}$ satisfies these inequalities. If $G_{11}(x)\neq 0$ ( $G_{22}(x)\neq 0$ , respectively), it follows from the inequality $G_{11}(x)\cdot(G_{11}(x)\cdot G_{22}(x)-G_{12}(x)^{2})\geq 0$ ( $G_{22}(x)\cdot(G_{11}(x)\cdot G_{22}(x)-G_{12}(x)^{2})\geq 0$ , respectively) that $G_{11}(x)\cdot G_{22}(x)-G_{12}(x)^{2}\geq 0$ . This implies that $G(x)\succeq 0$ . Otherwise, if $G_{11}(x)=G_{22}(x)=0$ , the last inequality reduces to $-2G_{12}(x)^{3}\geq 0$ and the inequality $G_{11}(x)+2G_{12}(x)+G_{22}(x)\geq 0$ reduces to $G_{12}(x)\geq 0$ . Then, we have that $G_{12}=0$ and $G(x)=0$ . Note that

\begin{bmatrix}G_{11}&0\\ -G_{12}&G_{11}\\ \end{bmatrix}\cdot G\cdot\begin{bmatrix}G_{11}&-G_{12}\\ 0&G_{11}\\ \end{bmatrix}=\begin{bmatrix}G_{11}^{3}&0\\ 0&G_{11}(G_{11}G_{22}-G_{12}^{2})\\ \end{bmatrix},

\begin{bmatrix}G_{22}&-G_{12}\\ 0&G_{22}\\ \end{bmatrix}\cdot G\cdot\begin{bmatrix}G_{22}&0\\ -G_{12}&G_{22}\\ \end{bmatrix}=\begin{bmatrix}G_{22}(G_{11}G_{22}-G_{12}^{2})&0\\ 0&G_{22}^{3}\\ \end{bmatrix},

A^{T}\cdot G\cdot A=\begin{bmatrix}(G_{11}+2G_{12}+G_{22})^{3}&0\\ 0&(G_{11}+2G_{12}+G_{22})((G_{11}+2G_{12}+G_{22})G_{22}-(G_{12}+G_{22})^{2})\\ \end{bmatrix},

where

A=\begin{bmatrix}1&0\\ 1&1\\ \end{bmatrix}\cdot\begin{bmatrix}G_{11}+2G_{12}+G_{22}&-G_{22}-G_{12}\\ 0&G_{11}+2G_{12}+G_{22}\\ \end{bmatrix}.

We know that all the above scalar inequalities involve polynomials that belong to $\mbox{QM}[G]_{3d_{G}}$ . Note that $\theta(2)=6$ . Hence, the result holds for $m=2$ .

Suppose the result holds for $m=k$ and consider the case that $m=k+1$ . In the following, we construct block diagonal polynomial matrices with a $1\times 1$ block and a $k\times k$ block, such that the inequality $G(x)\succeq 0$ can be equivalently described by the main diagonal blocks of these matrices. This reduction in matrix size allows us to apply induction. For $i\in\{1,\ldots,n\}$ , let $P_{i}$ denote the permutation matrix that swaps the first row and the $i$ -th row. For $1\leq i<j\leq k+1$ , denote the row operation matrix $Q^{(ij)}$ as

(Q^{(ij)})_{uv}=\left\{\begin{array}[]{ll}1,&\text{if~{}}(u,v)=(1,1),\dots,(k+1,k+1)\text{~{}or~{}if~{}}(u,v)=(i,j),\\ 0,&\text{otherwise}.\\ \end{array}\right.

Note that $Q^{(ij)}G(Q^{(ij)})^{T}$ is the matrix obtained by first adding the $j$ -th row of $G$ to the $i$ -th row and then adding the $j$ -th column to the $i$ -th column. Let

T_{ii}=P_{i}~{}(i=1,\dots,k+1),~{}T_{ij}=P_{i}\cdot Q^{(ij)}~{}(1\leq i<j\leq k+1).

Clearly, for $i<j$ , $T_{ij}GT_{ij}^{\mathrm{T}}$ is the matrix obtained by swapping the first row with the $i$ -th row of $Q^{(ij)}G(Q^{(ij)})^{T}$ and then swapping the first column with the $i$ -th column. Hence, we know that for $1\leq i\leq j\leq k+1$ , the matrices $T_{ij}$ are all invertible and it holds that

T_{ij}GT_{ij}^{\mathrm{T}}=\left[\begin{array}[]{cc}s_{ij}&(\beta^{(ij)})^{\mathrm{T}}\\ \beta^{(ij)}&H^{(ij)}\end{array}\right],

where $H^{(ij)}$ is a $k$ -by- $k$ symmetric polynomial matrix, $\beta^{(ij)}\in\mathbb{R}[x]^{k}$ and

s_{ii}=G_{ii}~{}(i=1,\dots,k+1),~{}s_{ij}=G_{ii}+G_{jj}+2G_{ij}~{}(1\leq i<j\leq k+1).

Denote the matrices

X_{+}^{(ij)}=\left[\begin{array}[]{cc}s_{ij}&~{}0\\ \beta^{(ij)}&~{}s_{ij}\cdot I_{k}\end{array}\right],~{}X_{-}^{(ij)}=\left[\begin{array}[]{cc}s_{ij}&~{}0\\ -\beta^{(ij)}&~{}s_{ij}\cdot I_{k}\end{array}\right].

By computations, we have that

(4.1)

X_{-}^{(ij)}X_{+}^{(ij)}=X_{+}^{(ij)}X_{-}^{(ij)}=s_{ij}^{2}\cdot I_{k+1},

(4.2)

(X_{-}^{(ij)}T_{ij})\cdot G\cdot(X_{-}^{(ij)}T_{ij})^{\mathrm{T}}=G^{(ij)},

(4.3)

s_{ij}^{4}T_{ij}GT_{ij}^{\mathrm{T}}=X_{+}^{(ij)}\cdot G^{(ij)}(X_{+}^{(ij)})^{\mathrm{T}},

where

G^{(ij)}=\left[\begin{array}[]{cc}s_{ij}^{3}&0\\ 0&s_{ij}\cdot\left(s_{ij}H^{(ij)}-\beta^{(ij)}(\beta^{(ij)})^{\mathrm{T}}\right)\end{array}\right].

Let

B^{(ij)}=s_{ij}\left(s_{ij}H^{(ij)}-\beta^{(ij)}(\beta^{(ij)})^{\mathrm{T}}\right)~{}(1\leq i\leq j\leq k+1).

Since $T_{ij}$ are scalar matrices, we have $\deg(s_{ij})\leq d_{G},~{}\deg(B^{(ij)})\leq 3d_{G}.$

In the following, we show that

(4.4)

K=\{x\in\mathbb{R}^{n}\mid s_{ij}(x)\geq 0,B^{(ij)}(x)\succeq 0,~{}1\leq i\leq j\leq k+1\}.

If $x\in K$ , i.e., $G(x)\succeq 0$ , it follows from (4.2) that $G^{(ij)}(x)\succeq 0$ , which implies that

(4.5)

s_{ij}(x)\geq 0,B^{(ij)}(x)\succeq 0,\quad\forall 1\leq i\leq j\leq k+1.

For the converse part, suppose $x\in\mathbb{R}^{n}$ satisfies (4.5). If $s_{ij}=0$ for all $1\leq i\leq j\leq k+1$ , then we have $G_{ij}(x)=0$ for all $1\leq i,j\leq k+1$ , leading to $G(x)=0$ . If there exist $1\leq i_{0}\leq j_{0}\leq k+1$ such that $s_{i_{0}j_{0}}(x)\neq 0$ , the relation (4.3) gives that

(4.6)

G(x)=s_{i_{0}j_{0}}^{-4}(x)T_{ij}^{-1}X_{+}^{(i_{0}j_{0})}\cdot G^{(i_{0}j_{0})}(X_{+}^{(i_{0}j_{0})})^{\mathrm{T}}(T_{i_{0}j_{0}}^{\mathrm{T}})^{-1}.

Since $G^{(i_{0}j_{0})}(x)\succeq 0$ , we conclude that $G(x)\succeq 0$ .

Note that each $B^{(ij)}$ is a $k$ -by- $k$ symmetric polynomial matrix with $\deg(B^{(ij)})\leq 3d_{G}$ for $1\leq i\leq j\leq k+1$ . By induction, there exist $d_{1}^{(ij)},\dots,d_{\theta(k)}^{(ij)}\in QM[G]_{3^{k}d_{G}}$ such that

\{x\in\mathbb{R}^{n}\mid B^{(ij)}(x)\succeq 0\}=\{x\in\mathbb{R}^{n}\mid d_{1}^{(ij)}(x)\geq 0,\dots,d_{\theta(k)}^{(ij)}(x)\geq 0\}.

Combining this with the relation (4.4), we have that

K=\{x\in\mathbb{R}^{n}\mid s_{ij}(x)\geq 0,d_{t}^{(ij)}(x)\succeq 0,~{}1\leq i\leq j\leq k+1,1\leq t\leq\theta(k)\}.

The total number of the above constraints is $\frac{1}{2}(k+1)(k+2)+\frac{1}{2}(k+1)(k+2)\theta(k),$ which equals to $\theta(k+1)$ . Hence, we have completed the proof.

Remark. There exist alternative ways to obtain finitely many scalar polynomial inequalities that describe $K$ . For instance, consider the characteristic polynomial $det[\lambda I_{m}-G(x)]$ of $G(x)$ . It can be expressed as

det[\lambda I_{m}-G(x)]=\lambda^{m}+\sum\limits_{i=1}^{m}(-1)^{i}g_{i}(x)\lambda^{m-i}.

Since $G(x)$ is symmetric, all eigenvalues are real, and $det[\lambda I_{m}-G(x)]$ has only real roots. We know that $G(x)\succeq 0$ if and only if $g_{i}(x)\geq 0$ for $i=1,\dots,m$ . Note that $g_{1}(x)=\operatorname{trace}(G(x))$ , which is always in $\mbox{QM}[G]$ . Hence, if the polynomials ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}g_{2}(x)},\dots,g_{m}(x)\in\mbox{QM}[G]$ , the quantity $\theta(m)$ and the degree $3^{m-1}d_{G}$ as stated in Theorem 4.1 can be improved to $m$ and $md_{G}$ , respectively. However, $g_{2}(x),\dots,g_{m}(x)$ typically do not belong to $\mbox{QM}[G]$ .

5 Degree bounds for matrix Positivstellensätze

This section is mainly to prove Theorems 1.1 and 1.2. As a byproduct, we can get a polynomial bound on the convergence rate of matrix SOS relaxations for solving polynomial matrix optimization, which resolves an open question raised by Dinh and Pham [10]. Let

(5.1)

K=\{x\in\mathbb{R}^{n}\mid G(x)\succeq 0\},

where $G(x)$ is an $m$ -by- $m$ symmetric polynomial matrix.

5.1 Proof of Theorem 1.1

For the polynomial matrix $G(x)$ , let $d_{1},\dots,d_{\theta(m)}$ be the polynomials as in Theorem 4.1. Note that we assume

K\subseteq\{x\in\mathbb{R}^{n}\mid 1-\|x\|_{2}^{2}\geq 0\}.

Denote

(5.2)

\mathcal{G}(x)=-\min\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{d_{1}(x)}{\left\|d_{1}\right\|_{B}}},\ldots,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{d_{\theta(m)}(x)}{\left\|d_{\theta(m)}\right\|_{B}}},0\right).

If $\mathcal{G}(x)=0$ , we have that $x\in K$ , i.e., $d(x,K)=0$ . By Corollary 2.2, there exist positive constants $\eta$ , $\kappa$ such that the following Łojasiewicz inequality holds:

(5.3)

d(x,K)^{\eta}\leq\kappa\mathcal{G}(x),~{}\forall x\in\bar{\Delta}.

In the following, we give the proof of Theorem 1.1.

Theorem 5.1.

Let $K$ be as in (5.1) with $m\geq 2$ . Suppose that $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix with $\deg(F)=d$ , and $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mbox{QM}[G]^{\ell}$ . If $F(x)\succeq F_{\min}\cdot I_{\ell}\succ 0$ on $K$ , then $F\in\mbox{QM}[G]_{k}^{\ell}$ for

(5.4)

k\geq C\cdot{8}^{7\eta}\cdot 3^{6(m-1)}\theta(m)^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14\eta}\left(\frac{\|F\|_{B}}{F_{\min}}\right)^{7\eta+3}.

In the above, $\kappa,\eta$ are respectively the Łojasiewicz constant and exponent in (5.3) and $C>0$ is a constant independent of $F$ , $G$ . Furthermore, the Łojasiewicz exponent can be estimated as

\eta\leq(3^{m-1}d_{G}+1)(3^{m}d_{G})^{n+\theta(m)-2}.

Proof 5.2.

By Theorem 4.1, we know that $d_{1},\dots,d_{\theta(m)}\in\mbox{QM}[G]_{3^{m-1}d_{G}}$ and

K=\{x\in\mathbb{R}^{n}\mid d_{1}(x)\geq 0,\dots,d_{\theta(m)}(x)\geq 0\}.

It follows from Theorem 3.5 that $F\in QM[D]_{k}^{\ell}$ , where $D$ is the diagonal matrix with diagonal entries $d_{1},\ldots,d_{\theta(m)}$ , $1-\|x\|_{2}^{2}$ , for

k\geq C\cdot{8}^{7\eta}\cdot 3^{6(m-1)}\theta(m)^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14\eta}\left(\frac{\|F\|_{B}}{F_{\min}}\right)^{7\eta+3}.

Equivalently, there exist SOS polynomial matrices $S_{i}\in\Sigma[x]^{\ell}$ ( $i=0,\dots,\theta(m)+1$ ) with $\deg(S_{0})\leq k$ , $\deg(d_{i}S_{i})\leq k~{}(i=1,\dots,\theta(m))$ , $\deg(S_{\theta(m)+1})\leq k-2$ , such that

F=S_{0}+d_{1}S_{1}+\cdots d_{\theta(m)}S_{\theta(m)}+(1-\|x\|_{2}^{2})S_{\theta(m)+1}.

Suppose that $S_{i}=\sum\limits_{j=1}^{s_{i}}v_{i,j}v_{i,j}^{T}$ for $v_{i,j}\in\mathbb{R}[x]_{\lceil k/2\rceil}^{\ell\times 1}$ and $d_{i}=\sigma_{i}+\sum\limits_{t=1}^{r_{i}}q_{i,t}^{T}Gq_{i,t}$ for some $\sigma_{i}\in\Sigma[x]_{3^{m-1}d_{G}}^{1}$ , $q_{i,t}\in\mathbb{R}[x]_{\lceil 3^{m-1}d_{G}/2-d_{G}/2\rceil}^{m\times 1}$ . Then, we know that

d_{i}S_{i}=\sigma_{i}S_{i}+\sum\limits_{j=1}^{s_{i}}\sum\limits_{t=1}^{r_{i}}v_{i,j}q_{i,t}^{T}Gq_{i,t}v_{i,j}^{T},

which implies that $d_{i}S_{i}\in\mbox{QM}[G]_{k+3^{m-1}d_{G}}^{\ell}$ . Since $(1-\|x\|_{2}^{2})\cdot I_{\ell}\in\mbox{QM}[G]^{\ell}$ , we know that $1-\|x\|_{2}^{2}\in\mbox{QM}[G]_{k_{0}}$ for some $k_{0}\in\mathbb{N}$ . Then, we know that $(1-\|x\|_{2}^{2})S_{\theta(m)+1}\in\mbox{QM}[G]_{k+k_{0}}^{\ell}$ . Let $C$ be sufficiently large. Then, we can drop the small terms $3^{m-1}d_{G}$ , $k_{0}$ , and thus $F\in\mbox{QM}[G]_{k}^{\ell}$ for $k$ satisfying (5.4). Since $d_{1},\dots,d_{\theta(m)}\in\mbox{QM}[G]_{3^{m-1}d_{G}}$ and

K=\left\{x\in\mathbb{R}^{n}\mid\frac{d_{1}(x)}{\left\|d_{1}\right\|_{B}}\geq 0,\dots,\dots,\frac{d_{\theta(m)}(x)}{\left\|d_{\theta(m)}\right\|_{B}}\geq 0\right\},

it follows from Theorem 2.4 that $\eta\leq(3^{m-1}d_{G}+1)(3^{m}d_{G})^{n+\theta(m)-2}$ .

Remark. When $G(x)$ is a diagonal polynomial matrix with diagonal entries $g_{1},\dots,g_{m}\in\mathbb{R}[x]$ , i.e.,

K=\{x\in\mathbb{R}^{n}\mid g_{1}(x)\geq 0,\dots,g_{m}(x)\geq 0\},

Theorem 5.1 implies that for $k$ greater than the quantity as in (5.4), we have $F\in\mbox{QM}[G]_{k}^{\ell}$ . However, the bound given in (3.6) from Theorem 3.5 is generally smaller than that in (5.4). Additionally, the proof of Theorem 5.1 builds upon Theorem 3.5.

5.2 Proof of Theorem 1.2

For a polynomial matrix $F=\sum_{\alpha\in\mathbb{N}^{n}_{d}}F_{\alpha}x^{\alpha}$ with $\deg(F)=d$ , $F^{hom}$ denotes its highest-degree homogeneous terms, i.e., $F^{hom}(x)=\sum_{\alpha\in\mathbb{N}^{n},|\alpha|=d}F_{\alpha}x^{\alpha}.$ The homogenization of $F$ is denoted by $\widetilde{F}$ , i.e., $\widetilde{F}(\tilde{x})=\sum_{\alpha\in\mathbb{N}^{n}_{d}}F_{\alpha}x^{\alpha}x_{0}^{d-|\alpha|}$ for $\tilde{x}:=(x_{0},x)$ . Let

(5.5)

\begin{array}[]{rcl}\widetilde{K}:=&\left\{\tilde{x}\in\mathbb{R}^{n+1}\left|\begin{array}[]{l}(x_{0})^{d_{0}}\widetilde{G}(\tilde{x})\succeq 0,\\ x_{0}^{2}+x^{T}x=1\end{array}\right.\right\},\\ \end{array}

where $d_{0}=2\lceil d_{G}/2\rceil-d_{G}$ . Consider the optimization

(5.6)

\left\{\begin{array}[]{rl}\min&\lambda_{\min}(\widetilde{F}(\tilde{x}))\\ \mathit{s.t.}&(x_{0})^{d_{0}}\widetilde{G}(\tilde{x})\succeq 0,\\ &x_{0}^{2}+x^{T}x=1,\\ \end{array}\right.

where $\lambda_{\min}(\widetilde{F}(\tilde{x}))$ is the smallest eigenvalue of $\widetilde{F}(\tilde{x})$ . Let $\widetilde{F}_{\min}$ denote the optimal value of (5.6).

Lemma 5.3.

Let $K$ be as in (5.1). Suppose that $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix with $\deg(F)=d$ . If $F\succ 0$ on $K$ and $F^{hom}\succ 0$ on $\mathbb{R}^{n}$ , then $\widetilde{F}_{\min}>0$ and $\widetilde{F}\succeq\widetilde{F}_{\min}\cdot I_{\ell}$ on $\widetilde{K}$ .

Proof 5.4.

Suppose $\tilde{x}=(x_{0},x)\in\widetilde{K}$ . If $x_{0}=0$ , then we have $\widetilde{F}(\tilde{x})=F^{hom}(x)\succ 0.$ If $x_{0}\neq 0$ , then

G(x/x_{0})=(x_{0})^{-d_{G}-d_{0}}(x_{0})^{d_{0}}\tilde{G}(\tilde{x})\succeq 0,

which implies that $x/x_{0}\in K$ . Since $F^{hom}\succ 0$ on $\mathbb{R}^{n}$ , the degree of $F$ must be even, and we have

\widetilde{F}(\tilde{x})=x_{0}^{d}F(x/x_{0})\succ 0.

Since $\widetilde{K}$ is compact, the optimal value of (5.6) is positive, i.e., $\widetilde{F}_{\min}>0$ .

For the polynomial matrix $(x_{0})^{d_{0}}\widetilde{G}(\tilde{x})$ , let $d_{1},\dots,d_{\theta(m)}$ be the polynomials as in Theorem 4.1. Denote

(5.7)

\mathcal{G}(\tilde{x})=-\min\left(\frac{d_{1}(\tilde{x})}{\left\|d_{1}\right\|_{B}},\ldots,\frac{d_{\theta(m)}(\tilde{x})}{\left\|d_{\theta(m)}\right\|_{B}},\frac{1-\|\tilde{x}\|_{2}^{2}}{\|1-\|\tilde{x}\|_{2}^{2}\|_{B}},\frac{\|\tilde{x}\|_{2}^{2}-1}{\|1-\|\tilde{x}\|_{2}^{2}\|_{B}},0\right).

Note that $\mathcal{G}(\tilde{x})=0$ implies that $\tilde{x}\in\widetilde{K}$ . By Corollary 2.2, there exist positive constants $\eta$ , $\kappa$ such that for all $\tilde{x}$ satisfying $\sqrt{n+1}-x_{0}-x_{1}-\cdots-x_{n}\geq 0,1+x_{0}\geq 0,1+x_{1}\geq 0,\ldots,1+x_{n}\geq 0$ , it holds that

(5.8)

d(\tilde{x},\widetilde{K})^{\eta}\leq\kappa\mathcal{G}(\tilde{x}).

In the following, we give the proof of Theorem 1.2, which provides a polynomial bound on the complexity of matrix Putinar–Vasilescu’s Positivstellensätz.

Theorem 5.5.

Let $K$ be as in (5.1) with $m\geq 2$ . Suppose that $F(x)$ is an $\ell$ -by- $\ell$ symmetric polynomial matrix with $\deg(F)=d$ . If $F\succ 0$ on $K$ and $F^{hom}\succ 0$ on $\mathbb{R}^{n}$ , then $(1+\|x\|_{2}^{2})^{k}F\in\mbox{QM}[G]_{2k+d}^{\ell}$ for

(5.9)

k\geq C\cdot{8}^{7\eta}\cdot 3^{6(m-1)}(\theta(m)+2)^{3}(n+1)^{2}(\lceil d_{G}/2\rceil)^{6}\kappa^{7}d^{14\eta}\left(\frac{\|\widetilde{F}\|_{B}}{\widetilde{F}_{\min}}\right)^{7\eta+3}.

In the above, $\kappa$ , $\eta$ are respectively the Łojasiewicz constant and exponent in (5.8), $C>0$ is a constant independent of $F$ , $G$ and $\widetilde{F}_{\min}$ is the optimal value of (5.6). Furthermore, the Łojasiewicz exponent can be estimated as

\eta\leq(2\cdot 3^{m-1}\lceil d_{G}/2\rceil+1)(2\cdot 3^{m}\lceil d_{G}/2\rceil)^{n+\theta(m)-1}.

Proof 5.6.

By Lemma 5.3, we have that $\widetilde{F}\succeq\widetilde{F}_{\min}\cdot I_{\ell}\succ 0$ on $\widetilde{K}$ . Note that $\mbox{QM}[1-\|\tilde{x}\|^{2}]^{\ell}$ is Archimedean, and ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widetilde{K}}$ can be equivalently described by

d_{1}(\tilde{x})\geq 0,\dots,d_{\theta(m)}(\tilde{x})\geq 0,1-\|\tilde{x}\|_{2}^{2}\geq 0,\|\tilde{x}\|_{2}^{2}-1\geq 0.

By following the proof of Theorem 1.1 for $\widetilde{F}(x)$ , we know that for $k$ satisfying (5.9), there exist $S\in\Sigma[\tilde{x}]^{\ell}$ , $H\in\mathbb{R}[\tilde{x}]^{\ell\times\ell}$ , $P_{i}\in\mathbb{R}[\tilde{x}]^{m\times\ell}$ ( $i=1,\dots,t$ ) with

\deg(S)\leq k,\,\deg(H)\leq k-2,\,\deg(P_{i}^{T}(x_{0})^{d_{0}}\widetilde{G}P_{i})\leq k~{}(i=1,\dots,t),

such that

\widetilde{F}(\tilde{x})=S(\tilde{x})+(\|\tilde{x}\|_{2}^{2}-1)\cdot H(\tilde{x})+\sum\limits_{i=1}^{t}P_{i}(\tilde{x})^{T}(x_{0})^{d_{0}}\widetilde{G}(\tilde{x})P_{i}(\tilde{x}).

Replacing $\tilde{x}$ by $(1,x)/\sqrt{1+\|x\|_{2}^{2}}$ in the above identity, we get that

(5.10)

\begin{array}[]{ll}\frac{F(x)}{\sqrt{1+\|x\|_{2}^{2}}^{d}}=&\sum\limits_{i=1}^{t}P_{i}\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right)^{T}\frac{G(x)}{\sqrt{1+\|x\|_{2}^{2}}^{d_{0}+d_{G}}}P_{i}\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right)\\ &+S\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right).\end{array}

Suppose that $S=V^{T}V$ for some polynomial matrix $V$ . Then, there exist polynomial matrices $V^{(1)},V^{(2)}$ with $2\deg(V^{(1)})\leq\deg(S)$ , $2\deg(V^{(2)})+2\leq\deg(S)$ such that

V\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right)=\left(\frac{1}{\sqrt{1+\|x\|_{2}^{2}}}\right)^{\deg(V)}(V^{(1)}+\sqrt{1+\|x\|_{2}^{2}}V^{(2)}).

It holds that

\begin{array}[]{ll}S\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right)=\frac{(V^{(1)})^{T}V^{(1)}+(1+\|x\|_{2}^{2})(V^{(2)})^{T}V^{(2)}}{\sqrt{1+\|x\|_{2}^{2}}^{\deg(S)}}+\frac{(V^{(2)})^{T}V^{(1)}+(V^{(1)})^{T}V^{(2)}}{\sqrt{1+\|x\|_{2}^{2}}^{\deg(S)-1}}.\end{array}

Similarly, there exist polynomial matrices $P_{i}^{(1)},P_{i}^{(2)}$ with $\deg(P_{i}^{(1)})\leq\deg(P_{i})$ , $\deg(P_{i}^{(2)})+1\leq\deg(P_{i})$ satisfying

P_{i}\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right)=\left(\frac{1}{\sqrt{1+\|x\|_{2}^{2}}}\right)^{\deg(P_{i})}(P_{i}^{(1)}+\sqrt{1+\|x\|_{2}^{2}}P_{i}^{(2)}),

Then, we have that

\begin{array}[]{l}\sum\limits_{i=1}^{t}P_{i}\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right)^{T}\frac{G(x)}{\sqrt{1+\|x\|_{2}^{2}}^{d_{0}+d_{G}}}P_{i}\left(\frac{(1,x)}{\sqrt{1+\|x\|_{2}^{2}}}\right)\\ \quad\quad\quad\quad\quad\quad=\sum_{i=1}^{t}\frac{(P_{i}^{(1)})^{T}G(x)P_{i}^{(1)}+(1+\|x\|_{2}^{2})(P_{i}^{(2)})^{T}G(x)P_{i}^{(2)}}{\sqrt{1+\|x\|_{2}^{2}}^{d_{0}+d_{G}+2\deg(P_{i})}}+\frac{(P_{i}^{(2)})^{T}G(x)P_{i}^{(1)}+(P_{i}^{(1)})^{T}G(x)P_{i}^{(2)}}{\sqrt{1+\|x\|_{2}^{2}}^{d_{0}+d_{G}+2\deg(P_{i})-1}}.\\ \end{array}

Combining these results with equation (5.10), we know that for $k$ satisfying (5.9), the following holds:

(1+\|x\|_{2}^{2})^{k}F=Q+\sqrt{1+\|x\|_{2}^{2}}H(x),

for some $Q\in\mbox{QM}[G]^{\ell}$ with $\deg(Q)\leq 2k+d$ and a symmetric polynomial matrix $H$ . Since $\sqrt{1+\|x\|_{2}^{2}}$ is not a rational function, we conclude that $(1+\|x\|_{2}^{2})^{k}F=Q$ , which implies $(1+\|x\|_{2}^{2})^{k}F\in\mbox{QM}[G]^{\ell}_{2k+d}$ .

Since $d_{1},\dots,d_{\theta(m)}\in\mbox{QM}[G]_{2\cdot 3^{m-1}\lceil d_{G}/2\rceil}$ and

\widetilde{K}=\left\{\tilde{x}\in\mathbb{R}^{n+1}\mid\frac{d_{1}(\tilde{x})}{\left\|d_{1}\right\|_{B}}\geq 0,\dots,\frac{d_{\theta(m)}(\tilde{x})}{\left\|d_{\theta(m)}\right\|_{B}}\geq 0,1-\|\tilde{x}\|_{2}^{2}=0\right\},

it follows from Theorem 2.4 that $\eta\leq(2\cdot 3^{m-1}\lceil d_{G}/2\rceil+1)(2\cdot 3^{m}\lceil d_{G}/2\rceil)^{n+\theta(m)-1}$ .

Proof of Corollary 1.3. Note that $F\succeq 0$ on $K$ , and we have

d+2\geq\deg(F+\varepsilon\cdot(1+\|x\|_{2}^{2})^{\lceil\frac{d+1}{2}\rceil}I_{\ell})=2\lceil\frac{d+1}{2}\rceil>d.

Hence, for $\tilde{x}\in\widetilde{K}$ , the homogenization of $F+\varepsilon\cdot(1+\|x\|_{2}^{2})^{\lceil\frac{d+1}{2}\rceil}I_{\ell}$ satisfies

\begin{array}[]{ll}x_{0}^{2\lceil\frac{d+1}{2}\rceil-d}\widetilde{F}+\varepsilon\cdot(x_{0}^{2}+\|x\|_{2}^{2})^{\lceil\frac{d+1}{2}\rceil}I_{\ell}\succeq\varepsilon\cdot(x_{0}^{2}+\|x\|_{2}^{2})^{\lceil\frac{d+1}{2}\rceil}I_{\ell}\succeq\varepsilon\cdot I_{\ell}.\\ \end{array}

The conclusion follows from Theorem 5.5.

5.3 Convergence rate of matrix SOS relaxations

Consider the polynomial matrix optimization

(5.11)

\left\{\begin{array}[]{rl}\min&f(x)\\ \mathit{s.t.}&G(x)\succeq 0,\\ \end{array}\right.

where $f(x)\in\mathbb{R}[x]$ , $G(x)$ is an $m\times m$ symmetric polynomial matrix. We denote the optimal value of (5.11) as $f_{\min}$ .

A standard approach for solving (5.11) globally is the sum-of-squares hierarchy introduced in [16, 28, 48]. This hierarchy consists of a sequence of semidefinite programming relaxations. Recall that for a degree $k$ , the $k$ th degree truncation of $\mbox{QM}[G]$ is

\mbox{QM}[G]_{k}:=\left\{\begin{array}[]{l|l}\sigma+\sum_{i=1}^{t}v_{i}^{T}Gv_{i}&\begin{array}[]{l}\sigma\in\Sigma[x],~{}v_{i}\in\mathbb{R}[x]^{m},~{}t\in\mathbb{N},\\ \deg(\sigma)\leq k,~{}\deg(v_{i}^{T}Gv_{i})\leq k\end{array}\end{array}\right\}.

Checking whether a polynomial belongs to the the quadratic module $\mbox{QM}[G]_{k}$ can be done by solving a semidefinite program (see [48]). For an order $k$ , the $k$ th order SOS relaxation of (5.11) is

(5.12)

\left\{\begin{array}[]{cl}\max&\gamma\\ \text{ s.t. }&f-\gamma\in\mathrm{QM}[G]_{2k}.\end{array}\right.

Let $f_{k}$ denote the optimal value of (5.12). It holds the monotonicity relation: $f_{k}\leq f_{k+1}\leq\cdots\leq f_{\min}.$ The hierarchy (5.12) is said to have asymptotic convergence if $f_{k}\rightarrow\infty$ as $k\rightarrow\infty$ , and it is said to have finite convergence if $f_{k}=f_{\min}$ for all $k$ big enough. When the quadratic module $\mbox{QM}[G]$ is Archimedean, it was shown in [16, 28, 48] that the hierarchy (5.12) converges asymptotically. Recently, Huang and Nie [24] proved that this hierarchy also has finite convergence if, in addition, the nondegeneracy condition, strict complementarity condition and second order sufficient condition hold at every global minimizer of (5.11). In the following, we provide a polynomial bound on the convergence rate of the hierarchy (5.12).

Theorem 5.7.

Suppose $f\in\mathbb{R}[x]$ with $d=\deg(f)$ , $m\geq 2$ , and $1-\|x\|_{2}^{2}\in\mbox{QM}[G]$ . Then we have that

(5.13)

|f_{k}-f_{\min}|\leq 3\cdot(C\cdot{8}^{7\eta}\cdot 3^{6(m-1)}\theta(m)^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14\eta})^{\frac{1}{7\eta+3}}\|f\|_{B}\left(\frac{1}{k}\right)^{\frac{1}{7\eta+3}},

where $\kappa$ , $\eta$ are respectively the Łojasiewicz constant and exponent in (5.3), and $C>0$ is a constant independent of $f$ , $G$ . Furthermore, the Łojasiewicz exponent can be estimated as

\eta\leq(3^{m-1}d_{G}+1)(3^{m}d_{G})^{n+\theta(m)-2}.

Proof 5.8.

Since $f_{\min}\leq\|f\|_{B}$ (see [13]), we have that for $0<\varepsilon\leq\|f\|_{B}$ ,

\|f-f_{\min}+\varepsilon\|_{B}\leq\|f\|_{B}+|f_{\min}|+\varepsilon\leq 3\|f\|_{B}.

Since $f-f_{\min}+\varepsilon\geq\varepsilon$ on $K$ , it follows from Theorem 1.1 that $f-f_{\min}+\varepsilon\in\mbox{QM}[G]_{k}$ for

k\geq C\cdot{8}^{7\eta}\cdot 3^{6(m-1)}\theta(m)^{3}n^{2}d_{G}^{6}\kappa^{7}d^{14\eta}\left(\frac{3\|f\|_{B}}{\varepsilon}\right)^{7\eta+3},\\

and $\eta\leq(3^{m-1}d_{G}+1)(3^{m}d_{G})^{n+\theta(m)-2}$ . Then, we know that $f_{\min}-\varepsilon$ is feasible for (5.12), i.e., $f_{k}\geq f_{\min}-\varepsilon$ when $k$ satisfies the above inequality. Equivalently, we know that the relation $(\ref{rate})$ holds.

6 Conclusions and discussions

In this paper, we establish a polynomial bound on the degrees of terms appearing in matrix Putinar’s Positivstellensätz. For the special case that the constraining polynomial matrix is diagonal, this result improves the exponential bound shown in [15]. As a byproduct, we also obtain a polynomial bound on the convergence rate of matrix SOS relaxations, which resolves an open question posed by Dinh and Pham [10]. When the constraining set is unbounded, a similar bound is provided for matrix Putinar–Vasilescu’s Positivstellensätz.

Theorem 1.1 uses the Łojasiewicz inequality (5.3) for equivalent scalar polynomial inequalities of $K$ . There also exists the Łojasiewicz inequality for polynomial matrices (see [9, 10]), where the corresponding Łojasiewicz exponent is typically smaller than the scalar one as in (5.3). An interesting future work is to provide a proof based directly on the Łojasiewicz inequality for $G(x)$ , which may yields a better bound. On the another hand, the set $\{x\in\mathbb{R}^{n}\mid G(x)\succeq 0\}$ can be equivalently described by the quantifier set $\{x\in\mathbb{R}^{n}\mid y^{T}G(x)y\geq 0,~{}\forall~{}\|y\|_{2}=1\}.$ It would also be interesting to study the complexity of Putinar-type Positivstellensätze with universal quantifiers for the above reformulation. We refer to [19] for the recent work on Positivstellensätze with universal quantifiers.

When $K$ is given by scalar polynomial inequalities, it was shown in [45] that the Łojasiewicz exponent $\eta$ as in (3.5) is equal to $1$ if the linear independence constraint qualification holds at every $x\in K$ . Consequently, we can get a representation with order $\left(\frac{\|F\|_{B}}{F_{\min}}\right)^{10}$ . An analogue to the linear independence constraint qualification in nonlinear semidefinite programming is the nondegeneracy condition [52, 56]. It would also be interesting to explore whether similar results exist for polynomial matrix inequalities under the nondegeneracy condition.

Acknowledgements: The author would like to thank Prof. Konrad Schmüdgen for helpful discussions on Proposition 1, Prof. Tien-Son Pham for fruitful comments on this paper. The author also thanks the associate editor and three anonymous referees for valuable comments and suggestions.

References

[1] F. Bach and A. Rudi, Exponential convergence of sum-of-squares hierarchies for trigonometric polynomials, SIAM J. Optim., 11 (2023), pp. 796–817.
[2] L. Baldi and B. Mourrain, On the effective Putinar’s Positivstellensätz and moment approximation, Math. Program., 200 (2023), pp. 71–103.
[3] L. Baldi, B. Mourrain and A. Parusinski, On Łojasiewicz inequalities and the effective Putinar’s Positivstellensätz, J. Algebra, 662 (2025), pp. 741–767.
[4] L. Baldi and L. Slot, Degree bounds for Putinar’s Positivstellensätz on the hypercube, SIAM J. Appl. Algebra Geom., 8 (2023), pp. 1–25.
[5] J. Bochnak, M. Coste and M. Roy, Real Algebraic Geometry, Springer, Berlin, 1998.
[6] G. Chesi, LMI techniques for optimization over polynomials in control: a survey, IEEE Trans. Autom., 55 (2010), pp. 2500–2510.
[7] J. Cimpric, Real algebraic geometry for matrices over commutative rings, J. Algebra 359 (2012), pp. 89–103.
[8] E. De Klerk and M. Laurent, On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems, SIAM J. Optim., 21 (2011), pp. 824–832.
[9] S. Dinh. and T. Pham, Łojasiewicz-type inequalities with explicit exponents for the largest eigenvalue function of real symmetric polynomial matrices, Internat. J. Math., 27 (2016) , 1650012.
[10] S. Dinh. and T. Pham, Łojasiewicz inequalities with explicit exponents for smallest singular value functions, J. Complex., 41 (2017), pp. 58–71.
[11] T. Dinh., M. Ho and C. Le, Positivstellensätze for polynomial matrices, Positivity 25 (2021), pp. 1295–1312.
[12] K. Fang and H. Fawzi, The sum-of-squares hierarchy on the sphere and applications in quantum information theory, Math. Program. 190 (2021), pp. 331-–360.
[13] G. Farin, Curves and Surfaces for CAGD: A Practical Guide, 5th ed. Morgan Kaufmann Series in Computer Graphics and Geometric Modeling, San Francisco, 2021.
[14] H. H $\grave{\text{a}}$ and T. Pham, Genericity in Polynomial Optimization, World Scientific Publishing, Singapore, 2017.
[15] J. Helton and J. Nie, Semidefinite representation of convex sets, Math. Program., 122 (2010), pp. 21–64.
[16] D. Henrion and J. Lasserre, Convergent relaxations of polynomial matrix inequalities and static output feedback, IEEE Trans. Autom. Control, 51 (2006), 192–202.
[17] D. Henrion and J. Lasserre, Inner approximations for polynomial matrix inequalities and robust stability, IEEE Trans. Autom. Control, 57 (2011), pp. 1456–1467.
[18] D. Henrion, M. Korda and J. Lasserre, The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs, World Scientific, Cambridge, 2020.
[19] X. Hu, I. Klep and J. Nie, Positivstellensätze and moment problems with universal quantifiers, arXiv preprint, https://arxiv.org/abs/2401.12359, 2024.
[20] L. Huang, Optimality conditions for homogeneous polynomial optimization on the unit sphere, Optim Lett, 17 (2023), pp. 1263–1270.
[21] L. Huang, J. Nie and Y. Yuan, Homogenization for polynomial optimization with unbounded sets, Math. Program., 200 (2023), pp. 105–145.
[22] L. Huang, J. Nie, and Y. Yuan, Generalized truncated moment problems with unbounded sets, J. Sci. Comput., 95 (2023).
[23] L. Huang, J. Nie and Y. Yuan, Finite convergence of Moment-SOS relaxations with non-real radical ideals, SIAM J. Optim., 34 (2024), pp. 3399–3428.
[24] L. Huang and J. Nie, On the tightness of matrix Moment-SOS hierarchy, arXiv preprint, https://arxiv.org/abs/2403.17241, 2024.
[25] H. Ichihara and J. Lasserre, Optimal control for polynomial systems using matrix sum of squares relaxations, IEEE Trans. Autom. Control, 54 (2009), pp. 1048–1053.
[26] T. Jacobi and A. Prestel, Distinguished representations of strictly positive polynomials, J. Reine Angew. Math., 532 (2001), pp. 223–235.
[27] I. Klep and M. Schweighofer, Pure states, positive matrix polynomials and sums of hermitian squares, Indiana Univ. Math. J., 59 (2010), pp. 857–874.
[28] M. Kojima, Sums of squares relaxations of polynomial semidefinite programs, In: Research Reports on Mathematical and Computing Sciences Series B: Operations Research B-397, Tokyo Institute of Technology, 2003.
[29] M. Korda, V. Magron and Z. Rios-Zertuche, Convergence rates for sums-of-squares hierarchies with correlative sparsity, Math. Program., (2024), to appear.
[30] A. Kroo and S. Revesz, On Bernstein and Markov-type inequalities for multivariate polynomials on convex bodies, J Approx Theory, 99 (1999), pp. 134–152.
[31] J. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796–817.
[32] J. Lasserre, Convexity in semialgebraic geometry and polynomial optimization, SIAM J. Optim., 19 (2009), pp. 1995–2014.
[33] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications, 149 (2009), pp. 157–270.
[34] S. Łojasiewicz, Sur le problème de la division, Studia Math., 18 (1959), pp. 87–136.
[35] N. Mai and V. Magron, On the complexity of Putinar–Vasilescu’s Positivstellensätz, J. Complexity, 72 (2022), 101663.
[36] M. Marshall, Representation of non-negative polynomials with finitely many zeros, Annales de la Faculte des Sciences Toulouse, 15 (2006), pp. 599–609.
[37] J. Nie, Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. Program., 146 (2014), pp. 97–121.
[38] J. Nie, Moment and Polynomial Optimization, SIAM, Philadelphia, 2023.
[39] J. Nie and M. Schweighofer, On the complexity of Putinar’s Positivstellensätz, J. Complexity, 23 (2007), pp. 135–150.
[40] G. Polya, Uber positive Darstellung von Polynomen, Vierteljahresschrift der Naturforschenden Gesellschaft in Zurich, 73 (1928), pp. 141–145.
[41] V. Powers and B. Reznick, A new bound for Polya’s theorem with applications to polynomials positive on polyhedra, J. Pure Appl. Algebra, 164 (2001), pp. 221–229.
[42] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), pp. 969–984.
[43] M. Putinar and F Vasilescu, Positive polynomials on semi-algebraic sets, C. R. Acad. Sci. Ser. I Math., 328 (1999), pp. 585–589.
[44] M. Putinar and F Vasilescu, Solving moment problems by dimensional extension, C. R. Acad. Sci. Ser. I Math., 328 (1999), pp. 495–499.
[45] S. Robinson, Stability theorems for systems of inequalities. Part II: Differentiable nonlinear systems, SIAM J. Numer. Anal., 13 (1976), pp. 497–513.
[46] C. Scheiderer, Distinguished representations of non-negative polynomials, J. Algebra, 289 (2005), pp. 558–573.
[47] C. Scherer, LMI relaxations in robust control, Eur. J. Control, 2 (2006), pp. 3–29.
[48] C. Scherer and C. Hol, Matrix sum-of-squares relaxations for robust semi-definite programs, Math. Program., 107 (2006), pp. 189–211.
[49] K. Schmüdgen, The $K$ -moment problem for compact semi-algebraic sets, Math. Ann., 289(1991), pp. 203–206.
[50] K. Schmüdgen, Noncommutative real algebraic geometry: some basic concepts and first ideas, In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications, 149 (2009), pp. 325–350.
[51] M. Schweighofer, On the complexity of Schmüdgen’s Positivstellensätz, J. Complexity, 20 (2004), pp. 529–543.
[52] A. Shapiro, First and second order analysis of nonlinear semidefinite programs, Math. Program., 77 (1997), pp. 301–320.
[53] L. Slot, Sum-of-squares hierarchies for polynomial optimization and the Christoffel–Darboux kernel, SIAM J. Optim., 32 (2022), pp. 2612–2635.
[54] L. Slot and M. Laurent, An effective version of Schmüdgen’s Positivstellensätz for the hypercube, Optim Lett, 17 (2023), pp. 515–530.
[55] L. Slot and M. Laurent, Sum-of-squares hierarchies for binary polynomial optimization, Math. Program., 197 (2023), pp. 621–660.
[56] D. Sun, The strong second order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications, Math. Oper. Res., 31 (2006), pp. 761–776.
[57] M. Tyburec, J. Zeman, M. Kruzık and D. Henrion, Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy, Struct Multidisc Optim , 64 (2021), pp. 1963–1981.
[58] Y. Zheng and G. Fantuzzi, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Math. Program., 197 (2023), pp. 71–108.