The \({\mathcal {A}}\)-Truncated \(K\)-Moment Problem

Let \({\mathcal {A}}\subseteq {\mathbb {N}}^n\) be a finite set, and \(K\subseteq {\mathbb {R}}^n\) be a compact semialgebraic set. An \({\mathcal {A}}\) -truncated multisequence (\({\mathcal {A}}\)-tms) is a vector \(y=(y_{\alpha })\) indexed by elements in \({\mathcal {A}}\). The \({\mathcal {A}}\)-truncated \(K\)-moment problem (\({\mathcal {A}}\)-TKMP) concerns whether or not a given \({\mathcal {A}}\)-tms \(y\) admits a \(K\)-measure \(\mu \), i.e., \(\mu \) is a nonnegative Borel measure supported in \(K\) such that \(y_\alpha = \int _K x^\alpha \mathtt {d}\mu \) for all \(\alpha \in {\mathcal {A}}\). This paper proposes a numerical algorithm for solving \({\mathcal {A}}\)-TKMPs. It aims at finding a flat extension of \(y\) by solving a hierarchy of semidefinite relaxations \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \) for a moment optimization problem, whose objective \(R\) is generated in a certain randomized way. If \(y\) admits no \(K\)-measures and \({\mathbb {R}}[x]_{{\mathcal {A}}}\) is \(K\)-full (there exists \(p \in {\mathbb {R}}[x]_{{\mathcal {A}}}\) that is positive on \(K\)), then \((\mathtt {SDR})_k\) is infeasible for all \(k\) big enough, which gives a certificate for the nonexistence of representing measures. If \(y\) admits a \(K\)-measure, then for almost all generated \(R\), this algorithm has the following properties: i) we can asymptotically get a flat extension of \(y\) by solving the hierarchy \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \); ii) under a general condition that is almost sufficient and necessary, we can get a flat extension of \(y\) by solving \((\mathtt {SDR})_k\) for some \(k\); iii) the obtained flat extensions admit a \(r\)-atomic \(K\)-measure with \(r\le |{\mathcal {A}}|\). The decomposition problems for completely positive matrices and sums of even powers of real linear forms, and the standard truncated \(K\)-moment problems, are special cases of \({\mathcal {A}}\)-TKMPs. They can be solved numerically by this algorithm.