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.^[1] Lo mismo es cierto también para el problema análogo en formas positivas simétricas.^[2]^[3]

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.^[4]^[5] 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.^[6]

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^[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]

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^[9] 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.^[10] Además, existen algoritmos capaces de descomponer polinomios matriciales-positivos en polinomios no conmutativos que son sumas de cuadrados.^[11]

Referencias

↑ Hilbert, David (September 1888). «Ueber die Darstellung definiter Formen als Summe von Formenquadraten». Mathematische Annalen 32 (3): 342-350. doi:10.1007/bf01443605.
↑ Choi, M. D.; Lam, T. Y. (1977). «An old question of Hilbert». Queen's Papers in Pure and Applied Mathematics 46: 385-405.
↑ Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (May 2016). «On the Choi–Lam analogue of Hilbert's 1888 theorem for symmetric forms». Linear Algebra and Its Applications 496: 114-120. arXiv:1505.08145. doi:10.1016/j.laa.2016.01.024.
↑ Lasserre, Jean B. (2007). «Sufficient conditions for a real polynomial to be a sum of squares». Archiv der Mathematik 89 (5): 390-398. arXiv:math/0612358. doi:10.1007/s00013-007-2251-y.
↑ Powers, Victoria; Wörmann, Thorsten (1998). «An algorithm for sums of squares of real polynomials». Journal of Pure and Applied Algebra 127 (1): 99-104. doi:10.1016/S0022-4049(97)83827-3. Archivado desde el original el 16 de junio de 2010. Consultado el 21 de enero de 2022.
↑ Lasserre, Jean B. (2007). «A Sum of Squares Approximation of Nonnegative Polynomials». SIAM Review 49 (4): 651-669. Bibcode:2007SIAMR..49..651L. arXiv:math/0412398. doi:10.1137/070693709.
↑ . 1999. pp. 1446-1451. Falta el |título= (ayuda)
↑ . 1995. pp. 103-125. Falta el |título= (ayuda)
↑ . 2003. pp. 4670-4675. doi:10.1109/CDC.2003.1272307. Falta el |título= (ayuda)
↑ Helton, J. William (September 2002). «"Positive" Noncommutative Polynomials Are Sums of Squares». The Annals of Mathematics 156 (2): 675-694. doi:10.2307/3597203.
↑ Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25 de octubre de 2012). «Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials». Computational Optimization and Applications 55 (1): 137-153. doi:10.1007/s10589-012-9513-8.

Véase también

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

Datos: Q7226631

[1] Hilbert, David (September 1888). «Ueber die Darstellung definiter Formen als Summe von Formenquadraten». Mathematische Annalen 32 (3): 342-350. doi:10.1007/bf01443605.

[2] Choi, M. D.; Lam, T. Y. (1977). «An old question of Hilbert». Queen's Papers in Pure and Applied Mathematics 46: 385-405.

[3] Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (May 2016). «On the Choi–Lam analogue of Hilbert's 1888 theorem for symmetric forms». Linear Algebra and Its Applications 496: 114-120. arXiv:1505.08145. doi:10.1016/j.laa.2016.01.024.

[4] Lasserre, Jean B. (2007). «Sufficient conditions for a real polynomial to be a sum of squares». Archiv der Mathematik 89 (5): 390-398. arXiv:math/0612358. doi:10.1007/s00013-007-2251-y.

[5] Powers, Victoria; Wörmann, Thorsten (1998). «An algorithm for sums of squares of real polynomials». Journal of Pure and Applied Algebra 127 (1): 99-104. doi:10.1016/S0022-4049(97)83827-3. Archivado desde el original el 16 de junio de 2010. Consultado el 21 de enero de 2022.

[6] Lasserre, Jean B. (2007). «A Sum of Squares Approximation of Nonnegative Polynomials». SIAM Review 49 (4): 651-669. Bibcode:2007SIAMR..49..651L. arXiv:math/0412398. doi:10.1137/070693709.

[7] . 1999. pp. 1446-1451. Falta el |título= (ayuda)

[8] . 1995. pp. 103-125. Falta el |título= (ayuda)

[9] . 2003. pp. 4670-4675. doi:10.1109/CDC.2003.1272307. Falta el |título= (ayuda)

[10] Helton, J. William (September 2002). «"Positive" Noncommutative Polynomials Are Sums of Squares». The Annals of Mathematics 156 (2): 675-694. doi:10.2307/3597203.

[11] Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25 de octubre de 2012). «Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials». Computational Optimization and Applications 55 (1): 137-153. doi:10.1007/s10589-012-9513-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]