En matemáticas , una forma (es decir, un polinomio homogéneo) h ( x ) de grado 2 m en el vector real n -dimensional x es suma de cuadrados de formas (SOS) si y solo si existen formas de grado m tales que
Toda forma que es SOS es también un polinomio positivo , y aunque la inversa no siempre es cierta, Hilbert demostró que para n = 2, 2 m = 2, o n = 3 y 2 m = 4 una forma es SOS si y sólo si es positiva. [1] Lo mismo es válido para el problema analógico sobre formas simétricas positivas. [2] [3]
Aunque no todas las formas pueden representarse como SOS, se han encontrado condiciones explícitas suficientes para que una forma sea SOS. [4] [5] Además, cada forma real no negativa puede aproximarse tan cerca como se desee (en la -norma de su vector de coeficientes) mediante una secuencia de formas que son SOS. [6]
Representación matricial cuadrada (SMR)
Establecer si una forma h ( x ) es SOS equivale a resolver un problema de optimización convexa . De hecho, cualquier h ( x ) puede escribirse como
donde es un vector que contiene una base para las formas de grado m en x (como todos los monomios de grado m en x ), el primo ′ denota la transpuesta , H es cualquier matriz simétrica que satisface
y es una parametrización lineal del espacio lineal
La dimensión del vector está dada por
mientras que la dimensión del vector está dada por
Entonces, h ( x ) es SOS si y solo si existe un vector tal que
significa que la matriz es positiva-semidefinida . Esta es una prueba de viabilidad de desigualdad matricial lineal (LMI), que es un problema de optimización convexa. La expresión fue introducida en [7] con el nombre de representación matricial cuadrada (SMR) para establecer si una forma es SOS a través de una LMI. Esta representación también se conoce como matriz de Gram. [8]
Ejemplos
- Consideremos la forma de grado 4 en dos variables . Tenemos Dado que existe α tal que , es decir , se deduce que h ( x ) es SOS.
- Consideremos la forma de grado 4 en tres variables . Tenemos Como para , se deduce que h ( x ) es SOS.
Generalizaciones
Matriz SOS
Una forma matricial F ( x ) (es decir, una matriz cuyas entradas son formas) de dimensión r y grado 2 m en el vector real n -dimensional x es SOS si y sólo si existen formas matriciales de grado m tales que
Matriz SMR
Establecer si una forma matricial F ( x ) es SOS equivale a resolver un problema de optimización convexa. De hecho, de manera similar al caso escalar, cualquier F ( x ) puede escribirse según el SMR como
donde es el producto de Kronecker de matrices, H es cualquier matriz simétrica que satisface
y es una parametrización lineal del espacio lineal
La dimensión del vector está dada por
Entonces, F ( x ) es SOS si y sólo si existe un vector tal que se cumple la siguiente LMI:
La expresión se introdujo en [9] para establecer si una forma matricial es SOS a través de un LMI.
Polinomio no conmutativo SOS
Considérese el álgebra libre R ⟨ X ⟩ generada por las n letras no conmutativas X = ( X 1 , ..., X n ) y equipada con la involución T , tal que T fija R y X 1 , ..., X n e invierte las palabras formadas por X 1 , ..., X n . Por analogía con el caso conmutativo, los polinomios simétricos no conmutativos f son los polinomios no conmutativos de la forma f = f T . Cuando cualquier matriz real de cualquier dimensión r × r se evalúa en un polinomio no conmutativo simétrico f da como resultado una matriz semidefinida positiva , se dice que f es matriz-positiva.
Un polinomio no conmutativo es SOS si existen polinomios no conmutativos tales que
Sorprendentemente, en el escenario no conmutativo, un polinomio no conmutativo es SOS si y solo si es positivo para la matriz. [10] Además, existen algoritmos disponibles para descomponer polinomios positivos para la matriz en sumas de cuadrados de polinomios no conmutativos. [11]
Referencias
- ^ Hilbert, David (septiembre de 1888). "Ueber die Darstellung definiter Formen als Summe von Formenquadraten". Annalen Matemáticas . 32 (3): 342–350. doi :10.1007/bf01443605. S2CID 177804714.
- ^ Choi, MD; Lam, TY (1977). "Una vieja cuestión de Hilbert". Queen's Papers in Pure and Applied Mathematics . 46 : 385–405.
- ^ Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (mayo de 2016). "Sobre el análogo de Choi-Lam del teorema de Hilbert de 1888 para formas simétricas". Álgebra lineal y sus aplicaciones . 496 : 114–120. arXiv : 1505.08145 . doi :10.1016/j.laa.2016.01.024. S2CID 17579200.
- ^ Lasserre, Jean B. (2007). "Condiciones suficientes para que un polinomio real sea una suma de cuadrados". Archiv der Mathematik . 89 (5): 390–398. arXiv : math/0612358 . CiteSeerX 10.1.1.240.4438 . doi :10.1007/s00013-007-2251-y. S2CID 9319455.
- ^ Powers, Victoria ; Wörmann, Thorsten (1998). "Un algoritmo para sumas de cuadrados de polinomios reales" (PDF) . Revista de álgebra pura y aplicada . 127 (1): 99–104. doi : 10.1016/S0022-4049(97)83827-3 .
- ^ Lasserre, Jean B. (2007). "Una aproximación de suma de cuadrados de polinomios no negativos". SIAM Review . 49 (4): 651–669. arXiv : math/0412398 . Código Bibliográfico :2007SIAMR..49..651L. doi :10.1137/070693709.
- ^ Chesi, G.; Tesi, A.; Vicino, A.; Genesio, R. (1999). "Sobre la convexificación de algunos problemas de distancia mínima". Actas de la 5.ª Conferencia Europea de Control . Karlsruhe, Alemania: IEEE. págs. 1446–1451.
- ^ Choi, M.; Lam, T.; Reznick, B. (1995). "Sumas de cuadrados de polinomios reales". Actas de simposios sobre matemáticas puras . págs. 103–125.
- ^ Chesi, G.; Garulli, A.; Tesi, A.; Vicino, A. (2003). "Estabilidad robusta para sistemas politópicos mediante funciones de Lyapunov dependientes de parámetros polinomiales". Actas de la 42.ª Conferencia IEEE sobre decisión y control . Maui, Hawái: IEEE. págs. 4670–4675. doi :10.1109/CDC.2003.1272307.
- ^ Helton, J. William (septiembre de 2002). "Los polinomios no conmutativos "positivos" son sumas de cuadrados". The Annals of Mathematics . 156 (2): 675–694. doi :10.2307/3597203. JSTOR 3597203.
- ^ Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25 de octubre de 2012). "Aspectos algorítmicos de las sumas de cuadrados hermíticos de polinomios no conmutativos". Optimización computacional y aplicaciones . 55 (1): 137–153. CiteSeerX 10.1.1.416.543 . doi :10.1007/s10589-012-9513-8. S2CID 254416733.
Véase también