数理解析研究所講究録
第 1773 巻 2012 年 36-46

36

A PERTURBATION THEOREM ON POLYNOMIALOPTIMIZATION AND ITS EXTENSIONS
Masakazu Muramatsu , and Hayato Waki
Department of Communication Engineering and Informatics,
The University of Electro-Communications
1-5-1 Chofugaoka, ChofU-shi, Tokyo, 182-8585 JAPAN.

Abstract
We prove a property of positive polynomials on a compact set witha small perturbation. When applied to a POP, the property implies
that the optimal value of the corresponding SDP relaxation with
sufficiently large relaxation order is bounded from below byis the optimal value ofand from above by $f^{*}+\epsilon(n+1)$ , where
the POP. This may help us to understand the funny phenomena of
SDP relaxations for polynomial optimization problems observed in[4, 17, 18].
$f^{*}-\epsilon$$f^{*}$

1

Introduction

1.1

Lasserre’s SDP relaxation for POP

We consider the POP:
minimize $f(x)$ subject to(1)$f_{i}(x)\geq 0(i=1, \ldots, m)$ ,are polynomials. The feasible region is denoted by $K=$$\{x\in \mathbb{R}^{n}|f_{j}(x)\geq 0(j=1, \ldots, m)\}$ . Then it is easy to see that the optimal value
canbe represented as$f^{*}= \sup\{\rho|f(x)-\rho\geq 0(\forall x\in K)\}$ .
We briefly describe the framework of the SDP realxation method for POP (1) proposed
where $f,$$f_{1},$$\ldots,$$f_{m}$:$\mathbb{R}^{n}arrow \mathbb{R}$$f^{*}$by Lasserre [8]. See also [13].
and , respectively.
We denote the set of polynomials and sums of squares byis the set of polynomials whose degree is less than or equals to . We letas. We define the quadratic module generated by$\Sigma$$\mathbb{R}[x]$$\Sigma_{r}=$$r$$\mathbb{R}[x]_{r}$$f_{1},$$\Sigma\cap \mathbb{R}[x]_{2r}$$M(f_{1}, \ldots, f_{m})=\{\sigma_{0}+\sum_{j=1}^{m}\sigma_{j}f_{j}|\sigma_{0},$$\ldots,$$\ldots,$$f_{m}$$\sigma_{m}\in\Sigma\}$.

The truncated quadratic module whose degree is less than or equal to $2r$ is defined by$M_{r}(f_{1}, \ldots, f_{m})=\{\sigma_{0}+\sum_{i=1}^{m}\sigma_{j}f_{j}|\sigma_{0}\in\Sigma_{r},$ $\sigma_{j}\in\Sigma_{r_{j}}(j=1, \ldots, m)\}$

,

37
$m$ .
where $r_{j}=r-\lceil\deg f_{j}/2\rceil$ for $j=1,$
Substituting the condition that $f(x)-\rho$ is nonnegative by another relaxed condition
that the polynomial is contained in, we obtain the following SOS relaxation$\ldots,$$M_{r}(f_{1}, \ldots, f_{m})$problem:$\rho_{r}=\sup\{\rho|f(x)-\rho\in M_{r}(f_{1}, \ldots, f_{m})\}$(2).

Lasserre[8] showed thatas $rarrow\infty$ if $M(f_{1}, \ldots, f_{m})$ is Archimedean. See [12, 14]
for the definition of Archimedean. In particluar, we point out that when $M(f_{1}, \ldots, f_{m})$is Archimedean, then $K$ is compact.
The problem (2) can be encoded to an SDP problem. Note that we can express a sum ofsquaresby using a positive semidefinite matrix
as $\sigma(x)=u_{r}(x)^{T}Xu_{r}(x)$ ,
where
and
is a monomial vector which contains all the monomials invariables up to degree . By using this relation, the containment by
in(2), i.e.,$\rho_{r}arrow f^{*}$$X\in S_{+}^{s(r)}$$\sigma\in\Sigma_{r}$$u_{r}(x)$$s(r)=(\begin{array}{l}n+rn\end{array})$$n$$M_{r}(f_{1}, \ldots, f_{m})$$r$$f- \rho=\sigma+\sum_{j=1}^{m}\sigma_{j}f_{j}$,can be transformed to equality constraints between semidefinite matrix variables corresponding to and.
Note that, in this paper, we do not assume that $K$ is compact nor thatis Archmedean. Still the framework of Lasserre‘s SDP relaxation can be applied to (1),althogh the good theoretical convergence property is lost.
$\sigma$$\sigma_{j}’ s$$M(f_{1}, \ldots, f_{m})$1.2Problems in the SDP relaxation for POP

Because POP is NP-hard, solving POP practically is sometimes extremely difficult. The
SDP relaxation method described above also has some difficulty. The major difficulty
consists in the size of the SDP relaxation problem (2). In fact, (2) contains
variables
and $s(r)\cross s(r)$ matrix. When and $/orr$ get larger, solving (2) is just impossible.
To overcome this difficulty, several techniques using sparsity of polynomials are proposed. See, e.g., [6, 15]. Based on the fact that most of the practical POPs are sparse insome sense, these techniques exploit special sparse structure of POPs to reduce the size
and the number of variables of the SDP (2).
Another problem of the SDP relaxation is that (2) is often ill-posed. In [4, 17, 18],
strange behaviors of SDP solvers are reported. Among them is that an SDP solver returns
an ‘optimal’ value of (2) which is significantly different from the true optimal value without
reporting no numerical errors. Even more strange is that the returned value by the SDP
solver is nothing but the real optimal value of the POP (1). This is a ‘super-accurate’
property of the SDP relaxation for POP.
$(\begin{array}{l}n+2rn\end{array})$

$n$

1.3

Contribution of this paper

We assume that there exists an optimal solution$x^{*}$of (1). Let

$b$

$=$

$\max(1, \max\{|x_{i}^{*}||i=1, \ldots, n\})$

$B$

$=$

$[-b, b]^{n}$.

38
Obviously $x^{*}\in B$ . We define:$\overline{K}$$=$$B\cap K$$= \max\{|f_{j}(x)||x\in B\}(j=1, \ldots, m)$$R_{j}$$R= \sum_{j=1}^{m}R_{j}$.

Define also, for a positive integer ,$r$$\psi_{r}(x)$$=$$- \sum_{j=1}^{m}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}$$\Theta_{r}(x)$$=$$1+ \sum_{i=1}^{n}x_{i}^{2r}$$\Theta_{r,b}(x)$$=$$1+ \sum_{i=1}^{n}(\frac{x_{i}}{b})^{2r}$,,We will prove the following theorem.
Theorem 1 Suppose that forbound of .

$\rho\in \mathbb{R},$$f(x)-\rho>0$ for every$x\in\overline{K}$, i. e.,$\rho$

is an lower$f^{*}$$i$$ii$. Then there exists$\tilde{r}\in \mathbb{N}$. In addition, for any

such that for all$\epsilon>0$$r\geq\tilde{r},$$f-\rho+\psi_{\overline{r}}$, there exists a positive integer$f-\rho+\epsilon\Theta_{r,b}+\psi_{\overline{r}}\in\Sigma$$\hat{r}$is positive over $B$ .

such that, for every$r\geq\hat{r}$,.

We remark that depends on and , while depends on , but not .
The implication of this theorem is twofold. First, it elucidates the super-accurate
property of the SDP relaxation for POPs. Notice that by construction,. Now assume that in (2),. Then, for any
wherelower bound of , Theorem 1 means thatfor arbitrarysmall
and sufficiently large . Such small perturbation is inevitably introduced
everywhere in the floating point arithmetics which is used by the interior-point methods
for solving the SDP relaxation problems. Note that we chose an artibrary lower bound of, and in (2), the lower bound is being maximized. Therefore, we may obtain
due tothe implicit perturbation introduced by the floating point arithmetics.
Second, we can use the result to construct new sparse SDP relaxations for POP (1).
A naive idea is that we use (1) as is. Note that
contains only monomials whose
exponents are contained in$\tilde{r}$$\hat{r}$$\epsilon$$\rho$$\epsilon$$\rho$$-\psi_{\overline{r}}(x)\in$$\overline{r}=\tilde{r}\max_{j}(\deg(f_{j}))$$M_{\overline{r}}(f_{1}, \ldots, f_{m})$$\overline{\rho}$$\epsilon>0$$r\geq\overline{r}$$f-\overline{\rho}+\epsilon\Theta_{r,b}\in M_{r}(f_{1}, \ldots, f_{m})$$f^{*}$$r$$f^{*}$$f^{*}$$-\psi_{\overline{r}}(x)$39is the support of the polynomial
wherewith nonzero coefficients in , andwe introduce a notation. For a finite set
and$\mathcal{F}_{j}$$f_{j}$, i. e., the set of exponents of monomials$\tilde{\mathcal{F}}_{j}=\mathcal{F}_{j}\cup\{0\}$$f_{j}$$\mathcal{F}\subseteq \mathbb{N}^{n}$. To state the idea more precisely,
and a positive integer , we denote$r$$r\mathcal{F}=\mathcal{F}+\cdots+\mathcal{F}\tilde{r}$$\Sigma(\mathcal{F})=\{\sum_{k=1}^{q}g_{k}(x)^{2}|supp(g_{k})\subseteq \mathcal{F}\}$,

where $supp(g_{k})$ is the support of . Note thatis the set of sums of squares ofpolynomials whose supports are contained by .
Now, fix an admissible error
and as in Theorem 1, and consider:$\Sigma(\mathcal{F})$$g_{k}$$\mathcal{F}$$\epsilon>0$$\hat{\rho}(\epsilon,\tilde{r}, r)=\sup\{\rho$

for some$r\geq\tilde{r}$$\tilde{r}$$f- \rho+\epsilon\Theta_{r,b}-\sum_{j=1}^{m}f_{j}\sigma_{j}=\sigma_{0},$$\sigma_{0}\in\Sigma_{r},$$\sigma_{j}\in\Sigma(\tilde{r}\tilde{\mathcal{F}}_{j})\}$(3). Due to Theorem 1, (3) has a solution for a sufficiently large .
$r$Theorem 2 For any$\epsilon>0$, there exists$r\in \mathbb{N}$Proof: We apply Theorem 1 to POP (1) withsuch that for every
integerwhich satisfies$\hat{r},\tilde{r}\in \mathbb{N}$$r\geq\hat{r},$such that$f^{*}-\epsilon\leq\hat{\rho}(\epsilon,\tilde{r}, r)\leq f^{*}+\epsilon(n+1)$$\rho=f^{*}-\epsilon$.

, there exist. Then for any. We choose a positive$\epsilon>0$$f-(f^{*}-\epsilon)+\epsilon\Theta_{r,b}+\psi_{\overline{r}}\in\Sigma$$r\geq\hat{r}$$r \geq\max\{\lceil\deg(f)/2\rceil, \lceil(\tilde{r}+1/2)\deg(f_{1})\rceil, \ldots, \lceil(\tilde{r}+1/2)\deg(f_{m})\rceil\}$.

(4)

Then there exists
such that
because the degree ofthe polynomial in the left hand side is equal to $2r$ . We denote
for all. The triplet. Therefore,
is feasible in (3) because
we have.
We prove that
. We choose as in (4) and consider thefollowing POP:$\tilde{\sigma}_{0}\in\Sigma_{r}$$f-(f^{*}-\epsilon)+\epsilon\Theta_{r,b}+\psi_{\overline{r}}=\tilde{\sigma}_{0}$$\tilde{\sigma}_{j}$$j$$:=(1-f_{j}/R_{j})^{2\overline{r}}$$(1-f_{j}/R_{j})^{2\overline{r}}\in\Sigma(\tilde{r}\tilde{\mathcal{F}}_{j})$$(f^{*}-\epsilon,\tilde{\sigma}_{0},\tilde{\sigma}_{j})$$f^{*}-\epsilon\leq\hat{\rho}(\epsilon,\tilde{r}, r)$$\hat{\rho}(\epsilon,\tilde{r}, r)\leq f^{*}+\epsilon(n+1)$$r$$f;= \inf_{x\in R^{n}}\{f(x)+\epsilon\Theta_{r,b}(x)|f_{1}(x)\geq 0, \ldots, f_{m}(x)\geq 0\}$

Apply Lasserre‘s SDP relaxation with relaxation order
SOS relaxation problem:$\hat{\rho}(\epsilon, r):=\sup\{\rho$where$r_{j}$$f- \rho+\epsilon\Theta_{r,b}=\sigma_{0}+\sum_{j=1}^{m}f_{j}\sigma_{j},$$\sigma_{0}\in\Sigma_{r},$ $\sigma_{j}\in\Sigma_{r_{j}}\}$$\hat{\rho}(\epsilon, r)\geq\hat{\rho}(\epsilon,\tilde{r}, r)$$\ldots,$$j$and thus.
The optimal solution. We have(5)

to (5), we obtain the following$m$ .
for $j=1,$
Then we havefor all . Indeed, it follows from (4) and definition of$:=r-\lceil\deg(f_{j})/2\rceil$$\Sigma(\tilde{r}\tilde{\mathcal{F}}_{j})\subseteq\Sigma_{r_{j}}$$r$.

$r_{j}$

that(6)

because$r_{j}\geq\tilde{r}\deg(f_{j})$,$\Sigma(\tilde{r}\tilde{\mathcal{F}}_{j})\subseteq\Sigma_{r_{j}}$$\Theta_{r,b}(x^{*})$$x^{*}$of POP (1) is feasible in (5) and the objective value is $f^{*}+$
because (3) is the relaxation problem of (1).

$f^{*}+\Theta_{r,b}(x^{*})\geq\hat{\rho}(\epsilon, r)$40
In addition, it follows from $x^{*}\in B$ that $n+1\geq\Theta_{r,b}(x^{*})$ , and thus$f^{*}+\epsilon(n+1)$$\hat{\rho}(\epsilon,\tilde{r}, r)\leq\hat{\rho}(\epsilon, r)\square \leq$.

In the above sparse relaxation (3), we have only to consider positive semidefinite
matrices whose rows and columns correspond tofor . In contrast in Lasserre‘s SDP
relaxation, we have to consider the whole set of monomials whose degree is less than orequals to for each polynomial . Only
is large; it contains all the set of monomials
whose degree is less than or equals to . However, because the other polynomials do notcontain most of the monomials of , such monomials may be safely eliminated to reduce
the size ofusing the technique proposed in [6]. As a result, our sparse relaxation
reduces the size of the matrix significantly if eachis small enough. We note that inmost of the practical cases, in fact this is true.
Finally, we consider the case where the feasible region $K$ is empty. $If-1\in M(f_{1}, \ldots, f_{m})$ ,then the feasible region $K$ is empty. Indeed, there exist sums of square polynomials. If $K$ is non empty, then we obtain asuch that-lcontradiction by substituting
into this identity.
However, the converse does not hold in general. For instance, let $f_{1}=x,$ $f_{2}=y,$ $f_{3}=$$-1-xy$ . Then $K$ is empty, but $-1\not\in M(f_{1}, f_{2}, f_{3})$ . We can prove this fact by using a
discussion in [14, Example 6.3.1].
The following result is directly obtained as a corollary of Theorem 1. We omit theproof.
$\tilde{r}\tilde{\mathcal{F}}_{j}$$f_{j}$$r_{j}$$f_{j}$$\sigma_{0}$$r$$\sigma_{0}$$\sigma_{0}$$|\mathcal{F}_{j}|$$\sigma_{0},$$\ldots,$$= \sigma_{0}(x)+\sum_{j=1}^{m}\sigma_{j}(x)f_{j}(x)$$\sigma_{m}$$\tilde{x}\in K$

Theorem 3 We assume that $K$ is empty. Then for any.
that for every$r\geq\hat{r},$$\epsilon>0$, there exists$\hat{r}\in \mathbb{N}$such$-1+\epsilon\Theta_{r}\in M(f_{1}, \ldots, f_{m})$The rest of this paper is organized as follows. In the next section, we prove Theorem
1. In Section 3, we give two extensions of Theorem 1. The former is a sparse version, andthe latter, a symmetric cone version.

2

A Proof of Theorem 1

Lemma 4 For any
holds.

$\epsilon>0$, there exists$\overline{r}$such that for all$r\geq\overline{r}$and $x\in B,$$\psi_{r}(x)\geq-\epsilon$

Proof: We have$\psi_{r}(x)$$=$$- \sum_{j=1}^{m}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}$$=$$- \sum_{jf_{j}(x)>0}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}-\sum_{jf_{j}(x)<0}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}$$\geq$$- \sum_{j:f_{j}(x)>0}R_{j}\frac{f_{j}(x)}{R_{j}}(1-\frac{f_{j}(x)}{R_{j}})^{2r}$41Note that, for any$0\leq\lambda\leq 1$,$\lambda(1-\lambda)^{2r}\leq(\frac{2r}{2r+1})^{2r}\frac{1}{2r+1}\leq\frac{1}{2r+1}\leq\frac{1}{2r}$and that if $r\geq R/(2\epsilon)$ , thenfurther evaluate
as$\lambda(1-\lambda)^{2r}\leq\epsilon/R$

on$\lambda\in[0,1]$,. Therefore, for such , we can$r$$\psi_{r}(x)$,$\psi_{r}(x)\geq-\sum_{j.f_{j}(x)>0}R_{j}\frac{\epsilon}{R}\geq-\epsilon$

because $x\in B$ and $f_{j}(x)>0$ imply $0<f_{j}(x)/R_{j}\leq 1$ . This completes the proof.
Lemma 5 Let, and $\kappa>0$ be given. Then there exist
and for any
holds.
for all$\tilde{x}\in B\backslash \overline{K}$$x\in B(\tilde{x},\tilde{\delta})\cap B,$$r\geq\tilde{r}$$\tilde{\delta}>0$

and$\tilde{r}$$\square$such that$\psi_{r}(x)\geq\kappa$

Proof: For every $x\in B$ , we have$\psi_{r}(x)$$=$$- \sum_{jf_{j}(x)>0}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}-\sum_{jf_{j}(x)<0}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}$$\geq$$- \sum_{j.f_{j}(x)>0}f_{j}(x)-\sum_{jf_{j}(x)<0}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}$$\geq$$-R- \sum_{j:f_{j}(x)<0}f_{j}(x)(1-\frac{f_{j}(x)}{R_{j}})^{2r}$, the minimum of
Since
over $j=1,$
of polynomials implies that there exist $\delta>0$ and. Then we can further evaluateas$\tilde{x}\in B\backslash \overline{K}$$f_{j}(\tilde{x})$$\ldots,$

is negative. The continuity, thensuch that if$m$$\overline{\lambda}<0$$\min_{j}f_{j}(x)\leq\overline{\lambda}$$x\in B(\tilde{x}, \delta)$$\psi_{r}(x)$$\psi_{r}(x)\geq-R-\overline{\lambda}(1-\frac{\overline{\lambda}}{R})^{2r}$for everysuch that. Because
for every$x\in B(\tilde{x}, \delta)\cap B$$\tilde{r}$$\psi_{r}(x)\geq\kappa$

and
and

$\overline{\lambda}<0$$r\geq\tilde{r}$, there exists a positive integer$1-\overline{\lambda}/R>1$$x\in B(\tilde{x}, \delta)\cap B$.

$\square$be a minimizer of $f-\rho+\psi_{r}$ on . We show thelemma by proving that there exists a positive integer such thatfor every.
Suppose to the contrary that for any, there exists such that
. Because is arbitrary, the set $L=\{r|f(\tilde{x}^{r})-\rho+\psi_{r}(\tilde{x}^{r})\leq 0\}$ is infinite. Since
and a, we can take an accumulation pointofsubsequence
converging to .
In the following, we will prove there exist a positive integer and a positive number. Becausesuch that $f(x)-\rho+\psi_{r}(x)>0$ for every
andProof of (i) of Theorem 1 : Let$B$$\tilde{x}^{r}$$f(\tilde{x}^{r})-\rho+\psi_{r}(\tilde{x}^{r})>0$$\tilde{r}$$r\geq\tilde{r}$$\tilde{r}>0$$0$$f(\tilde{x}^{r})-\rho+\psi_{r}(\tilde{x}^{r})\leq$$r$$\tilde{r}$$\{\tilde{x}^{r}|r\in L\}\subseteq B$$\{\tilde{x}^{r}|r\in L’\}$$\tilde{x}^{*}\in B$$\{\tilde{x}^{r}|r\in L\}$$\tilde{x}^{*}$$\tilde{r}$$\tilde{\delta}$$x\in B(\tilde{x}^{*},\tilde{\delta})\cap B$$r\geq\tilde{r}$42for sufficiently large $r\in L’$ , this contradicts thatis an accumulation
point of, establishing the lemma.
We first consider the case where. Sinceis compact, we can takesuch$f(x)-\rho\geq\epsilon$
that. Then, there exists a positive number
for everysuch that$f(x)-\rho\geq\epsilon/2$ for every. On the other hand, Lemma 4 implies that there
existssuch thatand $x\in B$ . Therefore if
andfor every, then $f(x)-\rho+\psi_{r}(x)\geq\epsilon/4>0$ .
Next we consider the case where. Let $\kappa^{*}=-\inf\{f(x)-\rho|x\in B\}+1$ ,which is finite because is compact. Then Lemma 5 implies that there exist a positive
number and a positive integer such thatfor every
and$f(x)-\rho+\psi_{r}(x)\geq
1>0$. For such and , we have
. This completes the proof.
$\tilde{x}^{r}\in B(\tilde{x}^{*},\tilde{\delta})\cap B$$\tilde{x}^{*}$$\{\tilde{x}^{r}|r\in L’\}$$\tilde{x}^{*}\in\overline{K}$$\epsilon>0$$\overline{K}$$\tilde{\delta}>0$$x\in\overline{K}$$x\in B(\tilde{x}^{*},\tilde{\delta})$$\tilde{r}>0$$\psi_{r}(x)\geq-\epsilon/4$$r\geq\tilde{r}$$r\geq\tilde{r}$$x\in B(\tilde{x}^{*},\tilde{\delta})\cap B$$\tilde{x}^{*}\in B\backslash \overline{K}$$B$$x\in B(\tilde{x}^{*},\tilde{\delta})\cap B$$\tilde{\delta}$$\psi_{r}(x)\geq\kappa^{*}$$\tilde{r}$$r\geq\tilde{r}$$x$$\square$$r$

Finally, to prove (ii) of Theorem 1, we need the following lemma estabilished by
Lasserre and Netzer [11].

Lemma 6 (Corollary 3.3 of [11]) Let
be a polynomial nonnegative on -1,
For arbitmry, there exists some such that for every, the polynomial
$SOS$
is an
.
$f\in \mathbb{R}[x]$$\epsilon>0$$[$$r\geq\hat{r}$$\hat{r}$$1]^{n}$.

$f+\epsilon\Theta_{r}$Proof of (ii) of Theorem 1 : We have already proved that there exist such that for all$\tilde{r}$$r\geq\tilde{r},$$f(x)-\rho+\psi_{\overline{r}}(x)>0$

for every $x\in B=[-b, b]^{n}$ . If we put $g(y)=f(by)-\rho+\psi_{\overline{r}}$ (by),, there exists. Now Lemma 6 shows that for arbitrary
is an SOS. Putting $by=x$ , we conclude thatthen $g(y)>0$ over -1,
such that for every
is also an SOS.
$r\geq\hat{r},$$\hat{r}$$\epsilon>0$$1]^{n}$$[$$g(y)+\epsilon\Theta_{r}(y)$$\square$$f+\epsilon\Theta_{r,b}+\psi_{\overline{r}}$3

Extensions

In this section, we give two extensions of Theorem 1. The first extension is for POP withcorrelative sparsity. The second one is for POP over symmetric cones.

3.1

Extension to POP with correlative sparsity

In [15], the authors introduced the correlative sparsity for POP (1), proposed a sparse
SDP relaxation that exploits the correlative sparsity, and demonstrated that the sparse
SDP relaxation outperforms Lasserre‘s SDP relaxation. The sparse SDP relaxation is
implemented in [16] and its source code is freely available.
We give the definition of the correlative sparsity for POP (1). For this, we use
symbolic symmetric matrix , whose element is either or representing a nonzero value.
We assign either or as follows:$n\cross n$

$R$

$0$

$0$

$\star$$\star$$R_{k,\ell}=\{\begin{array}{l}\star if k=\ell,\star if \alpha_{k}\geq 1 and \alpha_{\ell}\geq 1 for some \alpha\in \mathcal{F},\star if x_{k} and x_{\ell} are involved in the polynomial f_{j} for some j=1, \ldots, m,0 o.w.\end{array}$

POP (1) is said to be correlatively sparse if the matrix$R$is sparse.

43
We give the detail of the sparse SDP relaxation proposed in [15]. We induce the$:=\{1, \ldots, n\}$ andundirected graph $G(V, E)$ from . Here$:=\{(k, l)|R_{k,\ell}=$. After applying the chordal extension to $G(V, E)$ , we generate all maximal cliquesof the extension
with. See [2, 15] and references therein for thedetail of the chordal extension. For a finite set
denotes the subvector which
consists of $x_{i}(i\in C)$ . For all
in POP (1),denotes the set of indices whose$:=\{i\in\{1,$variables are involved in , i. e.,. For afor some
finite set, the sets
anddenote the subsets ofas follows:
$R$

$E$

$V$

$\star\}$$C_{1},$$\ldots,$$G(V,\tilde{E})$$C_{p}$$E\subseteq\tilde{E}$$C\subseteq \mathbb{N},$$f_{1},$$\ldots,$$f_{j}$$C\subseteq \mathbb{N}$$\Sigma_{\infty,C}$$:=$$x_{C}$$F_{j}$$F_{j}$$\Sigma_{r,C}$$\Sigma_{r,C}$$f_{m}$$\ldots,$$n\}|\alpha_{i}\geq 1$$\Sigma_{r}$$\Sigma_{\infty,C}$$\{\sum_{k=1}^{q}g_{k}(x)^{2}\forall k=1,$$:=$$\bigcup_{r\geq 0}\Sigma_{r,C}$$\alpha\in \mathcal{F}_{j}\}$$\ldots,$$q,$ $g_{k}\in \mathbb{R}[x_{C}]_{r}\}$,.

Note that if $C=\{1, \ldots, n\}$ , then we have
. The sparse SDP
andrelaxation problem with relaxation order for POP (1) is obtained from the following
SOS relaxation problem:$\Sigma_{r,C}=\Sigma_{r}$$\Sigma_{\infty,C}=\Sigma$$r$$\rho_{r}^{sparse}:=\sup\{\rho$(7),$\sigma_{0,h}\in\Sigma_{r,C_{h}}(h=1, \ldots,p),\sigma_{j}\in\Sigma_{r_{j},D_{j}}f-\rho=\sum_{h=1}^{p}\sigma_{0,h}+\sum_{j=1}^{m}\sigma_{j}f_{j},(j=1, \ldots, m)\}$is the union of some of the maximal cliquesandsuch that$r_{j}=r-\lceil\deg(f_{j})/2\rceil$ for $j=1,$$m$ .
It should be noted that another sparse SDP relaxation is proposed in [3, 10, 12] andthe asymptotic convergence is proved. In contrast, the convergence of the sparse SDP
relaxation (7) is not shown although (7) is smaller than the SDP problem obtained byusing the sparse SDP relaxation proposed in [3, 10, 12].
We give an extension of Theorem 1 into POP with correlative sparsity. If$\{1, \ldots, n\}$ satisfy the following property, we refer this property as the running intersection
property (RIP):

where$D_{j}$$C_{1},$$C_{p}$$\ldots,$$F_{j}\subseteq C_{h}$$\ldots,$$C_{1},$$\forall h\in\{1, \ldots,p-1\},$ ョ$t\in\{1, \ldots,p\}$For$C_{1},$$\ldots,$$C_{p}\subseteq\{1, \ldots, n\}$, we define setssuch that$J_{1},$$\ldots,$$J_{p}$$C_{h+1}\cap(C_{1}\cup\cdots\cup C_{h})\subseteq C_{t}$$\bigcup_{h=1}^{p}J_{h}=\{1, \ldots, m\}$$C_{p}\subseteq$.

as follows:$J_{h}:=\{j\in\{1, \ldots, m\}|f_{j}\in \mathbb{R}[x_{C_{h}}]\}$

Clearly, we have$\ldots,$.

. In addition, we define$\psi_{r,h}(x)$$:=$$- \sum_{j\in J_{h}}(1-\frac{f_{j}(x)}{R_{j}})^{2r}$$\Theta_{r,h,b}(x)$$;=$$1+ \sum_{i\in C_{h}}(\frac{x_{i}}{b})^{2r}$,for $h=1,$.
By a similar proof of the theorem on convergence of the sparse SDP relaxation given
in [3], we can establish the correlatively sparse case of Theorem 1. Indeed, we can obtainthe theorem by using [3, Lemma 4] and Theorem 1.
$\ldots,p$44
Theorem 7 Assume that nonempty setswithcan decompose intosuch that for allin Theorem 1, there exists$B=[-b, b]^{n}$ . In addition, for any, there exists$C_{1},$$f$$\ldots,$satisfy (RIP) and we. Under assumptions
is positive over,such that for every$C_{p}\subseteq\{1, \ldots, n\}$$\hat{f}_{h}\in \mathbb{R}[x_{C_{h}}](h=1, \ldots,p)$$f=\hat{f}_{1}+\cdots+\hat{f}_{p}$$r\geq\tilde{r},$$\tilde{r}\in \mathbb{N}$$\epsilon>0$$f- \rho+\sum_{h=1}^{p}\psi_{r,h}$$r\geq\hat{r}$$\hat{r}\in \mathbb{N}$.

$f- \rho+\epsilon\sum_{h=1}^{p}\Theta_{r,h,b}+\sum_{h=1}^{p}\psi_{\overline{r},h}\in\Sigma_{\infty,C_{1}}+\cdots+\Sigma_{\infty,C_{p}}$We remark that it could follow from Theorem 5 in [3] that Theorem 7 holds without
if we assumed in Theorem 7 that all quadratic modules
the polynomial
are Archimedean. To prove Theorem 7, we
generated by $f_{j}(j\in C_{h})$ for all $h=1,$
describe Lemma 4 in [3].
$\epsilon\sum_{h=1}^{p}\Theta_{r,h,b}$$\ldots,p$Lemma 8 ([3, Lemma $4l$) Assume that we decompose
and $f>0$ on K. Then for any bounded set
andwith $g_{h}>0$ on such that$\hat{f}_{h}\in \mathbb{R}[x_{C_{h}}]$$r\in \mathbb{N}$into $f=\hat{f}_{1}+\cdots+\hat{f}_{p}$ with, there exist $\lambda\in(0,1]$ ,$f$$B\subseteq \mathbb{R}^{n}$$B$$g_{h}\in \mathbb{R}[x_{C_{h}}]$$f= \sum_{h=1j}^{p}\sum_{\in J_{h}}(1-\lambda f_{j})^{2r}f_{j}+\sum_{h=1}^{p}g_{h}$in Lemma 8 because
8,
in Lemma we obtain the desired result.

Proof of Theorem 7: We choose

Theorem 1 into3.2

$g_{h}$

as.

$\overline{K}$$B$$\overline{K}$is compact. Applying$\square$

Extension to POP with symmetric cones

In this subsection, we extend Theorem 1 into POP over symmetric cones, i. e.,$f^{*}:= \inf_{x\in \mathbb{R}^{n}}\{f(x)|G(x)\in \mathcal{E}_{+}\}$

(8)

,

where
is a symmetric cone associated with an N-dimensional Euclidean
Jordan algebra , and is -valued polynomial in . The feasible region $K$ of POP (8),is the nonnegative orthantand. Note that if isisthen (8) is identical to (1). In addition, because $nxn$ symmetric positive semidefinite
is a symmetric cone, the bilinear matrix inequalities can be formulated as (8).
cone
To constructfor (8), we introduce some notation and symbols. The product and. Let be the identity element inare, respectively, $xoy$ andinner product of, we have $eox=x\circ e=x$ . We can define eigenvalues
the Jordan algebra . For any
for all elements in the Jordan algebra as well as square matrices. See [1] for the detail.
We constructfor (8) as follows:$f\in \mathbb{R}[x],$$\mathcal{E}_{+}$$G$$\mathcal{E}$$x$$\mathcal{E}$$\{x\in \mathbb{R}^{n}|G(x)\in \mathcal{E}_{+}\}$$\mathcal{E}$$\mathbb{R}^{m}$$\mathcal{E}_{+}$$\mathbb{R}_{+}^{m}$$S_{+}^{n}$$\psi_{r}$$x,$ $y\in \mathcal{E}$$x\bullet y$$e$$x\in \mathcal{E}$$\mathcal{E}$$\mathcal{E}$$\psi_{r}$maximum absolute eigenvalue of $G(x)|x\in K^{-}\}$ ,

$M$

$:=$

$\sup$$\psi_{r}(x)$$:=$$-G(x) \bullet(e-\frac{G(x)}{M})^{2r}$

$\{$

(9)

$:=x^{k-1}\circ x$
.
and
for
where we define
defined in (9) has the same properties as in Lemmas 4
Lemma 4 in [7] shows thatand 5. Therefore, we can extend Theorem 1 into POP (8).
$x^{k}$$k\in \mathbb{N}$$\psi_{r}$$x\in \mathcal{E}$45
Theorem 9 For a given , we assume that $f(x)-\rho>0$ for every. Then there$f-\rho+\psi_{r}$ is positive over B. In addition,
existssuch that for all
for any, there 伽 $sts\hat{r}\in N$ such $tha$ オ for every,$x\in\overline{K}$$\rho$$\tilde{r}\in \mathbb{N}$$\epsilon>0$$r\geq\tilde{r},$$e$$r\geq\hat{r}$$f-\rho+\epsilon\Theta_{r,b}+\psi_{\tilde{r}}\in\Sigma$.

References[1] J. Faraut and A. Kor\’anyi: Analysis on symmetic cones. (Oxford University Press,
New York, 1994)[2] M. Fukuda, M. Kojima, K. Murota and K. Nakata: “Exploiting sparsity in semidefinite programming via matrix completion I: General framework”. SIAM Journal on
optimization, 11 (2000), 647-674.

[3] D. Grimm, T. Netzer and M. Schweighofer: “A note on the representation of positive
polynomials with structured sparsity”. Archiv der Mathematik, 89 (2007), 399-403.
[4] H. Henrion, J. B. Lasserre: “Detecting global optimality and extracting solutions in
GloptiPoly”, in H. Henrion and A. Garulli (eds.) Positive Polynomials in Control.
Lecture Notes on Control and Information Sciences, vol. 312, Springer, Berlin (2005).

[5] S. Kim, M. Kojima and H. Waki: “Generalized Lagrangian Duals and Sums ofSquares Relaxations of Sparse Polynomial optimization Problems”. SIAM Journal
on optimization, 15 (2005), 697-719.
[6] M. Kojima, S. Kim and H. Waki: “Sparsity in sums of squares of polynomials”.
Mathematical Programming, 103 (2005), 45-62.
[7] M. Kojima and M. Muramatsu: “An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones”. Mathematical Programming,
110 (2007), 315-336.
[8] J. B. Lasserre: Global optimization with polynomials and the problems of moments.
SIAM Journal on optimization, 11 (2001), 796-817.

[9] J. B. Lasserre: “A sum of squares approximation of nonnegative polynomials“. SIAM
Journal on optimization, 16 (2006), 751-765.

[10] J. B. Lasserre: “Convergent SDP-relaxations in polynomial optimization with sparsity”. SIAM Journal on optimization, 17 (2006), 822-843.
[11] J. B. Lasserre and T. Netzer: (SOS approximations of nonnegative polynomials via
simple high degree perturbations”. Mathematische Zeitsc ん r 碗, 256 (2007), 99-112.
[12] M. Laurent: “Sums of squares, moment matrices and optimization over polynomials”, In M. Putinar and S. Sullivant (eds.): IMA Volume Emerging Applications of
Algebraic Geometry, 149 (Springer, Berlin, 2009), 157-270.

46[13] P. A. Parrilo: “Semidefinite programming relaxations for semialgebraic problems”.
Mathematical Progmmming, 96 (2003), 293-320.
[14] A. Prestel and C. N. Delzell: Positive Polynomials (Springer-Verlag, Berlin, 2001).

[15] H. Waki, S. Kim, M. Kojima and M. Muramatsu: “Sums of Squares and Semidefinite
Programming Relaxations with Structured Sparsity”. SIAM Joumal on optimization, 17 (2006), 218-242.
[16] H. Waki, S. Kim, M. Kojima, M. Muramatsu and H. Sugimoto, “SparsePOP:a Sparse Semidefinite Programming Relaxation of Polynomial optimization Problems”. ACM Transactions on Mathematical Soflware, 15 (2008) 15:1-15:13.

[17] H. Waki, M. Nakata and M. Muramatsu: “Strange Behaviors of Interior-point Methods for Solving Semidefinite Programming Problems in Polynomial optimization”.
To appear in Computational optimization and Applications, (DOI: 10.1007/sl0589011-9437-8).
[18] H. Waki: “How to generate weakly infeasible semidefinite programs via Lasserre‘s
relaxations for polynomial optimization”. To appear in Optim 伽 tion Le オオ ers, (DOI:
10.1007/sll590-Oll-0384-l).