Linear optimization with cones of moments and nonnegative polynomials
From MaRDI portal
Publication:745685
DOI10.1007/S10107-014-0797-6zbMATH Open1327.65113arXiv1305.2970OpenAlexW1985650248MaRDI QIDQ745685FDOQ745685
Authors: Jiawang Nie 
Publication date: 14 October 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: Let A be a finite subset of N^n and R[x]_A be the space of real polynomials whose monomial powers are from A. Let K be a compact basic semialgebraic set of R^n such that R[x]_A contains a polynomial that is positive on K. Denote by P_A(K) the cone of polynomials in R[x]_A that are nonnegative on K. The dual cone of P_A(K) is R_A(K), the set of all A-truncated moment sequences in R^A that admit representing measures supported in K. Our main results are: i) We study the properties of P_A(K) and R_A(K) (like interiors, closeness, duality, memberships), and construct a convergent hierarchy of semidefinite relaxations for each of them. ii) We propose a semidefinite algorithm for solving linear optimization problems with the cones P_A(K) and R_A(K), and prove its asymptotic and finite convergence; a stopping criterion is also given. iii) We show how to check whether P_A(K) and R_A(K) intersect affine subspaces; if they do, we show to get get a point in the intersections; if they do not, we prove certificates for the non-intersecting.
Full work available at URL: https://arxiv.org/abs/1305.2970
Recommendations
- Moments and sums of squares for polynomial optimization and related problems
- Extension of completely positive cone relaxation to moment cone relaxation for polynomial optimization
- Convergent conic linear programming relaxations for cone convex polynomial programs
- Positive polynomials and semidefinite programming
- Moments, positive polynomials and their applications
convergencealgorithmmomentsum of squareslinear optimizationrepresenting measuresemidefinite programnonnegative polynomialtruncated moment sequence
Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- 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
- Semidefinite programming relaxations for semialgebraic problems
- Title not available (Why is that?)
- GloptiPoly 3: moments, optimization and semidefinite programming
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Title not available (Why is that?)
- Semidefinite representations for finite varieties
- A semidefinite programming approach to the generalized problem of moments
- Sums of even powers of real linear forms
- Title not available (Why is that?)
- On the complexity of Putinar's Positivstellensatz
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Flat extensions of positive moment matrices: recursively generated relations
- Solution of the truncated complex moment problem for flat data
- Revisiting two theorems of Curto and Fialkow on moment matrices
- An exact Jacobian SDP relaxation for polynomial optimization
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Exposed faces of semidefinitely representable sets
- Positive polynomials and projections of spectrahedra
- Title not available (Why is that?)
- A semidefinite approach for truncated \(K\)-moment problems
- The truncated moment problem via homogenization and flat extensions
- Algebraic degree of polynomial optimization
- Truncated \(K\)-moment problems in several variables
- Theta bodies for polynomial ideals
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- Sufficient and necessary conditions for semidefinite representability of convex hulls and sets
- Semidefinite representation of convex sets
- Certifying convergence of Lasserre's hierarchy via flat truncation
- Convexity in SemiAlgebraic Geometry and Polynomial Optimization
- Convex sets with semidefinite representation
- A prolongation-projection algorithm for computing the finite real variety of an ideal
- The CP-matrix completion problem
- Convex hulls of algebraic sets
- The approach of moments for polynomial equations
- Probability Measures on Compact Sets
- Semidefinite Representation for Convex Hulls of Real Algebraic Curves
Cited In (52)
- A convex optimization model for finding non-negative polynomials
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
- Separability of Hermitian tensors and PSD decompositions
- The saddle point problem of polynomials
- The maximum tensor complementarity eigenvalues
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Stochastic polynomial optimization
- Extension of completely positive cone relaxation to moment cone relaxation for polynomial optimization
- Higher-degree tensor eigenvalue complementarity problems
- Dehomogenization for completely positive tensors
- Distributionally robust optimization with moment ambiguity sets
- Learning diagonal Gaussian mixture models and incomplete tensor decompositions
- Cones of multipowers and combinatorial optimization problems
- Rational Generalized Nash Equilibrium Problems
- Optimal data fitting: a moment approach
- Nonnegative Polynomial Optimization over Unit Spheres and Convex Programming Relaxations
- A utopia point method-based robust vector polynomial optimization scheme
- Tensor eigenvalue complementarity problems
- Local saddle points for unconstrained polynomial optimization
- Generalized truncated moment problems with unbounded sets
- Optimization Problems over Non-negative Polynomials with Interpolation Constraints
- Saddle points of rational functions
- Hermitian tensor decompositions
- Tensor maximal correlation problems
- A semidefinite relaxation algorithm for checking completely positive separable matrices
- Computing the distance between the linear matrix pencil and the completely positive cone
- Completely positive tensor recovery with minimal nuclear value
- Quantum entanglement, symmetric nonnegative quadratic polynomials and moment problems
- Uniform and monotone line sum optimization
- The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
- Properties of the cone of non-negative polynomials and duality
- Finite convergence of moment-SOS relaxations with nonreal radical ideals
- LP-based tractable subcones of the semidefinite plus nonnegative cone
- Bilinear optimality constraints for the cone of positive polynomials
- Completely positive binary tensors
- A hierarchy of semidefinite relaxations for completely positive tensor optimization problems
- Robust approximation of chance constrained optimization with polynomial perturbation
- Hermitian completely positive matrices
- The multivariate eigenvalues of symmetric tensors
- The CP-matrix approximation problem
- Positive maps and separable matrices
- Symmetric tensor nuclear norms
- Real radicals and finite convergence of polynomial optimization problems
- A GENERAL FRAMEWORK FOR CONVEX RELAXATION OF POLYNOMIAL OPTIMIZATION PROBLEMS OVER CONES
- Quadratic tensor eigenvalue complementarity problems
- Convex generalized Nash equilibrium problems and polynomial optimization
- Completely positive tensors in the complex field
- Moment approximations for set-semidefinite polynomials
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- A semidefinite algorithm for completely positive tensor decomposition
- Title not available (Why is that?)
Uses Software
This page was built for publication: Linear optimization with cones of moments and nonnegative polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745685)
