The A-truncated K-moment problem

DOI10.1007/S10208-014-9225-9zbMATH Open1331.65172arXiv1210.6930OpenAlexW2787555265MaRDI QIDQ486690FDOQ486690

Authors: Jiawang Nie 

Publication date: 16 January 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: Let A be a finite subset of N^n, and K be a compact semialgebraic set in R^n. 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.

Full work available at URL: https://arxiv.org/abs/1210.6930

Recommendations

• A semidefinite approach for truncated \(K\)-moment problems
• Binary truncated moment problems and the Hadamard product
• The truncated moment problem via homogenization and flat extensions
• Generalized truncated moment problems with unbounded sets
• Truncated \(K\)-moment problems in several variables

zbMATH Keywords

algorithmnumerical experimentflat extensioncompletely positive matrixtruncated moment problemsemidefinite program\(\mathcal A\)-truncated multisequencelocalizing matrixsums of even powers

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Semidefinite programming (90C22) Linear operator methods in interpolation, moment and extension problems (47A57) Numerical methods for integral transforms (65R10) Moment problems (44A60)

Cites Work

• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Detecting Global Optimality and Extracting Solutions in GloptiPoly
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• The \(K\)-moment problem for compact semi-algebraic sets
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Approximation of the stability number of a graph via copositive programming
• Title not available (Why is that?)
• GloptiPoly 3: moments, optimization and semidefinite programming
• Semidefinite optimization
• Sums of squares, moment matrices and optimization over polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The proof of Tchakaloff’s Theorem
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
• A semidefinite programming approach to the generalized problem of moments
• Sums of even powers of real linear forms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discriminants and nonnegative polynomials
• A generalized flat extension theorem for moment matrices
• Positivity of Riesz functionals and solutions of quadratic and quartic moment problems
• Title not available (Why is that?)
• On the computational complexity of membership problems for the completely positive cone and its dual
• Solution of the truncated complex moment problem for flat data
• Revisiting two theorems of Curto and Fialkow on moment matrices
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Positive polynomials and sums of squares
• A semidefinite approach for truncated \(K\)-moment problems
• New approximations for the cone of copositive matrices and its dual
• The truncated moment problem via homogenization and flat extensions
• Truncated \(K\)-moment problems in several variables
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• The maximal cp-rank of rank \(k\) completely positive matrices
• Linear-time complete positivity detection and decomposition of sparse matrices
• A note on the computation of the CP-rank
• Certifying convergence of Lasserre's hierarchy via flat truncation
• Title not available (Why is that?)
• An analogue of the Riesz-Haviland theorem for the truncated moment problem

Cited In (65)

• The truncated moment problem on reducible cubic curves. I: Parabolic and circular type relations
• The truncated moment problem on curves y  =  q ( x ) and yx ^ℓ  = 1
• A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
• Generalized truncated moment problems with unbounded sets
• Completely positive factorization by a Riemannian smoothing method
• Robust approximation of chance constrained optimization with polynomial perturbation
• The multivariate eigenvalues of symmetric tensors
• Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
• A simplex algorithm for rational cp-factorization
• Semidefinite Relaxation Methods for Tensor Absolute Value Equations
• Separability of Hermitian tensors and PSD decompositions
• The maximum tensor complementarity eigenvalues
• Stochastic polynomial optimization
• On truncated and full classical Markov moment problems
• T-optimal designs for multi-factor polynomial regression models via a semidefinite relaxation method
• Higher-degree tensor eigenvalue complementarity problems
• Dehomogenization for completely positive tensors
• Distributionally robust optimization with moment ambiguity sets
• The truncated complex $K$-moment problem
• The core variety of a multisequence in the truncated moment problem
• A complete semidefinite algorithm for detecting copositive matrices and tensors
• Minimizer Extraction in Polynomial Optimization Is Robust
• Tensor eigenvalue complementarity problems
• Hermitian tensor decompositions
• Tensor maximal correlation problems
• Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
• A semidefinite relaxation algorithm for checking completely positive separable matrices
• Constrained trace-optimization of polynomials in freely noncommuting variables
• Flat extension and ideal projection
• Computing the distance between the linear matrix pencil and the completely positive cone
• Completely positive tensor recovery with minimal nuclear value
• Bounding the separable rank via polynomial optimization
• The truncated Hamburger moment problems with gaps in the index set
• The truncated moment problem via homogenization and flat extensions
• A Semidefinite Relaxation Method for Partially Symmetric Tensor Decomposition
• An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
• The truncated moment problem on the union of parallel lines
• Monotonically positive matrices
• A factorization method for completely positive matrices
• Interiors of completely positive cones
• Certifying the global optimality of quartic minimization over the sphere
• Completely positive binary tensors
• Partially positive matrices
• A hierarchy of semidefinite relaxations for completely positive tensor optimization problems
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Hermitian completely positive matrices
• Truncated moment problems in ℝ^2 and recursiveness
• The strong truncated Hamburger moment problem with and without gaps
• The CP-matrix approximation problem
• Positive maps and separable matrices
• A semidefinite approach for truncated \(K\)-moment problems
• Sparse noncommutative polynomial optimization
• Symmetric tensor nuclear norms
• Estimation of multivariate generalized gamma convolutions through Laguerre expansions
• Quadratic tensor eigenvalue complementarity problems
• Convex generalized Nash equilibrium problems and polynomial optimization
• Unconstrained minimization of block-circulant polynomials via semidefinite program in third-order tensor space
• Binary truncated moment problems and the Hadamard product
• The multidimensional truncated moment problem: Carathéodory numbers
• The multidimensional truncated moment problem: Carathéodory numbers from Hilbert functions
• Completely positive tensors in the complex field
• A semidefinite algorithm for completely positive tensor decomposition
• Approximate optimal designs for multivariate polynomial regression
• A unified framework of SAGE and SONC polynomials and its duality theory
• On cones of nonnegative quartic forms

Uses Software

• SeDuMi
• GloptiPoly

This page was built for publication: The \(\mathcal A\)-truncated \(K\)-moment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q486690)