- An effective version of Schmüdgen's Positivstellensatz for the hypercube Monique Laurent(moniquecwi.nl) Lucas Slot(lucas.slotcwi.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/2021Entry Accepted: 12/01/2021Entry Last Modified: 11/13/2021Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.