  


An effective version of Schmüdgen's Positivstellensatz for the hypercube
Monique Laurent(moniquecwi.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) sumofsquares 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üdgentype 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, sumof=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 Modify/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  