The link between 1-norm approximation and effective positivstellensatze for the hypercube

Etienne de Klerk, Juan C. Vera

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The Schmudgen Positivstellensatz gives a certificate to verify positivity of a strictly positive polynomial f on a compact, basic, semi-algebraic set K subset of R-n. A Positivstellensatz of this type is called effective if one may bound the degrees of the polynomials appearing in the certificate in terms of properties of f. If K = [-1, 1](n) and 0 < f(min) := min(x is an element of K) f (x), then the degrees of the polynomials appearing in the certificate may be bounded by O(root f(max )- f(min/)f(min)), where f(max) := max(x is an element of K) f (x), as was recently shown by fmin Laurent and Slot [Optimization Letters 17:515-530, 2023]. The big-O notation suppresses dependence on n and the degree d of f. In this paper we show a similar result, but with a better dependence on n and d. In particular, our bounds depend on the 1-norm of the coefficients of f, that may readily be calculated.
Original languageEnglish
Number of pages21
JournalNumerical Algebra Control and Optimization
DOIs
Publication statusE-pub ahead of print - Dec 2024

Keywords

  • Polynomial kernel method
  • Positivstellensatz
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'The link between 1-norm approximation and effective positivstellensatze for the hypercube'. Together they form a unique fingerprint.

Cite this