The A-truncated K-moment problem

DOI10.1007/S10208-014-9225-9MaRDI QIDQ486690zbMATH OpenOpenAlexFDO

Authors Jiawang Nie

Publication date 16 January 2015

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

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

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)

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.

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

Cites work

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

Cited in

(65)

• A unified framework of SAGE and SONC polynomials and its duality theory
• A simplex algorithm for rational cp-factorization
• Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
• 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
• Semidefinite Relaxation Methods for Tensor Absolute Value Equations
• Separability of Hermitian tensors and PSD decompositions
• T-optimal designs for multi-factor polynomial regression models via a semidefinite relaxation method
• The maximum tensor complementarity eigenvalues
• A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
• Stochastic polynomial optimization
• Higher-degree tensor eigenvalue complementarity problems
• On truncated and full classical Markov moment problems
• Dehomogenization for completely positive tensors
• Distributionally robust optimization with moment ambiguity sets
• The core variety of a multisequence in the truncated moment problem
• The truncated complex $K$-moment problem
• A complete semidefinite algorithm for detecting copositive matrices and tensors
• Tensor eigenvalue complementarity problems
• Minimizer Extraction in Polynomial Optimization Is Robust
• Generalized truncated moment problems with unbounded sets
• Tensor maximal correlation problems
• Completely positive factorization by a Riemannian smoothing method
• Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
• A semidefinite relaxation algorithm for checking completely positive separable matrices
• Hermitian tensor decompositions
• 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
• Monotonically positive matrices
• The truncated moment problem on the union of parallel lines
• Interiors of completely positive cones
• A factorization method for completely positive matrices
• An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
• Partially positive matrices
• Certifying the global optimality of quartic minimization over the sphere
• A hierarchy of semidefinite relaxations for completely positive tensor optimization problems
• Completely positive binary tensors
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Hermitian completely positive matrices
• The strong truncated Hamburger moment problem with and without gaps
• Robust approximation of chance constrained optimization with polynomial perturbation
• Truncated moment problems in ℝ^2 and recursiveness
• The multivariate eigenvalues of symmetric tensors
• 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
• The multidimensional truncated moment problem: Carathéodory numbers
• The multidimensional truncated moment problem: Carathéodory numbers from Hilbert functions
• Binary truncated moment problems and the Hadamard product
• Completely positive tensors in the complex field
• A semidefinite algorithm for completely positive tensor decomposition
• Approximate optimal designs for multivariate polynomial regression
• On cones of nonnegative quartic forms

Describes a project that uses

Uses Software

• GloptiPoly
• SeDuMi

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)