The -Truncated -Moment Problem

Let be a finite set, and be a compact semialgebraic set. An -truncated multisequence (-tms) is a vector indexed by elements in . The -truncated -moment problem (-TKMP) concerns whether or not a given -tms admits a -measure , i.e., is a nonnegative Borel measure supported in such that for all . This paper proposes a numerical algorithm for solving -TKMPs. It aims at finding a flat extension of by solving a hierarchy of semidefinite relaxations for a moment optimization problem, whose objective is generated in a certain randomized way. If admits no -measures and is -full (there exists that is positive on ), then is infeasible for all big enough, which gives a certificate for the nonexistence of representing measures. If admits a -measure, then for almost all generated , this algorithm has the following properties: i) we can asymptotically get a flat extension of by solving the hierarchy ; ii) under a general condition that is almost sufficient and necessary, we can get a flat extension of by solving for some ; iii) the obtained flat extensions admit a -atomic -measure with . The decomposition problems for completely positive matrices and sums of even powers of real linear forms, and the standard truncated -moment problems, are special cases of -TKMPs. They can be solved numerically by this algorithm.