wypukłość SOS

Wielomian wielowymiarowy jest SOS-wypukły (lub suma kwadratów wypukły ⁾ , jeśli jego macierz Hesja H może być rozłożona jako H ( x ) = ST ( x ) S ( x ) gdzie S jest macierzą (prawdopodobnie prostokątną), której wpisy są wielomianami w x . Innymi słowy, macierz Hessego jest wielomianem macierzowym SOS .

Równoważna definicja jest taka, że forma zdefiniowana jako g ( x , y )= y ^T H ( x ) y jest sumą kwadratów form .

Połączenie z wypukłością

Jeśli wielomian jest SOS-wypukły, to jest również wypukły. ^{[ Potrzebne źródło ]} Ponieważ ustalenie, czy wielomian jest wypukły SOS, sprowadza się do rozwiązania półokreślonego problemu z programowaniem, wypukłość SOS może służyć jako wskaźnik zastępczy do ustalenia, czy wielomian jest wypukły. W przeciwieństwie do tego, podjęcie decyzji, czy ogólny wielomian stopnia większego niż cztery jest wypukły, jest problemem NP-trudnym.

Pierwszy kontrprzykład wielomianu, który jest wypukły, ale nie jest wypukły SOS, został skonstruowany przez Amira Ali Ahmadi i Pablo Parrilo w 2009 roku. Wielomian jest jednorodnym wielomianem, który jest sumą kwadratów i jest dany przez:

${\ Displaystyle p (x) = 32x_ {1} ^ {8} + 118x_ {1} ^ {6} x_ {2} ^ {2} + 40x_ {1} ^ { 6}x_{3}^{2}+25x_{1}^{4}x_{2}^{4}-43x_{1}^{4}x_{2}^{2}x_{3}^{ 2}-35x_{1}^{4}x_{3}^{4}+3x_{1}^{2}x_{2}^{4}x_{3}^{2}-16x_{1}^ {2}x_{2}^{2}x_{3}^{4}+24x_{1}^{2}x_{3}^{6}+16x_{2}^{8}+44x_{2} ^{6}x_{3}^{2}+70x_{2}^{4}x_{3}^{4}+60x_{2}^{2}x_{3}^{6}+30x_{3 }^{8}}$

W tym samym roku Grigorij Blekherman udowodnił w sposób niekonstruktywny , że istnieją formy wypukłe, których nie da się przedstawić jako sumy kwadratów. Wyraźny przykład formy wypukłej (ze zmiennymi stopnia 4 i 272), która nie jest sumą kwadratów, podał James Saunderson w 2021 roku.

Związek z nieujemnością i sumą kwadratów

W 2013 roku Amir Ali Ahmadi i Pablo Parrilo wykazali, że każdy wielomian jednorodny wypukły w n zmiennych i stopniu 2 d jest wypukły SOS wtedy i tylko wtedy, gdy (a) n = 2 lub (b) 2 d = 2 lub (c) n = 3 i 2 d = 4. Co ciekawe, ta sama zależność obowiązuje dla nieujemnego wielomianu jednorodnego w n zmiennych i stopnia 2 d , który można przedstawić jako sumę kwadratów wielomianów (patrz siedemnasty problem Hilberta ).

Zobacz też