2012/10/25 by Jiawang Nie, Nie, Jiawang · 8 citations
Computer Science · Mathematics · #44A60 #47A57 #90C22 #90C90 #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Functional Analysis (math.FA) #Polynomial and algebraic computation #math.FA #msc:44A60 #msc:47A57 #msc:90C22 #msc:90C90
paper · pdf · doi:10.48550/arxiv.1210.6930
29 pages
openalex publication_date 2012/10/25 · arxiv created 2014/08/28 · arxiv updated 2014/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let A be a finite subset of Nn, and K be a compact semialgebraic set in Rn. An A-tms is a vector y indexed by elements in A. The A-truncated K-moment problem (A-TKMP) studies whether a given A-tms y admits a K-measure or not. This paper proposes a numerical algorithm for solving A-TKMPs. It is based on finding a flat extension of y by solving a hierarchy of semidefinite relaxations (SDR)k for a moment optimization problem, whose objective R is generated in a certain randomized way. If y admits no K-measures and R[x]A is K-full, then (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, we prove that: i) we can asymptotically get a flat extension of y by solving the hierarchy (SDR)k\; ii) under a general condition that is almost sufficient and necessary, we can get a flat extension of y by solving (SDR)k for some k; this occurred in all our numerical experiments; iii) the obtained flat extensions admit a r-atomic K-measure with r <= |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 A-TKMPs, and hence can be solved numerically by this algorithm.