SOS approximations of nonnegative polynomials via simple high degree perturbations

DOI10.1007/S00209-006-0061-8MaRDI QIDQ883108zbMATH OpenOpenAlexFDO

Authors Tim Netzer, Jean B. Lasserre

Publication date 31 May 2007

Published in Mathematische Zeitschrift (Search for Journal in Brave)

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

zbMATH Keywords

moment problempositive polynomialsreal algebraic geometrysemidefinite programmingsum of squares

Mathematics Subject Classification ID

Sums of squares and representations by other particular quadratic forms (11E25) Real algebra (13J30) Moment problems (44A60) Semidefinite programming (90C22)

Abstract: We show that every real polynomial $f$ nonnegative on $[-1,1{]}^n$ can be approximated in the $l_1$-norm of coefficients, by a sequence of polynomials $f_{epr}$ that are sums of squares. This complements the existence of s.o.s. approximations in the denseness result of Berg, Christensen and Ressel, as we provide a very simple and extit{explicit} approximation sequence. Then we show that if the Moment Problem holds for a basic closed semi-algebraic set $K_{S}subset{R}^n$ with nonempty interior, then every polynomial nonnegative on $K_S$ can be approximated in a similar fashion by elements from the corresponding preordering. Finally, we show that the degree of the perturbation in the approximating sequence depends on $epsilon$ as well as the degree and the size of coefficients of the nonnegative polynomial $f$, but not on the specific values of its coefficients.

Recommendations

• Positive polynomials and sums of squares: theory and practice
• An effective version of Schmüdgen's Positivstellensatz for the hypercube
• Computation of sum of squares polynomials from data points
• Multihomogeneous nonnegative polynomials and sums of squares
• An algorithmic approach to Schmüdgen's Positivstellensatz
• Certificates of positivity for real polynomials. Theory, practice, and applications
• Complexity estimates for the Schmüdgen Positivstellensatz
• scientific article; zbMATH DE number 1824112
• Lower bounds for a polynomial in terms of its coefficients
• Operator-theoretic Positivstellensätze

Cites work

• A Sum of Squares Approximation of Nonnegative Polynomials
• Distinguished representations of strictly positive polynomials
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 1601019 (Why is no real title available?)
• scientific article; zbMATH DE number 4036424 (Why is no real title available?)
• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• On the Momentum Problem for Distribution Functions in More than One Dimension
• On the Momentum Problem for Distribution Functions in More Than One Dimension. II
• Optimization of Polynomials on Compact Semialgebraic Sets
• Positive definite functions on Abelian semigroups
• Positivity and sums of squares: a guide to recent results
• Positivity, sums of squares and the multi-dimensional moment problem
• Positivity, sums of squares and the multi-dimensional moment problem II
• Quasi-analytic vectors
• Semidefinite Programming
• Semidefinite programming relaxations for semialgebraic problems
• Sum of Squares Approximation of Polynomials, Nonnegative on a Real Algebraic Set
• The K-moment problem for compact semi-algebraic sets
• There are significantly more nonnegative polynomials than sums of squares

Cited in

(29)

• Approximate optimal designs for multivariate polynomial regression
• Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
• The moment problem for continuous positive semidefinite linear functionals
• Positivity certificates and polynomial optimization on non-compact semialgebraic sets
• Distributionally robust polynomial chance-constraints under mixture ambiguity sets
• On solving a class of fractional semi-infinite polynomial programming problems
• On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
• An algorithm for decomposing a non-negative polynomial as a sum of squares of rational functions
• Convex sets with semidefinite representation
• Application of Jacobi's representation theorem to locally multiplicatively convex topological \(\mathbb R\)-algebras
• Perturbed sums-of-squares theorem for polynomial optimization and its applications
• The K-moment problem for continuous linear functionals
• Semidefinite approximations of projections and polynomial images of semialgebraic sets
• Convexifying positive polynomials and sums of squares approximation
• Approximating nonnegative polynomials via spectral sparsification
• Positivstellensätze for quantum multigraphs
• Lebesgue decomposition in action via semidefinite relaxations
• A paradox in bosonic energy computations via semidefinite programming relaxations
• A generalization of Strassen’s Positivstellensatz
• Deciding robust feasibility and infeasibility using a set containment approach: an application to stationary passive gas network operations
• A Sum of Squares Approximation of Nonnegative Polynomials
• Sum of Squares Approximation of Polynomials, Nonnegative on a Real Algebraic Set
• Convex optimization and parsimony of L_p-balls representation
• A unified framework of SAGE and SONC polynomials and its duality theory
• Globally trace-positive noncommutative polynomials and the unbounded tracial moment problem
• Positive semidefinite diagonal minus tail forms are sums of squares
• The link between 1-norm approximation and effective Positivstellensätze for the hypercube
• Title not available (Why is no real title available?)
• Moments and sums of squares for polynomial optimization and related problems

This page was built for publication: SOS approximations of nonnegative polynomials via simple high degree perturbations

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