stringtranslate.com

SOS-convexidad

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]

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

  1. ^ 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ Blekherman, Grigoriy (4 de octubre de 2009). "Formas convexas que no son sumas de cuadrados". arXiv : 0910.0656 [matemáticas.AG].
  6. ^ 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.
  7. ^ 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