Optimization Online


An effective version of Schmüdgen's Positivstellensatz for the hypercube

Monique Laurent(monique***at***cwi.nl)
Lucas Slot(lucas.slot***at***cwi.nl)

Abstract: Let S be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schmüdgen's Positivstellensatz then states that for any \eta>0, the nonnegativity of f+\eta on S can be certified by expressing f+\eta as a conic combination of products of the polynomials that occur in the inequalities defining S, where the coefficients are (globally nonnegative) sum-of-squares polynomials. It does not, however, provide explicit bounds on the degree of the polynomials required for such an expression. We show that in the special case where S=[-1,1]^n is the hypercube, a Schmüdgen-type certificate of nonnegativity exists involving only polynomials of degree O(1/\sqrt{\eta}). This improves quadratically upon the previously best known estimate in O(1/\eta). Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval [-1,1].

Keywords: semidefinite programming, sum-of=squares polynomials, Lasserre hierarchy, performance analysis

Category 1: Global Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: Posted as arXiv:2109.09528

Download: [PDF]

Entry Submitted: 11/13/2021
Entry Accepted: 12/01/2021
Entry Last Modified: 11/13/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society