Un polinomio multivariado es SOS-convexo (o suma de cuadrados convexo ) si su matriz de Hesse H se puede factorizar como H ( x ) = S T ( x ) S ( x ) donde S es una matriz (posiblemente rectangular) cuyas entradas son polinomios en x . [1] En otras palabras, la matriz de Hesse es un polinomio de matriz SOS .
Una definición equivalente es que la forma definida como g ( x , y ) = y T H ( x ) y es una suma de cuadrados de formas . [2]
Conexión con la convexidad
Si un polinomio es SOS-convexo, entonces también es convexo. [ cita necesaria ] Dado que establecer si un polinomio es SOS-convexo equivale a resolver un problema de programación semidefinido , la convexidad SOS se puede utilizar como indicador para establecer si un polinomio es convexo. Por el contrario, decidir si un polinomio genérico de grado mayor que cuatro es convexo es un problema NP-difícil. [3]
El primer contraejemplo de un polinomio que es convexo pero no SOS-convexo fue construido por Amir Ali Ahmadi y Pablo Parrilo en 2009. [4] El polinomio es un polinomio homogéneo que es suma de cuadrados y está dado por: [4]
![{\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}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ese mismo año, Grigoriy Blekherman demostró de manera no constructiva que existen formas convexas que no se pueden representar como suma de cuadrados. [5] James Saunderson afirmó en 2021 un ejemplo explícito de una forma convexa (con grado 4 y 272 variables) que no es una suma de cuadrados.
Conexión con la no negatividad y la suma de cuadrados
En 2013, Amir Ali Ahmadi y Pablo Parrilo demostraron que todo polinomio homogéneo convexo en n variables y grado 2 d es SOS-convexo si y solo si (a) n = 2 o (b) 2 d = 2 o (c) n = 3 y 2 d = 4. [7] Impresionantemente, la misma relación es válida para polinomios homogéneos no negativos en n variables y grado 2 d que se pueden representar como polinomios de suma de cuadrados (ver el decimoséptimo problema de Hilbert ).
Referencias
- ^ Helton, J. William; Nie, Jiawang (2010). "Representación semidefinida de conjuntos convexos". Programación Matemática . 122 (1): 21–64. arXiv : 0705.4068 . doi :10.1007/s10107-008-0240-y. ISSN 0025-5610. S2CID 1352703.
- ^ Ahmadi, Amir Ali; Parrilo, Pablo A. (2010). "Sobre la equivalencia de condiciones algebraicas para la convexidad y cuasiconvexidad de polinomios". 49ª Conferencia IEEE sobre Decisión y Control (CDC) . págs. 3343–3348. doi :10.1109/CDC.2010.5717510. hdl : 1721.1/74151 . ISBN 978-1-4244-7745-6. S2CID 11904851.
- ^ Ahmadi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A.; Tsitsiklis, John N. (2013). "NP-dureza de decidir la convexidad de polinomios cuárticos y problemas relacionados". Programación Matemática . 137 (1–2): 453–476. arXiv : 1012.1908 . doi :10.1007/s10107-011-0499-2. ISSN 0025-5610. S2CID 2319461.
- ^ ab Ahmadi, Amir Ali; Parrilo, Pablo A. (2009). "Un polinomio definido positivo de Hesse que no factoriza". Actas de la 48ª Conferencia IEEE sobre Decisión y Control (CDC) celebrada conjuntamente con la 28ª Conferencia de Control de China de 2009 . págs. 1195-1200. doi :10.1109/CDC.2009.5400519. hdl : 1721.1/58871 . ISBN 978-1-4244-3871-6. S2CID 5344338.
- ^ Blekherman, Grigoriy (4 de octubre de 2009). "Formas convexas que no son sumas de cuadrados". arXiv : 0910.0656 [matemáticas.AG].
- ^ Saunderson, James (2022). "Una forma convexa que no es una suma de cuadrados". Matemáticas de la Investigación de Operaciones . 48 : 569–582. arXiv : 2105.08432 . doi :10.1287/moor.2022.1273. S2CID 234763204.
- ^ Ahmadi, Amir Ali; Parrilo, Pablo A. (2013). "Una caracterización completa de la brecha entre convexidad y convexidad SOS". Revista SIAM sobre Optimización . 23 (2): 811–833. arXiv : 1111.4587 . doi :10.1137/110856010. ISSN 1052-6234. S2CID 16801871.
Ver también