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 formasde grado m tal que
Toda forma que es SOS también es un polinomio positivo , y aunque lo contrario no siempre es cierto, Hilbert demostró que para n = 2, 2m = 2 o n = 3 y 2 m = 4 una forma es SOS si y solo si es positivo. [1] Lo mismo también es válido para el problema analógico en formas simétricas positivas . [2] [3]
Aunque no todas las formas se pueden representar como SOS, se han encontrado condiciones explícitas suficientes para que una forma sea SOS. [4] [5] Además, cada forma real no negativa se puede aproximar tanto como se desee (en la-norm de su vector de coeficientes) por 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 ) se puede escribir como
dónde 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 satisfaga
y es una parametrización lineal del espacio lineal
La dimensión del vector es dado por
mientras que la dimensión del vector es dado por
Entonces, h ( x ) es SOS si y solo si existe un vector tal que
lo que significa que la matriz es positivo-semidefinito . Esta es una prueba de viabilidad de desigualdad de matriz lineal (LMI), que es un problema de optimización convexa. La expresionse introdujo en [7] con el nombre de representación matricial cuadrada (SMR) para establecer si un formulario es SOS a través de un LMI. Esta representación también se conoce como matriz de Gram. [8]
Ejemplos de
- Considere la forma del grado 4 en dos variables . Tenemos
- Dado que existe α tal que , a saber , se deduce que h ( x ) es SOS.
- Considere la forma del grado 4 en tres variables . Tenemos
- Desde por , se deduce que h ( x ) es SOS.
Generalizaciones
Matrix SOS
Una forma matricial F ( x ) (es decir, una matriz cuyas entradas son formas) de dimensión r y grado 2m en el vector n- dimensional real x es SOS si y solo si existen formas matricialesde grado m tal 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 ) se puede escribir de acuerdo con el SMR como
dónde es el producto de Kronecker de las matrices, H es cualquier matriz simétrica que satisfaga
y es una parametrización lineal del espacio lineal
La dimensión del vector es dado por
Entonces, F ( x ) es SOS si y solo si existe un vector de manera que el siguiente LMI se mantenga:
La expresion se introdujo en [9] para establecer si una forma de matriz es SOS a través de un LMI.
Polinomio no conmutativo SOS
Considere el álgebra libre R ⟨ X ⟩ generado por la n noncommuting letras X = ( X 1 , ..., X n ) y equipado con la involución T , tal que T correcciones de R y X 1 , ..., X n y Palabras inversas formadas por X 1 , ..., X n . Por analogía con el caso conmutativo, el polinomio simétrico no conmutativo f son los polinomios no conmutativos de la forma f = f T . Cuando cualquier matriz real de cualquier dimensión rxr se evalúa en un polinomio simétrico no conmutativo 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 tal que
Sorprendentemente, en el escenario no conmutativo, un polinomio no conmutativo es SoS si y solo si es de matriz positiva. [10] Además, existen algoritmos disponibles para descomponer polinomios de matriz positiva en suma de cuadrados de polinomios no conmutativos. [11]
Referencias
- ^ Hilbert, David (septiembre de 1888). "Ueber die Darstellung definiter Formen als Summe von Formenquadraten" . Mathematische Annalen . 32 (3): 342–350. doi : 10.1007 / bf01443605 .
- ^ Choi, MD; Lam, TY (1977). "Una vieja pregunta de Hilbert". Papeles de Queen en Matemática Pura y Aplicada . 46 : 385–405.
- ^ Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (mayo de 2016). "En 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 .
- ^ Lasserre, Jean B. (2007). "Condiciones suficientes para que un polinomio real sea una suma de cuadrados" . Archiv der Mathematik . 89 (5): 390–398. arXiv : matemáticas / 0612358 . CiteSeerX 10.1.1.240.4438 . doi : 10.1007 / s00013-007-2251-y .
- ^ 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). "Aproximación de una suma de cuadrados de polinomios no negativos". Revisión SIAM . 49 (4): 651–669. arXiv : matemáticas / 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 en matemáticas puras . págs. 103-125.
- ^ Chesi, G .; Garulli, A .; Tesi, A .; Vicino, A. (2003). "Estabilidad robusta para sistemas politópicos a través de 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 " positivos "no conmutativos son sumas de cuadrados". Los anales de las matemáticas . 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 sumas de cuadrados hermitianos 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 .
Ver también
- Optimización de suma de cuadrados
- Polinomio positivo
- El decimoséptimo problema de Hilbert
- Convexidad SOS