A Semidefinite Approach for Truncated K-Moment Problems

A truncated moment sequence (tms) in n variables and of degree d is a finite sequence y=(y _α ) indexed by nonnegative integer vectors α:=(α ₁,…,α _n ) such that α ₁+⋯+α _n ≤d. Let K⊆ℝⁿ be a semialgebraic set. The truncated K-moment problem (TKMP) is: How can one check if a tms y admits a K-measure μ (a nonnegative Borel measure supported in K) such that \(y_{\alpha}= \int_{K} x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\,\mathrm{d}\mu\) for every α? This paper proposes a semidefinite programming (SDP) approach for solving TKMP. When K is compact, we get the following results: whether a tms admits a K-measure or not can be checked via solving a sequence of SDP problems; when y admits no K-measure, a certificate for the nonexistence can be found; when y admits one, a representing measure for y can be obtained from solving the SDP problems under some necessary and some sufficient conditions. Moreover, we also propose a practical SDP method for finding flat extensions, which in our numerical experiments always found a finitely atomic representing measure when it exists.

1. Throughout the paper, the moments of a tms are listed in the graded lexicographical ordering, and moments of different degrees are separated by semicolons.

2. The ranks here are evaluated numerically. We ignore singular values smaller than 10⁻⁶ when evaluating ranks. The same procedure is applied in computing ranks throughout this paper.

3. Here only four decimal digits are shown to present points of the support.

The authors thank Larry Fialkow for helpful comments on this work. J. William Helton was partially supported by NSF grants DMS-0700758, DMS-0757212, and the Ford Motor Co. Jiawang Nie was partially supported by NSF grants DMS-0757212 and DMS-0844775.

Authors and Affiliations

1. Department of Mathematics, University of California, San Diego, 9500 Gilman Drive, La Jolla, CA, 92093, USA

   J. William Helton & Jiawang Nie

Corresponding author

Correspondence to Jiawang Nie.

Communicated by Michael Todd.

Appendix: Optimization with Measures

We prove that for a dense set of optimization problems (4.3), the optimal solutions are measures having finite supports. This justifies condition (4.5) in Sect. 4.2.

Lemma A.1

Let y be a tms in and K be a subset of ℝⁿ. Assume the set meas(y,K) is nonempty. If a measure μ is an extreme point of meas(y,K), then μ is finitely atomic and \(|\mathrm{supp}(\mu)|\leq\binom{n+d}{d}\).

Proof

We prove by contradiction. Suppose μ is extreme and \(|\mbox {supp}(\mu )| > N:=\binom{n+d}{d}\). Then we can decompose supp(μ) in a way such that

For each j, let μ _j be the restriction of μ on S _j , i.e., \(\mu_{j} = \mu|_{S_{j}}\). Note that dimℝ[x] _d =N. So there exists (a ₁,…,a _N+1)≠0 satisfying

Define a measure ν (possibly non-positive) such that

Note that supp(ν)⊆supp(μ). Then, for ϵ>0 sufficiently small, μ±ϵν are nonnegative Borel measures supported on K, representing the same tms y and

This contradicts the extremality of μ in meas(y,K). □

Theorem A.2

Let y be a tms in . For any real analytic function f on a compact set K and ϵ>0, there exists an real analytic function \(\tilde{f}\) on K such that \(\|\tilde{f} - f \|_{\infty} \leq\epsilon\) and every minimizer of

has cardinality at most \(\binom{n+d}{d}\). Let Sol be the set of all optimizers above. Then

Proof

For a given real analytic function f on K, consider the optimization problem

The set of positive measures on K whose total masses equal y ₀ is compact in the weak-∗ topology (denote this topology by \(\mathcal{T}\)) by the Alaoglu Theorem (cf. [2, Theorem V.3.1]). Recall that the weak-∗ topology is the topology on the measures regarded as the dual space of the Banach space . It is the weakest topology for which the convergence of a sequence of measures μ _n →μ implies that for every

This implies that every moment of μ _n converges to the corresponding one of μ. Hence, meas(y,K) is \(\mathcal{T}\)-closed inside a compact set, and it is also \(\mathcal{T}\)-compact.

Thus, by compactness of its feasible set, the optimization problem (A.3) has a minimizer, which is a generalized convex combination of certain extreme points, by the Choquet–Bishop–de Leeuw Theorem (cf. [22]). To be more precise, this means that for every \(\hat{\mu}\in \mathrm{meas}(y,K)\), there exists a probability measure Γ on the set \(\mathcal{E}\) of extreme points of meas(y,K) such that

for every affine function ℓ on meas(y,K).

Let γ ^∗ be the optimal value of (A.3) and \(\tilde{\mu}\) be a minimizer, and let \(\widetilde{\varGamma}\) denote the probability measure on \(\mathcal{E}\) representing \(\tilde{\mu}\) and let \(\widetilde{\mathcal{E}}\) denote the support of \(\widetilde{\varGamma}\). Then

By optimality of γ ^∗, ∫ _K f dμ≥γ ^∗ for all \(\mu\in\widetilde{\mathcal{E}}\). Indeed, ∫ _K f dμ=γ ^∗ for all \(\mu\in\widetilde {\mathcal{E}}\). Otherwise, suppose ∫ _K f dμ>γ ^∗ on a set of μ having positive \(\widetilde{\varGamma}\) measure. Then

which yields a contradiction. This implies ∫ _K f dμ=γ ^∗ on \(\widetilde{\mathcal{E}}\). Choose a measure \(\mu^{*} \in\widetilde{\mathcal{E}}\). It is extreme and the optimum of (A.3) is attained at μ ^∗.

By Lemma A.1, we have \(|\mathrm{supp}(\mu^{*})|\leq N:=\binom{n+d}{d}\). Without loss of generality, we can normalize y ₀=∫ _K  dμ ^∗=1 and denote supp(μ ^∗)={u ₁,…,u _r }. Let e(x) be the exponential function defined as

Clearly, e(x)=ϵ for all x∈supp(μ ^∗) and 0<e(x)<ϵ for all \(x \not\in\mathrm{supp}(\mu^{*})\). This implies that

Set \(\tilde{f}:= f- e\) and

Then

On the other hand

because μ ^∗ belongs to meas(y,K). Thus

and μ ^∗ is a minimizer of (A.5) as well as (A.1).

Suppose \(\tilde{\mu}^{*}\) is another minimizer of (A.5). We wish to show that

If this is not true, then \(\int e \,\mathrm {d}{\tilde{\mu}^{*}} <\epsilon\) and

This implies

which is a contradiction.

The inequality (A.2) follows from the first part, because the average of all the minimizers is still a minimizer. □

Remark

As we can see in the above proof, if μ ^∗ is a unique minimizer of (4.3), then μ ^∗ must have finite support and \(|\mathrm{supp}(\mu^{*})|\leq \binom {n+d}{d}\).

The following lemmas are used in the proof of Theorem 4.3.

Lemma A.3

Suppose K⊆B(0,R) with R<1 and c is in . If a tms w belongs to E _k (y)∪E _∞(y), then

and for any integer t>0 we have

Proof

First, we consider the case that w∈E _k (y). The condition M _t−1(ρ∗w)⪰0 in (4.1) implies that for every t=1,…,k

A repeated application of the above gives

Since M _k (w) is positive semidefinite, we can see that

Thus, we have

When k>t, we have

Let M _t,k be the principal submatrix of M _k (w) whose row and column indices β satisfy t<|β|≤k. Clearly, M _t,k ⪰0 and we similarly have

Combining all of the above, we get

Note that w _α =0 if |α|>2k. So, (A.8) is true.

Second, we consider the case that w∈E _∞(y). The sequence w admits a K-measure μ such that w _α =∫ _K x ^α dμ for every α. For every k, consider the truncation z=∫ _K [x]_2k  dμ. Clearly, the tms z is feasible for (4.1). By part (i), we have

The above is true for all k, and implies (A.8) by letting k→∞. □

Lemma A.4

Assume K⊆B(0,R) with R<1, and c is in . Let γ _k ,γ be the optimal values of (4.1) and (4.3), respectively. Then, we have the convergence γ _k →γ as k→∞.

Proof

By Lemma A.3, for an arbitrary ϵ>0, there exists t such that

This implies that for every w∈E _k (y)∪E _∞(y) with k≥t, we have

Now we consider the truncated optimization problems

(A.11)

and

Let τ _k and τ be the optimal values of (A.11) and (A.12) respectively. Note that (A.11) is a semidefinite relaxation of (A.12). Thus, we have τ _k →τ, by Theorem 1 of Lasserre [16]. The inequality (A.10) implies that for all k≥t

This shows that |γ _k −τ _k |≤ϵ for k≥t. Applying a similar argument to (A.12), we can get |γ−τ|≤ϵ. Note that

Because τ _k →τ, one gets

Since ϵ>0 is arbitrary, we must have γ _k →γ as k→∞. □