A note on the representation of positive polynomials with structured sparsity

DOI10.1007/S00013-007-2234-ZMaRDI QIDQ2474124zbMATH OpenOpenAlexFDO

Authors David Grimm, Tim Netzer, Markus Schweighofer

Publication date 5 March 2008

Published in Archiv der Mathematik (Search for Journal in Brave)

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

zbMATH Keywords

positive polynomialsparse polynomialStructured sparsitysum of squares

Mathematics Subject Classification ID

Sums of squares and representations by other particular quadratic forms (11E25) Real algebra (13J30) Semialgebraic sets and related spaces (14P10)

Abstract: We consider real polynomials in finitely many variables. Let the variables consist of finitely many blocks that are allowed to overlap in a certain way. Let the solution set of a finite system of polynomial inequalities be given where each inequality involves only variables of one block. We investigate polynomials that are positive on such a set and sparse in the sense that each monomial involves only variables of one block. In particular, we derive a short and direct proof for Lasserre's theorem of the existence of sums of squares certificates respecting the block structure. The motivation for the results can be found in the literature and stems from numerical methods using semidefinite programming to simulate or control discrete-time behaviour of systems.

Recommendations

• Sparsity in sums of squares of polynomials
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Positive polynomials on fibre products
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity

Cited in

(23)

• Sparsity in sums of squares of polynomials
• Sparse noncommutative polynomial optimization
• Positive polynomials on fibre products
• Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Perturbed sums-of-squares theorem for polynomial optimization and its applications
• Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity
• Lasserre hierarchy for large scale polynomial optimization in real and complex variables
• LP formulations for polynomial optimization problems
• LP relaxations for a class of linear semi-infinite programming problems
• On Theorem 10 in “On Polar Polytopes and the Recovery of Sparse Representations” [Sep 07 3188-3195]
• A new scheme for approximating the weakly efficient solution set of vector rational optimization problems
• Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
• A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
• A Sparse Version of Reznick’s Positivstellensatz
• Global minimization of polynomial integral functionals
• CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
• Convergence rates for sums-of-squares hierarchies with correlative sparsity
• Sparse polynomial optimization with unbounded sets
• Sparse polynomial matrix optimization
• Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant
• Sparse polynomial optimization with matrix constraints
• Positive polynomials on projective limits of real algebraic varieties

This page was built for publication: A note on the representation of positive polynomials with structured sparsity

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