SOS approximations of nonnegative polynomials via simple high degree perturbations

DOI10.1007/S00209-006-0061-8zbMATH Open1122.13005arXivmath/0510456OpenAlexW2049225870MaRDI QIDQ883108FDOQ883108

Authors: Tim Netzer, Jean B. Lasserre 

Publication date: 31 May 2007

Published in: Mathematische Zeitschrift (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

semidefinite programmingreal algebraic geometrymoment problemsum of squarespositive polynomials

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (27)

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

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)