Vårt första bidrag i detta papper är att bevisa att tre naturliga summan av kvadrater (sos) baserade tillräckliga villkor för konvexitet av polynom, via definitionen av konvexitet, dess första ordning karakterisering, och dess andra ordning karakterisering, är likvärdiga. Dessa tre likvärdiga algebraiska förhållanden, hädanefter kallade sos-konvexitet, kan kontrolleras genom semidefinit programmering medan beslut konvexitet är NP-hård. Om vi betecknar uppsättningen konvexa och sosconvexa polynomials i n variabler av grad d medC n,d och på C n,d respektive d, då vårt huvudsakliga bidrag är att bevisa attC n,d = på C n,d om och endast om n = 1 eller d = 2 eller (n, d) = (2, 4). Vi presenterar också en fullständig karakterisering för former (homogen polynomials) med undantag för fallet (n, d) = (3, 4) som är gemensamt arbete med G. Blekherman och ska publiceras någon annanstans. Vårt resultat anger att uppsättningen C n,d konvexa former i n-variabler av grad d är lika med uppsättningen  på C n,d av sos-konvexa former om och endast om n = 2 eller d = 2 eller (n, d) = (3, 4). För att bevisa dessa resultat, presenterar vi i synnerhet explicita exempel på polynom i C 2,6 \ på 2,6 och C 3,4 på 3,4 och former i C 3,6 på 3,6 på C och C 4,4 på C 4,4 på C, och ett allmänt förfarande för att konstruera former i C n,d+2 på C n,d+2 på icke-negativa men inte sos bildar i n variabler och grad d. Även om det av olika skäl, är det anmärkningsvärda resultatet att konvex polynomials (resp. form) är sos-konvex exakt i fall där icke-negativa polynom (resp. former) är summor av kvadrater, som kännetecknas av Hilbert.
En fullständig karakterisering av dimensionerna och de grader för vilka begreppen konvexitet och soskonvexitet sammanfaller finns i REF.
A Complete Characterization of the Gap between Convexity and SOS-Convexity
{'venue': 'SIAM Journal on Optimization, Vol. 23, No.2, pp. 811-833, 2013', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}