Suma de cuadrados (SOS) Polinomial

Summarize Timeline Top Qs Fact Check

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

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

donde ${\displaystyle 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

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

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

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

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

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

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

${\displaystyle \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 ${\displaystyle \alpha }$ tal que

${\displaystyle H+L(\alpha )\geq 0,}$

significando que la matriz ${\displaystyle 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 ${\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}$ fue introducida en^[7] 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.^[8]

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

${\displaystyle 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 ${\displaystyle H+{\mathcal {L}}(\alpha )\geq 0}$, es decir ${\displaystyle \alpha =1}$, de donde sale que h(x) es SOS.

• Considera la forma de grado 4 en tres variables ${\displaystyle 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

${\displaystyle 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 ${\displaystyle H+L(\alpha )\geq 0}$ para ${\displaystyle \alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)}$, tenemos entonces que h(x) es SOS.