Suma de cuadrados (SOS) Polinomial

En matemáticas, una forma (i.e. un polinomio homogéneo) h(x) de grado 2m en el vector real n-dimensional x es una suma de cuadrados de formas (SOS, por sus siglas en inglés) si y sólo si existen formas $g_{1}(x),\ldots ,g_{k}(x)$ de grado m tales que

$h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.$

Cada forma que es SOS es también un polinomio positivo, y a pesar de que el converso no es siempre cierto, Hilbert probó que para n = 2, 2m = 2 o n = 3 y 2m = 4, una forma es SOS si y sólo si esta es positiva.​ Lo mismo es cierto también para el problema análogo en formas positivas simétricas.​​

A pesar de que no toda forma puede ser representada como una suma de cuadrados (SOS), ya se han encontrado condiciones suficientes explícitas que una forma sea SOS.​​ Además, toda forma real no negativa puede ser aproximada arbitrariamente bien (según la -norma de su vector de coeficientes) por una secuencia de formas $\{f_{\epsilon }\}$ que son SOS.​

Representación Cuadrada matricial (SMR)

Establecer si una forma h(x) es SOS, corresponde a solucionar un problema de optimización convexa. De hecho, cualquier h(x) puede ser escrito como

$h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}$

donde $x^{\{m\}}$ es un vector que contiene una base para las formas de grado m en x (tal como todos los monomios de grado m en x), El símbolo ′ denota que tomamos la matrix transpuesta, y H es cualquier matriz simétrica que satisface lo siguiente

$h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}$

y $L(\alpha )$ es una parameterización lineal del espacio lineal

${\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.$

La dimensión del vector $x^{\{m\}}$ está dada por

$\sigma (n,m)={\binom {n+m-1}{m}},$

mientras que la dimensión del vector $\alpha$ está dada por

$\omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).$

Entonces, h(x) es SOS sí y sólo si existe un vector $\alpha$ tal que

$H+L(\alpha )\geq 0,$

significando que la matriz $H+L(\alpha )$ es positiva-semidefinida. Esto es una prueba de viabilidad por medio de desigualdad matricial lineal (LMI, por sus siglas en inglés), lo cual es un problema de optimización convexa. La expresión $h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}$ fue introducida en​ con el nombre representación matricial cuadrada (SMR) para establecer si una forma es SOS por medio de una LMI. Esta representación es también conocida como la matriz de Gram.​

Ejemplos

• Considera la forma de grado 4 en dos variables .$h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}$ Tenemos

$m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{array}}\right)\!,~H+L(\alpha )=\left({\begin{array}{ccc}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{array}}\right)\!.$

ya que existe un α tal que $H+{\mathcal {L}}(\alpha )\geq 0$, es decir $\alpha =1$, de donde sale que h(x) es SOS.

• Considera la forma de grado 4 en tres variables $h(x)=2x_{1}^{4}-2.5x_{1}^{3}x_{2}+x_{1}^{2}x_{2}x_{3}-2x_{1}x_{3}^{3}+5x_{2}^{4}+x_{3}^{4}$. Tenemos que

$m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{array}}\right)\!,~H+L(\alpha )=\left({\begin{array}{cccccc}2&-1.25&0&-\alpha _{1}&-\alpha _{2}&-\alpha _{3}\\-1.25&2\alpha _{1}&0.5+\alpha _{2}&0&-\alpha _{4}&-\alpha _{5}\\0&0.5+\alpha _{2}&2\alpha _{3}&\alpha _{4}&\alpha _{5}&-1\\-\alpha _{1}&0&\alpha _{4}&5&0&-\alpha _{6}\\-\alpha _{2}&-\alpha _{4}&\alpha _{5}&0&2\alpha _{6}&0\\-\alpha _{3}&-\alpha _{5}&-1&-\alpha _{6}&0&1\end{array}}\right)\!.$

Ya que $H+L(\alpha )\geq 0$ para $\alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)$, tenemos entonces que h(x) es SOS.

Generalizaciones

Matricies SOS

Una forma matricial F(x) (i.e., una matriz cuyas entradas son formas) de dimensión r y grado 2m en el vector real n-dimensional x es SOS sí y sólo si existen formas matriciales $G_{1}(x),\ldots ,G_{k}(x)$ de grado m tales que

$F(x)=\sum _{i=1}^{k}G_{i}(x)'G_{i}(x).$

SMR Matricial

Establecer si una forma matricial F(x) es SOS consiste en resolver un problema de optimización convexa. De hecho, de modo parecido al caso escalar, cualquier F(x) puede ser escrita según el SMR como

$F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)$

donde $\otimes$ es el producto de Kronecker de matrices, H es cualquier matriz simétrica tal que

$F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'H\left(x^{\{m\}}\otimes I_{r}\right)$

y es $L(\alpha )$ un parameterización lineal del espacio lineal dado por

${\mathcal {L}}=\left\{L=L':~\left(x^{\{m\}}\otimes I_{r}\right)'L\left(x^{\{m\}}\otimes I_{r}\right)=0\right\}.$

La dimensión del vector $\alpha$ está dada por

$\omega (n,2m,r)={\frac {1}{2}}r\left(\sigma (n,m)\left(r\sigma (n,m)+1\right)-(r+1)\sigma (n,2m)\right).$

Entonces, F(x) es SOS sí y sólo si existe un vector $\alpha$ tal que la siguiente LMI se cumple:

$H+L(\alpha )\geq 0.$

La expresión $F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)$fue introducida en​ para establecer si una forma matricial es SOS vía un LMI.

Polinomio SOS no conmutativo

Consideremos el álgebra libre R⟨X⟩ generada por las n letras X = (X₁, ..., X_n)) que no conmutan, y equipada con la involución ^T, tal que ^T fija R y X₁, ..., X_n y reversa aquellas palabras formadas por X₁, ..., X_n. Por analogía con el caso conmutativo, lospolinomios simétricos no conmutativos f son los polinomios no commutativos y de la forma f = f^T. Cuando la evaluación de cualquier matriz real de cualquier dimensión r × r en el polinomio simétrico no conmutativo f resulta en una matriz positivo semidefinida, decimos que f es matricial-positivo.

Un polinomio no conmutativo es SOS si existen polinomios no conmutativos $h_{1},\ldots ,h_{k}$ tales que

$f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).$

Sorprendentemente, en el escenario no conmutativo, un polinomio no conmutativo es SOS sí y sólo si éste es matricial-positivo.​ Además, existen algoritmos capaces de descomponer polinomios matriciales-positivos en polinomios no conmutativos que son sumas de cuadrados.​

 

Véase también

• Optimización por medio de Suma-de-Cuadrados
• Polinomio positivo
• El decimoséptimo problema de Hilbert
• SOS-Convexidad

• Datos: Q7226631